All permutations of numbers 1...N using list comprehension (without itertools)

user_10871632 0
Viewed 167

I am currently using Python 3.7.7, and I posed a coding challenge for myself.

I would like to list all permutations of integers from 1 to N using a one-line code (perhaps a list comprehension). I cannot use itertools (or other packages which solve this with one function).

For N <= 9, I found "cheaty" method:

N = 3
print([list(str(i)) for i in range(10**N) if all([str(i).count(str(j)) == 1 for j in range(1,N+1)])])

Example:

Out: [['1', '2', '3'], ['1', '3', '2'], ['2', '1', '3'], ['2', '3', '1'], ['3', '1', '2'], ['3', '2', '1']]

In the case of N = 3, this goes through all integers from 0 to 999 in order, and selects the ones that have exactly one 1, exactly one 2, and exactly one 3. (These are 123, 132, 213, 231, 312, 321; and from here, it's simple enough to convert them to a list.)

However this obviously fails for N >= 10.

I thought about converting the numbers to a higher base first, but that turned out to be even more difficult when restricting myself to only using list comprehension.

Can anyone think of a way to do this for N >= 10?

permutation list-comprehension python
3 Answers

A not-so-simple functional one-liner without any "outside" variable assignment except N.

N = 3
(lambda n: (lambda f, n: f(f, n))(lambda f, n: [p[:i]+[n]+p[i:] for p in f(f, n-1) for i in range(len(p)+1)] if n > 1 else [[1]], n))(N)

Output

[[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]]
user_142777220

I tried to use recursion here, and it apparently works:

def perm(n):
    return [p[:i] + [n] + p[i:]  for p in perm(n-1) for i in range(0,len(p)+1)] if n > 2 else [[2,1], [1,2]]

print(perm(4))

output:

[[4, 3, 2, 1], [3, 4, 2, 1], [3, 2, 4, 1], [3, 2, 1, 4], [4, 2, 3, 1], [2, 4, 3, 1], [2, 3, 4, 1], [2, 3, 1, 4], [4, 2, 1, 3], [2, 4, 1, 3], [2, 1, 4, 3], [2, 1, 3, 4], [4, 3, 1, 2], [3, 4, 1, 2], [3, 1, 4, 2], [3, 1, 2, 4], [4, 1, 3, 2], [1, 4, 3, 2], [1, 3, 4, 2], [1, 3, 2, 4], [4, 1, 2, 3], [1, 4, 2, 3], [1, 2, 4, 3], [1, 2, 3, 4]]
user_155829110

For no good reason, here is an implementation of your approach in base 16, which means that this method works for N<=15.

N = 3
print([[
dict(zip([*map(str,range(10)),*'abcdef'],
         map(str,range(16))))[c] 
    for c in f'{i:x}'] 
    for i in range(16**N) 
    if set(f'{i:x}') == set('1234567890abcdef'[:N])])
user_24769770
Related