3

I'm looking for an algorithm to generate or iterate through all permutations of a list of objects such that:

  1. They are generated by fewest to least positional changes from the original. So first all the permutations with a single pair of elements swapped, then all the permutations with only two pairs of elements swapped, etc.
  2. The list generated is complete, so for n objects in a list there should be n! total, unique permutations.
  3. Ideally (but not necessarily) there should be a way of specifying (and generating) a particular permutation without having to generate the full list first and then reference the index.
  4. The speed of the algorithm is not particularly important.

I've looked through all the permutation algorithms that I can find, and none so far have met criteria 1 and 2, let alone 3.

I have an idea how I could write this algorithm myself using recursion, and filtering for duplicates to only get unique permutations. However, if there is any existing algorithm I'd much rather use something proven.

Improve this question
7
  • I propose the following steps: 1) Write an algorithm to generate all subsets of a given size. 2) Write an algorithm to generate all derangements of a set; 3) Write a function that, given a derangement of a subset of the list, completes this derangement of the sublist into the corresponding permutation of the full list. 4) Combine all these steps together to get your algorithm. Commented Jan 12, 2023 at 14:39
  • As for your "generate the Nth permutation directly" requirement, most permutations can be skipped by comparing N with the number of subsets of a given size (n choose k) and the number of derangements of a set of size k (see Wikipedia: Counting derangements or sympy.subfactorial). For instance, find the largest K such that sum_{k=0}^K (n choose k) subfactorial(k) ⩽ N. This K is the number of elements that should be changed by the permutation. Commented Jan 12, 2023 at 14:48
  • @Stef: that is one way of going about it, but if n is large (say > 13), the memory and time needed to do this would be considerable unless I'm missing something. Commented Jan 12, 2023 at 16:11
  • The time would of course be at least proportional to the length of the output. Yes, the length of the output goes up exponentially, but that's the output you're asking for. As for memory, the memory used by the algorithm would be proportional to n, but the memory of the output would of course be exponential in n. Again, that's what you're asking for. Commented Jan 12, 2023 at 16:39
  • 1
    Reminds me of Cycle sort, except instead of sorting, one needs to output all the permutations. Commented Jan 12, 2023 at 17:44

3 Answers 3

Reset to default
1

This code answers your requirement #3, which is to compute permutation at index N directly.

This code relies on the following principle:

The first permutation is the identity; then the next (n choose 2) permutations just swap two elements; then the next (n choose 3)(subfactorial(3)) permutations derange 3 elements; then the next (n choose 4)(subfactorial(4)) permutations derange 4 elements; etc. To find the Nth permutation, first figure out how many elements it deranges by finding the largest K such that sum[k = 0 ^ K] (n choose k) subfactorial(k) ⩽ N.

This number K is found by function number_of_derangements_for_permutation_at_index in the code.

Then, the relevant subset of indices which must be deranged is computed efficiently using more_itertools.nth_combination.

However, I didn't have a function nth_derangement to find the relevant derangement of the deranged subset of indices. Hence the last step of the algorithm, which computes this derangement, could be optimised if there exists an efficient function to find the nth derangement of a sequence efficiently.

As a result, this last step takes time proportional to idx_r, where idx_r is the index of the derangement, a number between 0 and factorial(k), where k is the number of elements which are deranged by the returned permutation.

from sympy import subfactorial from math import comb from itertools import count, accumulate, pairwise, permutations from more_itertools import nth_combination, nth def number_of_derangements_for_permutation_at_index(n, idx): #n = len(seq) for k, (low_acc, high_acc) in enumerate(pairwise(accumulate((comb(n,k) * subfactorial(k) for k in count(2)), initial=1)), start=2): if low_acc <= idx < high_acc: return k, low_acc def is_derangement(seq, perm): return all(i != j for i,j in zip(seq, perm)) def lift_permutation(seq, deranged, permutation): result = list(seq) for i,j in zip(deranged, permutation): result[i] = seq[j] return result # THIS FUNCTION NOT EFFICIENT def nth_derangement(seq, idx): return nth((p for p in permutations(seq) if is_derangement(seq, p)), idx) def nth_permutation(seq, idx): if idx == 0: return list(seq) n = len(seq) k, acc = number_of_derangements_for_permutation_at_index(n, idx) idx_q, idx_r = divmod(idx - acc, subfactorial(k)) deranged = nth_combination(range(n), k, idx_q) derangement = nth_derangement(deranged, idx_r) # TODO: FIND EFFICIENT VERSION return lift_permutation(seq, deranged, derangement)

Testing for correctness on small data:

print( [''.join(nth_permutation('abcd', i)) for i in range(24)] ) # ['abcd', # 'bacd', 'cbad', 'dbca', 'acbd', 'adcb', 'abdc', # 'bcad', 'cabd', 'bdca', 'dacb', 'cbda', 'dbac', 'acdb', 'adbc', # 'badc', 'bcda', 'bdac', 'cadb', 'cdab', 'cdba', 'dabc', 'dcab', 'dcba']

Testing for speed on medium data:

from math import factorial seq = 'abcdefghij' n = len(seq) # 10 N = factorial(n) // 2 # 1814400 perm = ''.join(nth_permutation(seq, N)) print(perm) # fcjdibaehg
Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Thank you for the effort in answering the question so thoroughly. It looks really promising, and I'll definitely try it out this weekend.
@JohnGB Unfortunately, function nth_derangement is hopelessly inefficient, so this code practically only works for sequences up to length 12. There should be a way to rewrite the function nth_derangement more efficiently but that's far from trivial.
Actually it shouldn't be so hard to come up with a way to make an nth_derangement function...
@JohnGB I think the easiest way to write nth_derangement directly would be inspired by the recursive formula given in Wikipedia: Counting derangements. Another way is to count the cycles, inspired by the answer to: How to directly generate permutations without fixed points?
I ended up writing a package based on the Fischer Yates shuffle, which is surprisingly fast and memory efficient as I can process the iterations one at a time while stepping through the shuffle as well as return to a given shuffle position quite easily to save and continue progress.
|
1

Imagine a graph with n! nodes labeled with every permutation of n elements. If we add edges to this graph such that nodes which can be obtained by swapping one pair of elements are connected, an answer to your problem is obtained by doing a breadth-first search from whatever node you like.

You can actually generate the graph or just let it be implied and just deduce at each stage what nodes should be adjacent (and of course, keep track of ones you've already visited, to avoid revisiting them).

I concede this probably doesn't help with point 3, but maybe is a viable strategy for getting points 1 and 2 answered.

Improve this answer

2 Comments

The only issue there is that many duplicate elements will be generated. This is essentially the plan that I have to write myself, but it will involve generating the full set and removing duplicates, which could be problematic with n > 13.
To avoid duplicates you could put the ones you've found in a hash set or something, then when you propose new ones, check the hash set first.
0

To solve 1 & 2, you could first generate all possible permutations, keeping track of how many swaps occurred during generation for each list. Then sort them by number of swaps. Which I think is O(n! + nlgn) = O(n!)

Improve this answer

1 Comment

Only one would have to also keep track of how many times an element had already been swapped, as it's possible to swap elements which could have already been swapped.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.