Number permutations in python iterative

Question

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 numbers of upto 20 digits length. For example I the first few permutations would be 0, 1, 2, 10, 11, 12, ... 1122, 1211.

There are existing answers using Iterator in Python here or here and those gives the full permutation directly.

But I need to perform some tests over each permutations and if I keep the entire permutations list in memory it becomes too big, especially for 20 digits it comes to 3²⁰ permutations.

So my question is can it be done without recursion, so that I can perform the tests over each permutations.

Edit:

I'm looking at permutations with repetitions. So for a number of say 20 digits, each digit can take value from [0, 1, 2]. That's why the number of permutations in that case will come to 3²⁰.

score 2 · Answer 1 · answered Aug 12 '15 at 09:47

2

Yes, your program could like like this:

import itertools


def perform_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)

answered Aug 12 '15 at 09:47

Gill Bates

14,330
23
70
138

One problem with this is if I try to use a smaller `tuple` to get a larger permutations it doesn't work for me. Case in point `for pu in permutations([1, 2], 3): perform_test(pu)` ; `def perform_test(pux): print pux` – kay dee Aug 12 '15 at 10:22
Using the following function `def perform_test(pux): # print pux if int(pux)%9==0: print "OK" ` throws an error `TypeError: unsupported operand type(s) for %: 'tuple' and 'int'` – kay dee Aug 12 '15 at 10:25
@kaydee "if I try to use a smaller tuple to get a larger permutations it doesn't work for me." - what result do you expect as permutations of three elements by two places? – Gill Bates Aug 12 '15 at 12:39
e.g. 12101 it's generating elements are `[0, 1, 2]`, but if I do `permutations([0, 1, 2], 5)` it doesn't give me anything. Each digit of a, let's say 5 digit long number, can have any one digit from `[0, 1, 2]`. So it's a permutations with repetitions allowed. Hope that clears up. – kay dee Aug 12 '15 at 14:21

score 2 · Accepted Answer · edited Jul 05 '18 at 19:17

2

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:

0 1 2 00 01 02 10 11 12 20 21 22 000 001 002 010 [...] 2220 2221 2222

edited Jul 05 '18 at 19:17

ayhan

70,170
20
182
203

answered Aug 12 '15 at 15:13

Ber

40,356
16
72
88

Thanks, it works great is generating the sequence. How can I a test function such as `def perform_test(pux): if pux%9==0: print "OK"` over each item on the resulting list? – kay dee Aug 12 '15 at 16:09
@kaydee Thanks for up-vorting and accepting my answer, if it works for you. :) Your test: `if int(pux) % 9 == 0: print pux, "OK"` – Ber Aug 13 '15 at 06:48

score 1 · Answer 3 · edited May 23 '17 at 10:26

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):

def digit_to_char(digit):
    if digit < 10:
        return str(digit)
    return chr(ord('a') + digit - 10)

def perm(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 = 0
while len(str(permutation)) < 20:
    permutation = perm(i)
    do_test(permutation)
    i += 1

Number permutations in python iterative

3 Answers3

Linked

Related