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

Question

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?

Can `permutations` contain more than a list comprehension, so long as it does not rely on any other packages? — Scott Hunter, May 31 '22 at 15:28
Yes, it can contain generators, maps, lambdas, etc., as long as no other packages are used and it can all fit into a single line. — Daniel P, May 31 '22 at 15:30
The idea is to use the restriction of a single line (meaning you can't define / save variables). — Daniel P, May 31 '22 at 15:31
You can use the walrus operator to assign to names within an expression these days... — AKX, May 31 '22 at 15:32
That's part of the challenge! I'm using Python 3.7.7 where the walrus operator doesn't exist. ^^ — Daniel P, May 31 '22 at 15:34
You can extend your "cheaty" method up to N=36 using an alternative base in `int(x,base = b)` — Ben Grossmann, May 31 '22 at 15:39
Also, you can shorten your initial approach to `print([list(str(i)) for i in range(10**N) if set(str(i))==set(range(N))])` — Ben Grossmann, May 31 '22 at 15:48
Actually, I think we would need a [function like this](https://stackoverflow.com/q/2063425/2476977) for what in mind. But we can extend this up to N = 16 without too much trouble — Ben Grossmann, May 31 '22 at 15:52

Michael Szczesny · Accepted Answer · 2022-06-01T00:49:57.867

4

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]]

edited Jun 01 '22 at 00:49

answered May 31 '22 at 16:16

Michael Szczesny

4,911
5
15
32

1

I'm not so sure about simple :) is that a [Y-combinator](https://en.wikipedia.org/wiki/Fixed-point_combinator#Fixed-point_combinators_in_lambda_calculus)? – Ben Grossmann May 31 '22 at 16:22
@BenGrossmann - Yes it is. – Michael Szczesny May 31 '22 at 16:24
This indeed works, so I'll accept your answer! Could you go into a little bit more detail on how it works? – Daniel P May 31 '22 at 22:03
1

Essentially, this is the same solution as [@mrCopiCat's](https://stackoverflow.com/a/72450824/14277722) but uses a functional style pattern called [Y-combinator](https://stackoverflow.com/q/93526/14277722) to achieve recursion with anonymous `lambdas` (without actually using recursion). The `range` `map` was a debugging artefact and is redundant. Please note the update. – Michael Szczesny Jun 01 '22 at 01:07
1

[Here](https://youtu.be/pkCLMl0e_0k?t=10214) is a brief tutorial about this concept. – Michael Szczesny Jun 01 '22 at 01:35

score 2 · Answer 2 · answered May 31 '22 at 15:53

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]]

score 0 · Answer 3 · answered May 31 '22 at 20:21

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

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

3 Answers3