2

I need to generate all possible permutations (with repetitions) of the characters in a string. If the string is 'abc', the output should be:

aaa aab aac abc ... cbc cca ccb ccc

I can't use the itertools module and I don't want to use recursion (because this is just an example. What I really need will output millions of permutations and I'm afraid to run out of memory)

I can do it like this:

s = 'abc'

for c1 in range(0, 3):
    for c2 in range(0, 3):
        for c3 in range(0, 3):
            print(s[c1]+s[c2]+s[c3])

Basically, I have as many for cycles as the string has characters. Now imagine if the string has length 10, for example!

Is there a better way of doing this?

gfields
  • 105
  • 1
  • 2
  • 7
  • 1
    Possible duplicate of [Finding all possible permutations of a given string in python](http://stackoverflow.com/questions/8306654/finding-all-possible-permutations-of-a-given-string-in-python) – idjaw Oct 23 '15 at 22:50
  • 1
    Why can't you use the itertools module? – pppery Oct 23 '15 at 22:53

2 Answers2

9

One easy way to go about this problem is to think of the characters in your string as digits in an unusual number system. The length of the string is the base. So the permutations (with repetition) of 'abc' correspond to the numbers from 0 to 3**3-1 in base 3, where 'a' is the digit 0, 'b' is 1 and 'c' is 2.

def permutations_with_repetition(s):
    base = len(s)
    for n in range(base**base):
        yield "".join(s[n // base**(base-d-1) % base] for d in range(base))

Sample run:

>>> for p in permutations_with_repetition("abc"):
    print(p)


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

If you were allowed to use itertools, you'd want itertools.product with a repeat keyword argument: itertools.product("abc", repeat=3)

Blckknght
  • 100,903
  • 11
  • 120
  • 169
  • You could also use `base**d` instead of `base**(base-d-1)` – Stefan Pochmann Oct 24 '15 at 00:00
  • @StefanPochmann: That puts the output digits in the opposite order, which may not be desirable (e.g. the sequence goes `"aaa", "baa", "caa", "aba", ...`). There are ways of fixing it, and I played around with `reversed()` and a list comprehension, but just changing the exponent seemed easier. @DSM, thanks for pointing that out, I've fixed it. – Blckknght Oct 24 '15 at 03:50
  • @Blckknght Can you please explain the math behind the following statement ? yield "".join(s[n // base**(base-d-1) % base] for d in range(base)) – Dhiwakar Ravikumar Jan 06 '19 at 08:42
  • @DhiwakarRavikumar: It's not too tricky mathematically. `n // base ** (base-d-1) % base` is the numerical value of the `d`th digit of `n` in when converted to base `base` (with leading zeros, if necessary). The `s[...]` is an indexing that gets the appropriate character for the digit, and `"".join(...)` turns all the separate digits into a single string. – Blckknght Jan 06 '19 at 18:48
3

If you are afraid to run out of memory use generators. Keep on calling d.next() for your values. It's only efficient for small nested loops.

>>> s = 'abc'
>>> d =( (x,y,z) for x in s for y in s for z in s)
>>> d.next()
'aaa'
>>> d.next()
'aab'

If you want all the values just do 

list(d)

For arbitrary length use: This makes as many groups as elements in strings and then iterates over all of them and keeps on adding to the final result. This is how itertools.product is implemented in python. For more details visit here

def product(x):
        final = [[]]
        l = len(x)
        groups = [list(x)] * l
        for i in groups:
            final = [x+[y] for x in final for y in i]
        for k in final:
            yield ''.join(k)

Force all results:

list(product('abc'))

['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']
garg10may
  • 5,794
  • 11
  • 50
  • 91