CODEWITHSUNDEEP
pythonpython-2.7
whatf
whatf

Reputation: 6458

unexpected results while calculating permutations while using itertools.permutation

Given string is '0123456789'. I wanted to generate its one millionth permutation(1000000).

I wanted to give itertools.permutations a first try: 

In [85]: import itertools

In [86]: a = list(itertools.permutations('0123456789'))

In [87]: a[1]
Out[87]: ('0', '1', '2', '3', '4', '5', '6', '7', '9', '8')

In [88]: a[1000000]
Out[88]: ('2', '7', '8', '3', '9', '1', '5', '6', '0', '4')

However if i run the following code:

def perm(S, perms=[], current=[], maximum=None):
    if maximum and len(perms) > maximum:
        return
    size = len(S)
    for i in range(size):
        subset = list(S)
        del(subset[i])
        tmp_current = list(current)
        tmp_current.append(S[i])
        if size > 1:
            perm(subset, perms, tmp_current, maximum)

        else:
            perms.append(tmp_current)
            if maximum:
                if len(perms) == maximum:
                    print tmp_current
                    return

perm('0123456789', maximum=1000000)

# the result is ['2', '7', '8', '3', '9', '1', '5', '4', '6', '0']

The answer from itertools.permutations and from the above psuedo code does not match.

[2783915604] from itertools
[2783915460] from the snippet above

The second answer is the correct answer. Could anyone please explain me why the first process is not yielding a correct result?

Upvotes: 0

Views: 169

Answers (1)

Roman Bodnarchuk
Roman Bodnarchuk

Reputation: 29717

You messed up with indexes:

>>> a[999999]
('2', '7', '8', '3', '9', '1', '5', '4', '6', '0')

You code quits when generates 1m result. And 1m element in a list has index 999999.

Upvotes: 2

Related Questions