将n个元素分成k个集合的每种组合生成算法

Question

我想生成将小写字母表拆分为两个六个字母和两个七个字母组合的所有不同组合。组合内字母的顺序无关紧要，即如果两个解只在组合内字母的顺序上有所不同，则这些解是相同的。

例如，下面两个解是相同的：

[a,b,c,d,e,f][g,h,i,j,k,l][m,n,o,p,q,r,s][t,u,v,w,x,y,z] [f,b,c,d,e,a][l,h,i,j,k,g][s,n,o,p,q,r,m][z,u,v,w,x,y,t]

一种简单粗暴的方法可能是生成26个字母加2个虚拟字符的全排列，平均分成四组并剔除重复的解（使用数据时忽略虚拟字符）。但这似乎效率不高。我相信已经存在一个众所周知的算法可以解决这个问题，但在茫茫多的类似但不同的排列/组合问题中搜索这个算法让我很困惑。

是否存在一种现有的、命名的算法，可以将nk个元素拆分为n个k个元素的集合，并生成这些集合的每个组合？如果没有，我将不得不自己想办法解决。但这感觉像是已经被解决的问题。

- Duncan Jones

---

这似乎与此相关：https://dev59.com/7UnSa4cB1Zd3GeqPSvhH，尽管我更希望有一个解决此问题的标准算法的参考。 - Duncan Jones

你意识到这些不同组合的数量大约是10的12次方吗？你真的想要它们全部吗？ - Vincent van der Weele

只是出于好奇，您打算如何使用这些组合？很有可能有更好的方法来解决您试图解决的问题。 - StriplingWarrior

@VincentvanderWeele 不，我没有意识到会有那么多！ - Duncan Jones

我确信你可以使用纯逻辑来解决这个问题，而不需要猜测，也不需要查找所有可能的组合。在我的脑海中浮现的是一个加权图，它会随着你输入数据而跟踪字母之间的频率和平均距离。虽然我不是图论领域的专家，但似乎你可以使用2D映射算法根据该信息提出最优位置。 - StriplingWarrior

Answer 1

我不知道这方面的算法名称（尽管可能存在），但我在评论中提到的方法避免了处理重复项，并且是我想象中最有效的方法。

引用： 似乎可以通过反向思考来改进问题：每个字母必须放入四个桶之一，而桶的空间有限，因此递归地尝试将每个字母放入每个具有其所需空间的桶中。这样，您只会生成组合而不是排列。

以下是C#实现。它可以在不到30秒的时间内生成1000万个组合，其中2/3的时间仅用于构建字符串输出：

void Main()
{
    // Tweak these starting values to create smaller subsets if you want.
    var letters = Enumerable.Range(0, 26).Select(i => (char)('a' + i)).ToList();
    var buckets = new[]{new Bucket(6), new Bucket(6), new Bucket(7), new Bucket(7)};
    // I'm only taking 100 values because otherwise this would take a really long time.
    var combos = Combos(letters, 0, buckets).Take(100);
    foreach (var combo in combos)
    {
        Console.WriteLine(combo);
    }
}

public class Bucket : List<char>
{
    public int MaxLoad {get; private set;}
    public Bucket(int capacity) : base(capacity)
    {
        MaxLoad = capacity;
    }
}

// Define other methods and classes here
IEnumerable<string> Combos(IList<char> letters, int currentIndex, Bucket[] buckets)
{
    if(currentIndex == letters.Count){
        yield return string.Join("|", buckets.Select(b => string.Join(",", b)));
        yield break;
    }
    var currentLetter = letters[currentIndex];
    foreach (var bucket in buckets)
    {
        if(bucket.Count < bucket.Capacity)
        {
            bucket.Add(currentLetter);
            foreach (var possibility in Combos(letters, currentIndex + 1, buckets))
            {
                yield return possibility;
            }
            bucket.Remove(currentLetter);
        }
    }
}

样例输出:

a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,r,s|t,u,v,w,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,r,t|s,u,v,w,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,r,u|s,t,v,w,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,r,v|s,t,u,w,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,r,w|s,t,u,v,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,r,x|s,t,u,v,w,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,r,y|s,t,u,v,w,x,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,r,z|s,t,u,v,w,x,y
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,s,t|r,u,v,w,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,s,u|r,t,v,w,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,s,v|r,t,u,w,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,s,w|r,t,u,v,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,s,x|r,t,u,v,w,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,s,y|r,t,u,v,w,x,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,s,z|r,t,u,v,w,x,y
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,t,u|r,s,v,w,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,t,v|r,s,u,w,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,t,w|r,s,u,v,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,t,x|r,s,u,v,w,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,t,y|r,s,u,v,w,x,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,t,z|r,s,u,v,w,x,y
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,u,v|r,s,t,w,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,u,w|r,s,t,v,x,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,u,x|r,s,t,v,w,y,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,u,y|r,s,t,v,w,x,z
a,b,c,d,e,f|g,h,i,j,k,l|m,n,o,p,q,u,z|r,s,t,v,w,x,y
...

我给出的方法有一个很好的特点，就是你可以在结果生成时进行处理--你不需要等待整个列表被生成，也不需要同时在内存中拥有所有的组合。

但请注意，你最终会得到非常多的组合--可能会超过计算机可以在任何合理的时间内生成的数量，无论算法效率如何。例如，如果Vincent的估计为10^12，使用上述代码大约需要一年的时间。你也许可以将其优化到一个月左右。并行化可能会在一台真正强大的计算机上将其缩短到一周。

- StriplingWarrior

---

+1 我很感激你抽出时间编写这个代码。它看起来确实是一个优雅的解决方案。也许对于这个问题没有一个经典算法 - 有很多类似但不同的排列/组合问题，可能许多都没有被解决。我同意这似乎非常高效 - 我喜欢它如何处理不同大小的“桶”。 - Duncan Jones

非常优雅的解决方案。我已经进行了适应，返回一个整数列表，避免了字符串格式化的低效率。 - Jone Polvora

Answer 2

这是一个递归问题。

如果我想要找到长度为n的所有包含某个字母的集合列表，最简单的方法是先考虑那些不包含该字母的长度为n-1的所有集合的列表，然后将每个集合都与[letter]集合连接在一起，以避免重复项，你需要丢弃之前已经完成过的所有元素。

例如，如果我想要在集合[A-F]中找到两个字母组合的数量，答案就是取出每个元素并找到其组合。假设我想要找到所有包含A的组合，那么结果就是[A][B-F]，然后再说我想要找到所有包含B但不包含A的组合，这可以继续写成[B][C-F]。对所有字母a-f都这样做，就可以得到由两个字母A-F组成的所有可能组合，然后这个组合成为三个字母组合的列表尾部。

你需要将a添加到所有不包含A的二字母组合中，然后将b添加到所有不包含a或b的二字母组合中，并继续进行此操作以获取所有三字母组合。

你可以继续使用此算法，直到获得所需长度的元素集合的所有组合。

我知道你不是在寻找代码，但这里有一个C#实现

public IList<string> Combos(IList<string> elements, int level)
    {
        if (level == 1)
        {
            return elements;
        }
        var combinations = new List<string>();
        var previousCombos = Combos(elements, level - 1);
        for (var i = 0; i < elements.Count; i++)
        {
            previousCombos.ToList().ForEach(item =>
            {
                if (!elements.Take(i+1).Any(item.Contains))
                {
                    combinations.Add(item + elements[i]);
                }
            });
        }
        return combinations;
    }

只是提个警告，这个方法非常低效，实际上我认为它是一个指数级算法，所以不要在大数据集或大规模的情况下使用它，否则你的计算将永远持续下去。

- theDarse