Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # https://oeis.org/A280318
- # listing the permutations generated by Heap's algorithm as their reverse colexicographic index numbers
- # _heap_perm_ comes from http://stackoverflow.com/questions/29042819/heaps-algorithm-permutation-generator
- from itertools import permutations
- from bidict import bidict
- from math import factorial
- n = 7
- # generate n-element permutations in reverse colexicographic order
- perms_iter = permutations(list(range(n)))
- perms_revcolex_bidict = bidict()
- for i, perm in enumerate(perms_iter):
- perms_revcolex_bidict[factorial(n)-1-i] = tuple(perm[::-1]) # create reverse colexicographic order
- # generate n-element permutations in Heap order
- def _heap_perm_(n, A):
- if n == 1: yield A
- else:
- for i in range(n-1):
- for hp in _heap_perm_(n-1, A): yield hp
- j = 0 if (n % 2) == 1 else i
- A[j],A[n-1] = A[n-1],A[j]
- for hp in _heap_perm_(n-1, A): yield hp
- heap_generator = _heap_perm_(n, list(range(n)))
- perms_heap = {}
- for i, perm in enumerate(heap_generator):
- perms_heap[i] = tuple(perm)
- # assign rev colex index numbers to permutations
- heap_numbers = []
- for i in range(factorial(n)):
- perm = perms_heap[i]
- heap_number = perms_revcolex_bidict.inv[perm]
- heap_numbers.append(heap_number)
- print(heap_numbers)
- b_file_text = ''
- for i, e in enumerate(heap_numbers):
- b_file_text += '%s %s\n' % (i, e)
- b_file = open('b_file', 'w')
- b_file.write(b_file_text)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement