Permutations With Repeating Characters (Python)
The number of combination should be n^k (n=number of elements, k=combination length). For this case, n and k happens to be the same.
ab = 2^2 = 4 abc = 3^3 = 9 If we use `abc`(n=3) to generate permutations of length 1 (k=1) P(abc, 1) = a, b, c = 3^1 = 3 combinations If we use `abc`(n=3) to generate permutations of length 2 (k=2) P(abc, 2) = aa, bb, cc, ab, ac . = 3^2 = 9 combinationsLinear iteration of all elements is unlikely to generate all combinations, so a recursive solution is more likely.
Imagine the following diagram.
Result of P(a) is used to generate P(ab). We start with a prefix of 1 character, then we more character to prefix until all combination are generated recursively.
def _permutation_repeat(text, prefix, n, k): if k == 0: # base, len(prefix) == len(text) print(prefix) return for i in range(n): new_prefix = prefix + text[i] # a, aa, aaa, aab, aac ab, aba, abb, abc # print(new_prefix) _permutation_repeat(text, new_prefix, n, k-1) # print('---') def permutation_repeat(text, k): _permutation_repeat(text, "", len(text), k) permutation_repeat("abc", 3)The combination is generated in the following sequence.
a -> aa -> aaa aab aac ab -> aba abb abc ac -> aca acb acc b -> ba -> baa bab bac . . aaa aab aac aba abb abc aca acb acc baa bab bac bba bbb bbc bca bcb bcc caa cab cac cba cbb cbc cca ccb cccPermutation with repeats in result is actually Cartesian Product .
You can use Python itertools.product to generate the same result.
from itertools import product for _set in product(list('abc'), repeat=3): print(''.join(_set))❤️ Is this article helpful?
Buy me a coffee ☕ or support my work via PayPal to keep this space 🖖 and ad-free.
Do send some 💖 to @d_luaz or share this article.
A dream boy who enjoys making apps, travelling and making youtube videos. Follow me on @d_luaz
Travelopy — discover travel places in Malaysia, Singapore, Taiwan, Japan.
Combinations and Permutations in Python with itertools
If you a list, dictionary, or other iterable object of values you need to generate combinations and permutations from, Python has the built-in itertools module as part of its standard library. The permutations of an iterable are every possible ordering of all of the values, while the combinations are every possible selection of some, none, or all of the values. For example, the permutations and combinations of the set are:
| Permutations | Combinations |
|---|---|
| ABC, ACB, BAC, BCA, CAB | (none), A, B, C, AB, AC, BC, ABC |
You can also reuse the values multiple times, which is called permutations with repetition and combinations with repetition (also called replacement):
| Permutations with Repetition | Combinations with Repetition |
|---|---|
| AAA, AAB, AAC, ABA, ABB, ABC, ACA, ACB, ACC, BAA, BAB, BAC, BBA, BBB, BBC, BCA, BCB, BCC, CAA, CAB, CAC, CBA, CBB, CBC, CCA, CCB, CCC | (none), A, B, C, AA, AB, AC, BB, BC, CC, AAA, AAB, AAC, ABB, ABC, ACC, BBB, BBC, BCC, CCC |
(Note that permutations with repetition is effectively the same as a password cracker that tries every possible combination of characters to brute force a password.)
The number of permutations and combinations quickly grows when more values are added to the iterable object. The total number of permutations and combinations is given in the following:
| Permutations of n Values | Combinations of n Values | |
| Without Repetition | n! | 2^n |
| With Repetition | n^n | «2n choose n», that is, (2n)! / (n!)^2 |
But to have Python generate permutations, you can use itertools.permutations() :
>>> import itertools >>> for v in itertools.permutations(['A', 'B', 'C']): . print(v) . ('A', 'B', 'C') ('A', 'C', 'B') ('B', 'A', 'C') ('B', 'C', 'A') ('C', 'A', 'B') ('C', 'B', 'A') >>> >>> list(itertools.permutations(['A', 'B', 'C'])) [('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')] >>> list(itertools.permutations(['A', 'B', 'C'], 2)) [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')] >>> list(itertools.permutations(['A', 'B', 'C'], 1)) [('A',), ('B',), ('C',)] To have Python generate combinations, you can use itertools.combinations() :
>>> import itertools >>> for v in itertools.combinations(['A', 'B', 'C'], 2): . print(v) . ('A', 'B') ('A', 'C') ('B', 'C') >>> list(itertools.combinations(['A', 'B', 'C'], 1)) [('A',), ('B',), ('C',)] >>> list(itertools.combinations(['A', 'B', 'C'], 2)) [('A', 'B'), ('A', 'C'), ('B', 'C')] >>> list(itertools.combinations(['A', 'B', 'C'], 3)) [('A', 'B', 'C')] Note that the combinations() function takes a second argument for the number of values to select. To get all combinations (also called the power set), you’ll need to make multiple calls to combinations() :
>>> powerSet = [] >>> import itertools >>> for k in range(4): . powerSet.extend(itertools.combinations(['A', 'B', 'C'], k)) . >>> powerSet [(), ('A',), ('B',), ('C',), ('A', 'B'), ('A', 'C'), ('B', 'C'), ('A', 'B', 'C')] To get permutations with repetition/replacement, call itertools.product() and pass the size of the iterable object for its repeat argument:
>>> import itertools >>> for v in itertools.product(['A', 'B', 'C'], repeat=3): . print(v) . ('A', 'A', 'A') ('A', 'A', 'B') ('A', 'A', 'C') ('A', 'B', 'A') ('A', 'B', 'B') ('A', 'B', 'C') ('A', 'C', 'A') ('A', 'C', 'B') ('A', 'C', 'C') ('B', 'A', 'A') ('B', 'A', 'B') ('B', 'A', 'C') ('B', 'B', 'A') ('B', 'B', 'B') ('B', 'B', 'C') ('B', 'C', 'A') ('B', 'C', 'B') ('B', 'C', 'C') ('C', 'A', 'A') ('C', 'A', 'B') ('C', 'A', 'C') ('C', 'B', 'A') ('C', 'B', 'B') ('C', 'B', 'C') ('C', 'C', 'A') ('C', 'C', 'B') ('C', 'C', 'C') >>> list(itertools.product(['A', 'B', 'C'], repeat=3)) [('A', 'A', 'A'), ('A', 'A', 'B'), ('A', 'A', 'C'), ('A', 'B', 'A'), ('A', 'B', 'B'), ('A', 'B', 'C'), ('A', 'C', 'A'), ('A', 'C', 'B'), ('A', 'C', 'C'), ('B', 'A', 'A'), ('B', 'A', 'B'), ('B', 'A', 'C'), ('B', 'B', 'A'), ('B', 'B', 'B'), ('B', 'B', 'C'), ('B', 'C', 'A'), ('B', 'C', 'B'), ('B', 'C', 'C'), ('C', 'A', 'A'), ('C', 'A', 'B'), ('C', 'A', 'C'), ('C', 'B', 'A'), ('C', 'B', 'B'), ('C', 'B', 'C'), ('C', 'C', 'A'), ('C', 'C', 'B'), ('C', 'C', 'C')] To get combinations with repetition/replacement, call itertools.combinations_with_replacement() :
>>> import itertools >>> for v in itertools.combinations_with_replacement(['A', 'B', 'C'], 3): . print(v) . ('A', 'A', 'A') ('A', 'A', 'B') ('A', 'A', 'C') ('A', 'B', 'B') ('A', 'B', 'C') ('A', 'C', 'C') ('B', 'B', 'B') ('B', 'B', 'C') ('B', 'C', 'C') ('C', 'C', 'C') >>> list(itertools.combinations_with_replacement(['A', 'B', 'C'], 3)) [('A', 'A', 'A'), ('A', 'A', 'B'), ('A', 'A', 'C'), ('A', 'B', 'B'), ('A', 'B', 'C'), ('A', 'C', 'C'), ('B', 'B', 'B'), ('B', 'B', 'C'), ('B', 'C', 'C'), ('C', 'C', 'C')] If you’re like me and you had trouble remembering the differences between permutations and combinations, with and without repetition, and which Python functions implement them, bookmark this page to have easy access in the future.
Learn to program for free with my books for beginners:
Sign up for my «Automate the Boring Stuff with Python» online course with this discount link.