7

我正在寻找一种生成整数固定长度分区的所有排列的算法。顺序无所谓。

例如,对于 n=4 和长度 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)]

我对整数分区 + 长度小于 L 的分区的排列感到困惑;但这太慢了,因为我多次获得相同的分区(因为[0, 0, 1]可能是[0, 0, 1];-)

任何帮助表示赞赏,不,这不是家庭作业——个人兴趣:-)

4

6 回答 6

3

正如@pbarranis 所指出的,@rlibby 的代码在n等于k​​时不包括所有列表。下面是包含所有列表的 Python 代码。此代码是非递归的,这在内存使用方面可能更有效。

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

列表是按字典顺序创建的(算法和更多描述在这里)。

于 2013-02-04T19:19:59.660 回答
3

鉴于您出于兴趣提出此问题,您可能会对权威答案感兴趣!它可以在 Knuth 的计算机编程艺术(第4A分卷)的“7.2.1.2 - 生成所有排列”中找到。

此外,可以在此处找到 3 个具体算法。

于 2011-04-06T01:15:56.850 回答
3

好的。首先,忘记排列,只生成长度为 L 的分区(如@Svein Bringsli 所建议的那样)。请注意,对于每个分区,您可以对元素进行排序,例如 >。现在只需“计数”即可维持您的订单。对于 n = 4,k = 3:

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

那么,如何实现呢?它看起来像:从位置 i 减去 1 并将其添加到下一个位置保持我们的顺序,从位置 i 减去 1,在位置 i + 1 上加 1,然后移动到下一个位置。如果我们处于最后一个位置,请退后一步。

这是一个小python,它就是这样做的:

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

现在您有一个列表列表(实际上是一个多集列表),并且生成列表的每个多集的所有排列可以为您提供解决方案。我不会深入讨论,有一个递归算法,它基本上说,对于每个位置,选择多重集中的每个唯一元素,并附加从多重集中删除该元素所产生的多重集的排列。

于 2011-02-05T10:14:04.903 回答
2

我发现使用递归函数对于更大的长度和整数并不好,因为它会消耗太多的 RAM,并且使用生成器/可恢复函数(即“产生”值)太慢并且需要一个大型库来使其交叉-平台。

所以这里有一个 C++ 中的非递归解决方案,它按排序顺序生成分区(这也是排列的理想选择)。我发现这比我为 4 或更大的分区长度尝试的看似聪明和简洁的递归解决方案快 10 倍以上,但对于 1-3 的长度,性能不一定更好(而且我不关心短长度,因为它们对任何一种方法都很快)。

// 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]);

我在这里写了用“分区”做一些事情的地方。是您实际消耗价值的地方。(在最后一次迭代中,代码将继续执行循环的其余部分,但我发现这比不断检查退出条件要好——它针对更大的操作进行了优化)

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

哦,我使用了“无符号短”,因为我知道我的长度和整数不会超过某些限制,如果它不适合你,请更改它:) 检查评论;必须对那里的一个变量(cur)进行签名以处理 1 或 2 的长度,并且有一个相应的 if 语句与之相伴,我还在评论中指出,如果您的分区向量已签名整数,则还有另一行可以简化。

为了得到所有的组合,在 C++ 中我会使用这个简单的排列策略,幸运的是它不会产生任何重复:

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

将它嵌套在DO SOMETHING WITH “partition” HERE点中,你就可以开始了。

查找组合的替代方法(基于此处的 Java 代码https://www.nayuki.io/page/next-lexicographical-permutation-algorithm)如下。我发现这比 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);

您会注意到那里有一些未声明的变量,只需在代码中的所有 do-loop 之前声明它们:ijpostemp(无符号短裤)和composition(与 相同的类型和长度partition)。您可以i在分区代码片段的 for 循环中重用 for 的声明。还要注意像正在使用的变量last,它假定此代码嵌套在前面给出的分区代码中。

同样,“您的代码在此处”是您出于自己的目的使用该组合物的地方。

供参考这里是我的标题。

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

尽管使用这些方法大大提高了速度,但对于任何相当大的整数和分区长度,这仍然会让你对你的 CPU 生气:)

于 2017-07-12T17:40:33.377 回答
0

就像我上面提到的,我无法让@rlibby 的代码满足我的需要,我需要 n=l 的代码,所以只是你需要的一个子集。下面是我的 C# 代码。我知道这不是上述问题的完美答案,但我相信您只需要修改第一种方法即可使其适用于不同的 l 值;基本上添加了与@rlibby 相同的代码,使数组长度为 l 而不是长度为 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);
    }
}
于 2012-07-02T12:42:52.773 回答
0

大量搜索导致了这个问题。这是一个包含排列的答案:

#!/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

例如,OP 要求的 all_part(4, 3) 给出:

[[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]]
于 2016-12-20T11:07:14.060 回答