将N个项“合并”为K的算法

我想知道是否有一个已知的算法来执行以下操作，并且还想知道如何在C＃中实现它。 也许这是一种已知类型的问题。

例：

假设我有一堂课

class GoldMine { public int TonsOfGold { get; set; } } 

以及N=3此类项目的List

 var mines = new List() { new GoldMine() { TonsOfGold = 10 }, new GoldMine() { TonsOfGold = 12 }, new GoldMine() { TonsOfGold = 5 } }; 

然后将地雷合并为K=2地雷将是合并

 { {Lines[0],Lines[1]}, {Lines[2]} }, // { 22 tons, 5 tons } { {Lines[0],Lines[2]}, {Lines[1]} }, // { 15 tons, 12 tons } { {Lines[1],Lines[2]}, {Lines[0]} } // { 17 tons, 10 tons } 

并且巩固到K=1矿井将是单一的整合

 { Lines[0],Lines[1],Lines[2] } // { 27 tons } 

我感兴趣的是整合过程的算法。

Answer 1

如果我没有弄错的话，你所描述的问题是所有k的k组合数

我找到了一个代码片段，我相信它可以解决你的用例，但我不记得我从哪里得到它。 它必须来自StackOverflow。 如果有人认出这段特殊的代码，请告诉我，我一定会相信它。

所以这是扩展方法：

 public static class ListExtensions { public static List> GroupCombinations(this List items, int count) { var keys = Enumerable.Range(1, count).ToList(); var indices = new int[items.Count]; var maxIndex = items.Count - 1; var nextIndex = maxIndex; indices[maxIndex] = -1; var groups = new List>(); while (nextIndex >= 0) { indices[nextIndex]++; if (indices[nextIndex] == keys.Count) { indices[nextIndex] = 0; nextIndex--; continue; } nextIndex = maxIndex; if (indices.Distinct().Count() != keys.Count) { continue; } var group = indices.Select((keyIndex, valueIndex) => new { Key = keys[keyIndex], Value = items[valueIndex] }) .ToLookup(x => x.Key, x => x.Value); groups.Add(group); } return groups; } } 

还有一个打印输出的小实用工具方法：

 public void PrintGoldmineCombinations(int count, List mines) { Debug.WriteLine("count = " + count); var groupNumber = 0; foreach (var group in mines.GroupCombinations(count)) { groupNumber++; Debug.WriteLine("group " + groupNumber); foreach (var set in group) { Debug.WriteLine(set.Key + ": " + set.Sum(m => m.TonsOfGold) + " tons of gold"); } } } 

你会像这样使用它：

 var mines = new List { new GoldMine {TonsOfGold = 10}, new GoldMine {TonsOfGold = 12}, new GoldMine {TonsOfGold = 5} }; PrintGoldmineCombinations(1, mines); PrintGoldmineCombinations(2, mines); PrintGoldmineCombinations(3, mines); 

这将产生以下输出：

 count = 1 group 1 1: 27 tons of gold count = 2 group 1 1: 22 tons of gold 2: 5 tons of gold group 2 1: 15 tons of gold 2: 12 tons of gold group 3 1: 10 tons of gold 2: 17 tons of gold group 4 2: 10 tons of gold 1: 17 tons of gold group 5 2: 15 tons of gold 1: 12 tons of gold group 6 2: 22 tons of gold 1: 5 tons of gold count = 3 group 1 1: 10 tons of gold 2: 12 tons of gold 3: 5 tons of gold group 2 1: 10 tons of gold 3: 12 tons of gold 2: 5 tons of gold group 3 2: 10 tons of gold 1: 12 tons of gold 3: 5 tons of gold group 4 2: 10 tons of gold 3: 12 tons of gold 1: 5 tons of gold group 5 3: 10 tons of gold 1: 12 tons of gold 2: 5 tons of gold group 6 3: 10 tons of gold 2: 12 tons of gold 1: 5 tons of gold 

注意：这并没有考虑到集合内容的重复，我不确定你是否真的希望那些被过滤掉。 这是你需要的吗？

编辑

实际上，看你的评论似乎你不想要重复，你也想要包含k的较低值，所以这里是一个小修改，取出重复（以一种非常丑陋的方式，我道歉）并给你每组k的较低值：

 public static List> GroupCombinations(this List items, int count) { var keys = Enumerable.Range(1, count).ToList(); var indices = new int[items.Count]; var maxIndex = items.Count - 1; var nextIndex = maxIndex; indices[maxIndex] = -1; var groups = new List>(); while (nextIndex >= 0) { indices[nextIndex]++; if (indices[nextIndex] == keys.Count) { indices[nextIndex] = 0; nextIndex--; continue; } nextIndex = maxIndex; var group = indices.Select((keyIndex, valueIndex) => new { Key = keys[keyIndex], Value = items[valueIndex] }) .ToLookup(x => x.Key, x => x.Value); if (!groups.Any(existingGroup => group.All(grouping1 => existingGroup.Any(grouping2 => grouping2.Count() == grouping1.Count() && grouping2.All(item => grouping1.Contains(item)))))) { groups.Add(group); } } return groups; } 

它为k = 2产生以下输出：

 group 1 1: 27 tons of gold group 2 1: 22 tons of gold 2: 5 tons of gold group 3 1: 15 tons of gold 2: 12 tons of gold group 4 1: 10 tons of gold 2: 17 tons of gold 

Answer 2

这实际上是枚举一组N个对象的所有K分区的问题，通常被描述为枚举将N个标记对象放入K个未标记框中的方法。

几乎总是这样，解决涉及未标记或无序替代的枚举的问题的最简单方法是创建规范排序，然后弄清楚如何仅生成规范排序的解决方案。 在这种情况下，我们假设对象有一些总排序，以便我们可以通过1和N之间的整数来引用它们，然后我们将对象按顺序放入分区，并按第一个对象的索引对分区进行排序在每一个。 很容易看出这种排序不能产生重复，并且每个分区必须对应于一些规范排序。

然后，我们可以通过N个整数序列表示给定的规范排序，其中每个整数是对应对象的分区的编号。 然而，并非每个N个整数序列都有效; 我们需要约束序列，以便分区按规范顺序排序（按第一个元素的索引排序）。 约束很简单：序列中的每个元素必须是先前出现在序列中的某个整数（放置在已存在的分区中的对象），或者它必须是下一个分区的索引，它比索引的索引多一个最后一个分区已经存在。 综上所述：

• 序列中的第一个条目必须为1（因为第一个对象只能放在第一个分区中）; 和
• 每个后续条目至少为1，并且不超过该点之前的最大条目。
  （如果我们将“第一个条目之前的最大条目”解释为0，则可以合并这两个条件。）
• 这还不够，因为它不会将序列限制为精确的K. 如果我们想要找到所有分区，那就没问题，但如果我们想要所有大小都精确为K的分区，那么我们需要将序列中的最后一个元素约束为K ，这意味着第二个最后一个元素必须至少为K -1，第三个最后一个元素至少为K -2，依此类推，以及不允许任何元素大于K ：
  位置i的元素必须在[max（1， K + i – N ）， K ]范围内

根据如上所述的一组简单约束生成序列可以容易地递归地完成。 我们从一个空序列开始，然后连续添加每个可能的下一个元素，递归调用此过程以填充整个序列。 只要生成可能的下一个元素列表很简单，递归过程就会很简单。 在这种情况下，我们需要三条信息来生成此列表： N ， K和到目前为止生成的最大值。

这导致以下伪代码：

 GenerateAllSequencesHelper(N, K, M, Prefix): if length(Prefix) is N: Prefix is a valid sequence; handle it else: # [See Note 1] for i from max(1, length(Prefix) + 1 + K - N) up to min(M + 1, K): Append i to Prefix GenerateAllSequencesHelper(N, K, max(M, i), Prefix) Pop i off of Prefix GenerateAllSequences(N, K): GenerateAllSequencesHelper(N, K, 0, []) 

由于递归深度对于此过程的任何实际应用都将非常有限，因此递归解决方案应该没问题。 但是，即使不使用堆栈，也可以非常简单地生成迭代解决方案。 这是受约束序列的标准枚举算法的实例：

• 从按字典顺序排列的最小序列开始
• 虽然可能：
  • 向后扫描以找到可以增加的最后一个元素。 （“可能是”意味着增加该元素仍将导致某些有效序列的前缀。）
  • 将该元素增加到下一个可能的最大值
  • 使用尽可能小的后缀填写序列的其余部分。

在迭代算法中，向后扫描可能涉及检查O（N）元素，这显然使其比递归算法慢。 但是，在大多数情况下，它们将具有相同的计算复杂度，因为在递归算法中，每个生成的序列也会产生递归调用和返回它所需的返回的成本。 如果每个（或至少，大多数）递归调用产生多个替代，则递归算法对于每个生成的序列仍然是O（1）。

但是在这种情况下，只要扫描步骤可以在O（1）中执行，迭代算法很可能每个生成的序列也是O（1）; 也就是说，只要它可以在不检查整个序列的情况下执行。

在这种特定情况下，计算直到给定点的序列的最大值不是O（1），但是我们也可以通过维持累积最大值的向量来产生O（1）迭代算法。 （实际上，此向量对应于上面递归过程中的M个参数的堆栈。）

保持M向量很容易; 一旦我们拥有它，我们就可以很容易地识别序列中的“可递增”元素：如果i > 0，则元素i是可递增的， M [ i ]等于M [ i -1]，并且M [ i ]不等于K 。 [笔记2]

笔记

1. 如果我们想要生成所有分区，我们将使用相当简单的替换上面的for循环：

    for i from 1 to M+1: 

2. 这个答案主要基于这个答案 ，但是这个问题要求所有分区; 在这里，您想要生成K分区。 如上所述，算法非常相似。