Skip to content

Instantly share code, notes, and snippets.

@carl-mastrangelo
Last active July 17, 2022 22:41
Show Gist options
  • Save carl-mastrangelo/908bafc0bac6cfe53ec94bfb24b9243e to your computer and use it in GitHub Desktop.
Save carl-mastrangelo/908bafc0bac6cfe53ec94bfb24b9243e to your computer and use it in GitHub Desktop.
factorial encoder
ordered = ["A", "B", "C", "D", "E", "F"]
def encode_permutation(permutation, ordered):
ordered = ordered.copy()
size = len(ordered)
encoded = 0
for (i, value) in enumerate(permutation):
fact = factorial(size - i - 1)
idx = ordered.index(value)
ordered.remove(value)
encoded += fact * idx
return encoded
def decode_permutation(encoded, ordered):
ordered = ordered.copy()
size = len(ordered)
permutation = []
for i in range(len(ordered)):
divisor = factorial(size - i - 1)
idx = encoded // divisor
permutation.append(ordered[idx])
del ordered[idx]
encoded = encoded % divisor
return permutation
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
for encoded in range(factorial(len(ordered))):
roundtripped = encode_permutation(decode_permutation(encoded, ordered), ordered)
if roundtripped != encoded:
print("bad")
permutation = ["D", "C", "A", "B", "F", "E"]
print("Permutation", permutation)
encoded = encode_permutation(permutation, ordered)
print("Encoded", encoded) # Prints '409'
decoded = decode_permutation(encoded, ordered)
print("Decoded ", decoded)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment