Algorithm to generate all unique permutations of f

问题:

I'm searching for an algorithm that generates all permutations of fixed-length partitions of an integer. 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 bumbled about with integer partitions + permutations for partitions whose length is lesser than L; but that was too slow because I got the same partition multiple times (because [0, 0, 1] may be a permutation of [0, 0, 1] ;-)

Any help appreciated, and no, this isn't homework -- personal interest :-)

回答1:

Okay. First, forget about the permutations and just generate the partitions of length L (as suggested by @Svein Bringsli). Note that for each partition, you may impose an ordering on the elements, such as >. Now just "count," maintaining your ordering. 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: while subtracting 1 from position i and adding it to the next position maintains our order, subtract 1 from position i, add 1 to position i + 1, and move to the next position. If we're in the last position, step back.

Here's a little python which 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 permutations of each multiset of the list gives you your solution. I won't go into that, there's a recursive algorithm which basically says, for each position, choose each unique element in the multiset and append the permutations of the multiset resulting from removing that element from the multiset.

回答2:

Given that you ask this out of interest, you would probably be interested an authorative answer! It can be found in "7.2.1.2 - Generating all permutations" of Knuth's The Art of Computer Programming (subvolume 4A).

Also, 3 concrete algorithms can be found here.

回答3:

As noted by @pbarranis, the code by @rlibby does not include all lists when n equals k. Below is Python code which does include all lists. This code is non-recursive, which may be more efficient with respect to 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

The lists are created in colexicographic order (algorithm and more description here).

回答4:

Like I mentioned above, I couldn't get @rlibby's code to work for my needs, and I needed code where n=l, so just a subset of your need. Here's my code below, in C#. I know it's not perfectly an answer to the question above, but I believe you'd only have to modify the first method to make it work for different values of l; basically add the same code @rlibby did, making the 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);
    }
}

回答5:

A lot of searching led to this question. Here is an answer that includes the 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
    i.e. 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 instance, all_part(4, 3) as asked by 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]]

回答6:

I found that using a recursive function was not good for larger lengths and integers because it chews up too much RAM, and using a generator / resumable-function (that 'yields' values) was too slow and required a large library to make it cross-platform.

So here's a non-recursive solution in C++ that produces the partitions in sorted order (which is ideal for permutations too). I've found this to be over 10 times faster than seemingly clever and concise recursive solutions I tried for partition lengths of 4 or greater, but for lengths of 1-3 the performance is not necessarily better (and I don't care about short lengths because they're fast with either 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've written DO SOMETHING WITH "partition" HERE. is where you would actually consume the value. (On the last iteration the code will continue to execute the remainder of the loop but I found this to be better than constantly checking for exit conditions - it's optimised for larger 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've used "unsigned short" because I know my length and integer won't exceed certain limits, change that if it's not suitable for you :) Check the comments; one variable there (cur) had to be signed to handle lengths of 1 or 2 and there's a corresponding if-statement that goes with that, and I've also noted in a comment that if your partition vector has signed ints there is another line that can be simplified.

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

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

Nest that in the DO SOMETHING WITH "partition" HERE spot, and you're good to go.

An alternative to finding the compositions (based on the Java code here https://www.nayuki.io/page/next-lexicographical-permutation-algorithm) is as follows. I've found this to perform 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'll notice some undeclared variables there, just declare them earlier in the code before all your do-loops: i, j, pos, and temp (unsigned shorts), and composition (same type and length as partition). You can reuse the declaration of i for it's use in a for-loop in the partitions code snippet. Also note variables like last being used which assume this code is nested within the partitions code given earlier.

Again "Your code goes here" is where you consume the composition for your own 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 the massive increase in speed using these approaches, for any sizeable integers and partition lengths this will still make you mad at your CPU :)