More efficient way to get integer permutations?

Question

I can get integer permutations like this:

myInt = 123456789

l = itertools.permutations(str(myInt))
[int(''.join(x)) for x in l]

Is there a more efficient way to get integer permutations in Python, skipping the overhead of creating a string, then joining the generated tuples? Timing it, the tuple-joining process makes this 3x longer than list(l).

added supporting information

myInt =123456789
def v1(i): #timeit gives 258ms
    l = itertools.permutations(str(i))
    return [int(''.join(x)) for x in l]

def v2(i): #timeit gives 48ms
    l = itertools.permutations(str(i))
    return list(l)

def v3(i): #timeit gives 106 ms
    l = itertools.permutations(str(i))
    return [''.join(x) for x in l]

I took the liberty of posting some timeit results to help clarify OP's problem — Joran Beasley, May 19 '13 at 00:22

Simeon Visser · Answer 1 · 2013-05-19T00:43:37.673

5

You can do:

>>> digits = [int(x) for x in str(123)]
>>> n_digits = len(digits)
>>> n_power = n_digits - 1
>>> permutations = itertools.permutations(digits)
>>> [sum(v * (10**(n_power - i)) for i, v in enumerate(item)) for item in permutations]
[123, 132, 213, 231, 312, 321]

This avoids conversion to and from a tuple as it'll use the integer's position in the tuple to compute its value (e.g., (1,2,3) means 100 + 20 + 3).

Because the value of n_digits is known and the same throughout the process, I think you can also optimize the computations to:

>>> values = [v * (10**(n_power - i)) for i, v in enumerate(itertools.repeat(1, n_digits))]
>>> values
[100, 10, 1]
>>> [sum(v * index for v, index in zip(item, values)) for item in permutations]
[123, 132, 213, 231, 312, 321]

I also think we don't need to call zip() all the time because we don't need that list:

>>> positions = list(xrange(n_digits))
>>> [sum(item[x] * values[x] for x in positions) for item in permutations]
[123, 132, 213, 231, 312, 321]

edited May 19 '13 at 00:43

answered May 19 '13 at 00:24

Simeon Visser

118,920
18
185
180

And the first line being the same as `digits = [int(x) for x in str(123)]` – Jared May 19 '13 at 00:26
This does indeed work but I don't believe it is more efficient than v1 given above. Thank you! – jumbopap May 19 '13 at 00:34
1

@JumBopap: I have just added an optimization that I could think of. Have you timed it rather than believing it's not faster? – Simeon Visser May 19 '13 at 00:35
I did indeed time it, on my computer v1 = 0.452999830246 seconds and your first version is 1.46900010109 seconds and your second version is 1.35899996758 seconds. – jumbopap May 19 '13 at 00:39
1

@JumBopap: thanks, that's pretty clear. I have added another version that doesn't call `zip()` all the time. Not sure if it's much faster but if not, have you considered writing a small C module for this? You can then call that C function from Python. – Simeon Visser May 19 '13 at 00:44

ppw0 · Answer 2 · 2018-12-18T01:28:35.203

I can't comment on Simeon's answer, so I'm adding this here.

If you try to permute 120 with the function in the answer, you get

[120,102,210,201,12,21]

12 and 21 are wrong answers, so I made a modification to discard them:

def permute(n):
        digits = [int(x) for x in str(n)]
        n_digits = len(digits)
        n_power = n_digits - 1
        values = [v * (10**(n_power - i)) for i, v in
            enumerate(itertools.repeat(1, n_digits))]
        positions = list(range(n_digits))
        permutations = {sum(item[x] * values[x] for x in positions) for
            item in itertools.permutations(digits) if item[0] > 0}
        for p in permutations:
            yield p

Edit: also forgot to add that the function will count the same digits twice, leaving you with duplicates, so I modified that as well.

Fernando Macedo · Answer 3 · 2013-05-19T00:37:45.203

0

This will give you a generator:

import itertools as it
gen = it.permutations(range(1, 10))

Then you can iterate over each item:

for i in gen:
    #some code

Or convert it to a list, but it'll take some time:

items = list(gen)

EDIT: Clarified that you want back an integer, maybe the fastest way is using another lazy evaluation:

gen = (int('%d%d%d%d%d%d%d%d%d' % x) for x in it.permutations(range(1, 10)))

edited May 19 '13 at 00:37

answered May 19 '13 at 00:13

Fernando Macedo

2,518
1
24
25

I was about to say the same thing but his code is indeed much slower than calling list – Joran Beasley May 19 '13 at 00:15
In this process wouldn't I have to iterate through every integer in the generator, convert the integers to a string, then iterate again to join every tuple, then finally convert the joined-tuple back into ints? – jumbopap May 19 '13 at 00:21

More efficient way to get integer permutations?

3 Answers3

Linked