Skip to content

Instantly share code, notes, and snippets.

@brianpursley
Last active December 18, 2022 07:38
Show Gist options
  • Save brianpursley/57bbaf0a8823e51012bc to your computer and use it in GitHub Desktop.
Save brianpursley/57bbaf0a8823e51012bc to your computer and use it in GitHub Desktop.
This is a Python implementation of the QuickPerm algorithm described by Phillip Paul Fuchs at http://www.quickperm.org that generates all permutations of a list without using recursion
#!/usr/bin/env python
#
# This is a Python implementation of the QuickPerm algorithm described by Phillip Paul Fuchs at http://www.quickperm.org
# that generates all permutations of a list without using recursion.
#
a = ['a', 'b', 'c', 'd']
N = len(a)
p = range(0, N + 1)
i = 1
print a
while i < N:
p[i] -= 1
if i % 2 == 1:
j = p[i]
else:
j = 0
a[j], a[i] = a[i], a[j]
print a
i = 1
while p[i] == 0:
p[i] = i
i += 1
@Fate1405
Copy link

thanks pretty epic bro legit 😎

@jackhftang
Copy link

jackhftang commented Apr 6, 2022

A little modification which use only single yield (instead of two prints), so that no duplicated inline codes and look nicer to me.

def quickperm(a):
    N = len(a)
    p = [*range(N+1)]
    i = 1
    while True:
        yield a
        if i >= N: break

        p[i] -= 1
        j = 0 if i % 2 == 0 else p[i]
        a[j], a[i] = a[i], a[j]

        i = 1
        while p[i] == 0:
            p[i] = i
            i += 1

@lydonchandra
Copy link

does anyone have a parallel version of this, eg. using 2 or more cores ?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment