An algorithm for generating all unique permutations of entire sections of a fixed length?

Question

I am looking for an algorithm that generates all permutations of partitions of a fixed integer length. The order does not matter.

For example, for n = 4 and length L = 3:

[(0, 2, 2), (2, 0, 2), (2, 2, 0), (2, 1, 1), (1, 2, 1), (1, 1, 2), (0, 1, 3), (0, 3, 1), (3, 0, 1), (3, 1, 0), (1, 3, 0), (1, 0, 3), (0, 0, 4), (4, 0, 0), (0, 4, 0)] 

I came across whole sections + permutations for sections whose length is less than L; but it was too slow because I got the same section several times (because [0, 0, 1] might be a permutation of [0, 0, 1] ;-)

Any help is appreciated, and no, this is not homework - personal interest :-)

Answer 1

Good. First, forget about permutations and just generate partitions of length L (as suggested by @Svein Bringsli). Note that for each section, you can put an order on elements such as>. Now just “count”, saving your order. For n = 4, k = 3:

 (4, 0, 0) (3, 1, 0) (2, 2, 0) (2, 1, 1) 

So how to implement this? It looks like this: when you subtract 1 from position i and add it to the next position, our order is preserved, subtract 1 from position i, add 1 to position i + 1 and go to the next position. If we are in the last position, lean back.

Here's a little python that does just that:

 def partition_helper(l, i, result): if i == len(l) - 1: return while l[i] - 1 >= l[i + 1] + 1: l[i] -= 1 l[i + 1] += 1 result.append(list(l)) partition_helper(l, i + 1, result) def partition(n, k): l = [n] + [0] * (k - 1) result = [list(l)] partition_helper(l, 0, result) return result 

Now you have a list of lists (really a list of multisets), and generating all the permutations of each multiset of the list gives you your solution. I will not go into this, there is a recursive algorithm, which basically says, for each position, selects each unique element in the multiset and adds permutations of the multiset that result from the removal of this element from the multiset.

Answer 2

Given that you are asking about this out of interest, you will probably be interested in the author's answer! It can be found in the section "7.2.1.2 - Generating All Permutations" by Knut. The Art of Computer Programming ( subvolume 4A ).

In addition, here you can find 3 specific algorithms here .

Answer 3

As @pbarranis noted, @rlibby code does not include all lists when n is k. The following is Python code that includes all lists. This code is not recursive, which may be more efficient regarding memory usage.

 def successor(n, l): idx = [j for j in range(len(l)) if l[j] < l[0]-1] if not idx: return False i = idx[0] l[1:i+1] = [l[i]+1]*(len(l[1:i+1])) l[0] = n - sum(l[1:]) return True def partitions(n, k): l = [0]*k l[0] = n results = [] results.append(list(l)) while successor(n, l): results.append(list(l)) return results 

Lists are created in colexicographic order (algorithm and more detailed description here ).

Answer 4

As I mentioned above, I could not get the @rlibby code to work for my needs, and I need a code where n = l, which means that it is just a subset of your needs. Here is my code below in C #. I know that this is not quite the answer to the question above, but I believe that you only need to change the first method so that it works for different values ​​of l; basically add the same @rlibby code, making an array of length l instead of length n.

 public static List<int[]> GetPartitionPermutations(int n) { int[] l = new int[n]; var results = new List<int[]>(); GeneratePermutations(l, n, n, 0, results); return results; } private static void GeneratePermutations(int[] l, int n, int nMax, int i, List<int[]> results) { if (n == 0) { for (; i < l.Length; ++i) { l[i] = 0; } results.Add(l.ToArray()); return; } for (int cnt = Math.Min(nMax, n); cnt > 0; --cnt) { l[i] = cnt; GeneratePermutations(l, (n - cnt), cnt, i + 1, results); } } 

Answer 5

Many searches led to this issue. Here is an answer that includes permutations:

 #!/usr/bin/python from itertools import combinations_with_replacement as cr def all_partitions(n, k): """ Return all possible combinations that add up to n ie divide n objects in k DISTINCT boxes in all possible ways """ all_part = [] for div in cr(range(n+1), k-1): counts = [div[0]] for i in range(1, k-1): counts.append(div[i] - div[i-1]) counts.append(n-div[-1]) all_part.append(counts) return all_part 

For example, all_part (4, 3) on request of OP gives:

 [[0, 0, 4], [0, 1, 3], [0, 2, 2], [0, 3, 1], [0, 4, 0], [1, 0, 3], [1, 1, 2], [1, 2, 1], [1, 3, 0], [2, 0, 2], [2, 1, 1], [2, 2, 0], [3, 0, 1], [3, 1, 0], [4, 0, 0]] 

Answer 6

I found that using a recursive function is not suitable for long lengths and integers, because it digests too much RAM, and using a generator / renewable function (which gives values) was too slow and required a large library to make it cross-platform.

So, here is a non-recursive solution in C ++ that creates partitions in sorted order (which is also ideal for permutations). I found this to be more than 10 times faster than the seemingly smart and concise recursive solutions that I tried for section lengths of 4 or more, but for lengths 1-3 the performance is not always better (and I don't care about the short length, because they are fast with any approach).

 // Inputs unsigned short myInt = 10; unsigned short len = 3; // Partition variables. vector<unsigned short> partition(len); unsigned short last = len - 1; unsigned short penult = last - 1; short cur = penult; // Can dip into negative value when len is 1 or 2. Can be changed to unsigned if len is always >=3. unsigned short sum = 0; // Prefill partition with 0. fill(partition.begin(), partition.end(), 0); do { // Calculate remainder. partition[last] = max(0, myInt - sum); // Would only need "myInt - sum" if partition vector contains signed ints. /* * * DO SOMETHING WITH "partition" HERE. * */ if (partition[cur + 1] <= partition[cur] + 1) { do { cur--; } while ( cur > 0 && accumulate(partition.cbegin(), partition.cbegin() + cur, 0) + (len - cur) * (partition[cur] + 1) > myInt ); // Escape if seeked behind too far. // I think this if-statement is only useful when len is 1 or 2, can probably be removed if len is always >=3. if (cur < 0) { break; } // Increment the new cur position. sum++; partition[cur]++; // The value in each position must be at least as large as the // value in the previous position. for (unsigned short i = cur + 1; i < last; ++i) { sum = sum - partition[i] + partition[i - 1]; partition[i] = partition[i - 1]; } // Reset cur for next time. cur = penult; } else { sum++; partition[penult]++; } } while (myInt - sum >= partition[penult]); 

Where I wrote DO SOMETHING WITH "partition" HERE. where you actually consume value. (At the last iteration, the code will continue the rest of the loop, but I found it to be better than constantly checking the exit conditions - it is optimized for large operations)

 0,0,10 0,1,9 0,2,8 0,3,7 0,4,6 0,5,5 1,1,8 1,2,7 1,3,6 1,4,5 2,2,6 2,3,5 2,4,4 3,3,4 

Oh, I used "unsigned short" because I know that my length and integer will not exceed certain limits, change this if it does not suit you :) Check the comments; one variable there (cur) had to be signed to handle lengths 1 or 2, and there is a corresponding if-statement that comes with it, and I also noted in the comment that if your section vector has signed ints, there is another line which can be simplified.

To get all the compositions, in C ++ I would use this simple permutation strategy, which, fortunately, does not give duplicates:

 do { // Your code goes here. } while (next_permutation(partition.begin(), partition.end())); 

The socket that is in DO SOMETHING WITH "partition" is HERE and you will go well.

An alternative to finding songs (based on Java code here https://www.nayuki.io/page/next-lexicographical-permutation-algorithm ) is the following. I found this to work better than next_permutation ().

 // Process lexicographic permutations of partition (compositions). composition = partition; do { // Your code goes here. // Find longest non-increasing suffix i = last; while (i > 0 && composition[i - 1] >= composition[i]) { --i; } // Now i is the head index of the suffix // Are we at the last permutation already? if (i <= 0) { break; } // Let array[i - 1] be the pivot // Find rightmost element that exceeds the pivot j = last; while (composition[j] <= composition[i - 1]) --j; // Now the value array[j] will become the new pivot // Assertion: j >= i // Swap the pivot with j temp = composition[i - 1]; composition[i - 1] = composition[j]; composition[j] = temp; // Reverse the suffix j = last; while (i < j) { temp = composition[i]; composition[i] = composition[j]; composition[j] = temp; ++i; --j; } } while (true); 

You will notice some undeclared variables, just declare them earlier in the code before all your do-loops: i , j , pos and temp (unsigned shorts) and composition (the same type and length as the partition ). You can reuse declaration i to use it in a for loop in a section code snippet. Also pay attention to variables of the last type, which assume that this code is nested in the section code specified earlier.

Again, “Your code goes here” is where you consume the composition for your purposes.

For reference, here are my headers.

 #include <vector> // for std::vector #include <numeric> // for std::accumulate #include <algorithm> // for std::next_permutation and std::max using namespace std; 

Despite a significant increase in speed using these approaches, for any significant integers and partition lengths this will still make you crazy on your CPU :)