Number Permutations In Python Iterative

I need to generate permutations of digits, the number can be bigger than the digit count. For my current purpose I need to generate permutations of these digits 0, 1, 2 to get numb

Solution 1:

What you are looking is called a Cartesian product, not a permutation. Python itertools have a method itertools.product() to produce the desired result:

import itertools

for p in itertools.product(range(3), repeat=4):
    print p

Output is 3^4 lines:

(0, 0, 0, 0)
(0, 0, 0, 1)
(0, 0, 0, 2)
(0, 0, 1, 0)
(0, 0, 1, 1)
...
(2, 2, 2, 1)
(2, 2, 2, 2) 

To produce output tuples with length form 1 to 4, use an additional iteration:

for l in range(1, 5):
    for p in itertools.product(range(3), repeat=l):
        print p

Finally, this works for string elements, too:

for i in range(5):
    for p in itertools.product(('0', '1', '2'), repeat=i):
        print''.join(p),
print

Output:

012000102101112202122000001002010 [...] 2220 2221 2222

Solution 2:

Yes, your program could like like this:

import itertools


defperform_test(permutation):
    pass# permutations() does not construct entire list, but yields # results one by on.for permutation in itertools.permutations([1, 2, 3, 4, 5], 2):
    perform_test(permutation)

Solution 3:

While there are ways to do this using itertools etc, here is a way that is a bit different from what you would normally do.

If you were to have a list of these permutations in order, what you would actually have is ternary numbers that represent their place in the list. e.g. list[4] is 11 which is 4 in ternary (3*1+1*1). So you could convert the index value that you want to test into ternary and that would produce the correct value.

While python can do conversion from an integer to its form in that base (e.g. int("11",3) outputs 4) the reverse is not implicitly implemented. There are lots of implementations out there though. Here is a good one (modified for your case):

defdigit_to_char(digit):
    if digit < 10:
        returnstr(digit)
    returnchr(ord('a') + digit - 10)

defperm(number):
    (d, m) = divmod(number, 3)
    if d > 0:
        return perm(d) + digit_to_char(m)
    return digit_to_char(m)

So if you wanted to find the 20th permutation, you could do perm(20), which would give you 202. So now you can just do a regular loop through the index values that you want. With no storage of big lists in memory.

permutation = 0
i = 0whilelen(str(permutation)) < 20:
    permutation = perm(i)
    do_test(permutation)
    i += 1