Skip to content

Instantly share code, notes, and snippets.

@jackhftang
Created April 6, 2022 06:56
Show Gist options
  • Save jackhftang/cea4567a0a969930b33e9ae2970050d2 to your computer and use it in GitHub Desktop.
Save jackhftang/cea4567a0a969930b33e9ae2970050d2 to your computer and use it in GitHub Desktop.
single yield, fast inner loop version
def permutations(lis):
N = len(lis)
i = 0
c = [*range(0, max(2,N+1))]
while True:
yield lis
i = 1
while c[i] == 0:
c[i] = i
i += 1
if i >= N: break
c[i] -= 1
k = 0 if i % 2 == 0 else c[i]
lis[k], lis[i] = lis[i], lis[k]
for l in range(9):
lis = [i for i in range(l)]
s = set()
for x in permutations(lis):
# all permutation must be of length l
assert len(x) == l
# all permutation must be unique
radix = [True] * l
for i in x:
assert radix[i]
radix[i] = False
# all permutation must be unique
hash = sum([x[i] * l**i for i in range(l)])
assert hash not in s
s.add(hash)
# exactly l! number of permutations
assert len(s) == factorial(l)
print(l, len(s))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment