logo标签列表

生成所有固定长度整数分区的唯一排列的算法？

algorithmintegerdata-partitioning
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]的排列；-）任何帮助都将不胜感激，不，这不是作业 - 纯属个人兴趣 :-)
(2, 1, 1) 的排列组合不应该在那个列表里吗？ - user325117
我知道我忘了什么。谢谢，已添加。 - deleted77
3
整数划分的排列称为“组合”。 - user325117
先生成所有有序排列（4,0,0），（3,1,0），（2,2,0），（2,1,1），然后生成它们的所有排列，这样是否会更简单？ - Svein Bringsli
你说顺序不重要，但是你的答案中有条目除了顺序外完全相同。哪一部分是错误的？ - bukzor
6个回答
4

好的。首先，忘记排列，只生成长度为L的分区（如@Svein Bringsli所建议的）。注意，对于每个分区，您可以对元素进行排序，例如>。现在只需“计数”，维护您的排序。对于n = 4，k = 3：

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

那么，如何实现呢？看起来像这样：当从位置i减1并加到下一个位置时，维护了我们的顺序，那么从位置i减1，加1到位置i + 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

现在你有一个列表的列表（实际上是一个多重集合的列表），生成列表中每个多重集合的所有排列就可以得到你的解决方案。我不会详细介绍，但有一个递归算法，基本上是说，对于每个位置，在多重集合中选择每个唯一的元素，并将从该元素中删除的多重集合的排列附加到结果中。
1
我尝试运行这个解决方案，但对于大多数情况它都不起作用；它只适用于n=4和l=3，但其他情况则不行。我需要一个针对n=l子集的算法，而这个算法除了n=2之外，在任何情况下都没有产生(1,1,1,...)的解决方案。我试图让它工作，但最终不得不制作一个全新的解决方案（如下）。 - pbristow
你需要生成该程序输出向量的每个条目的所有排列。 - undefined
3
我发现对于较大的长度和整数，使用递归函数不是一个好的选择，因为它会占用过多的 RAM。使用生成器/可恢复函数（以“yield”值）也太慢了，并且需要一个大型库来使其跨平台。所以这里提供了一个非递归解决方案，用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]);

在这里我写了在这里对“partition”进行操作。是你实际上会使用这个值的地方。(在最后一个迭代中，代码将继续执行循环的其余部分，但我发现这比不断检查退出条件更好，它针对更大的操作进行了优化)

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

噢，我使用了“unsigned short”，因为我知道我的长度和整数不会超过某些限制，如果不适合您，请更改 :) 请检查注释；那里有一个变量（cur）必须是有符号的，以处理长度为1或2的情况，并且与此相对应的if语句也有，我还在注释中指出，如果您的分区向量具有有符号整数，则可以简化另一行。

要获取所有组合，在C ++中，我将使用这个简单的排列策略，它幸运地不会产生任何重复：

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

将其嵌套在此处的"partition"位置，你就可以开始了。

寻找组合的另一种方法（基于此处的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循环之前在代码中声明它们: i、j、pos和temp（无符号短整型），以及composition（与partition相同类型和长度）。在分区代码片段中，可以重复使用i的声明。还要注意像last这样的变量被使用，这假设代码被嵌套在之前给出的分区代码中。
再次提醒，在“Your code goes here”处，您可以根据自己的需要使用这个组合。
以下是我的头文件供参考。
#include <vector> // for std::vector
#include <numeric> // for std::accumulate
#include <algorithm> // for std::next_permutation and std::max
using namespace std;

尽管使用这些方法可以大大提高速度，但对于任何较大的整数和分区长度，这仍然会让您的CPU发疯 :)
3
考虑到您的兴趣，您可能会对权威答案感兴趣！可以在 Knuth 的《计算机程序设计艺术》（4A 子卷）的“7.2.1.2 - 生成所有排列”中找到它。
此外，在这里可以找到3个具体的算法。
听听！如果你喜欢这种问题，那么这个子卷中包含了更多的变化。Knuth提出的解决方案是思维盛宴：非常优雅和聪明。 - Joseph Tanenbaum
2

正如 @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

这些列表按照词典顺序创建（有关算法和更多描述，请参见此处）。

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);
    }
}
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]]
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接