计算一个字符串的所有可能组合

  • Z时代
  • 2024-01-10
  • 分类：问答

我试图允许用户在文本框中输入文本，并让程序生成所有可能的组合，但最少3个字符，最多6个字符。我不需要“ as”之类的无用字，

‘a’，’i’，’to’等使我的数组混乱。我还将对照字典检查每个组合，以确保它是一个真实的单词。

我有完整的字典（经过精心制作，这是它的返回链接（警告：（对我来说）巨大的加载时间！）

无论如何，如果用户输入“ ABCDEF”（无特定顺序），我将如何生成，例如：

'ABC'
'BAC'
'CAB'
...
'ABD'
'ABE'
'ABF'

等等…每种可能的组合，无论顺序如何？我知道这些组合的数量非常可笑，但是只需要计算一次，因此我对此并不担心。

我发现代码示例可以递归地找到固定宽度字符串（ABCDEF，ABCDFE …

ACDBFE等）的组合（不是排列，我不需要那些）。他们没有做我需要的事情，而且我对从哪里开始这个项目一无所知。

这不是家庭作业，它最初是我的一个个人项目，逐渐发展成为接管我这个简单问题的生活……我不敢相信我无法弄清楚！

回答：

在我看来，您正在描述电源套件

这是我在我的个人库中的一个实现：

// Helper method to count set bits in an integer
public static int CountBits(int n)
{
    int count = 0;
    while (n != 0)
    {
        count++;
        n &= (n - 1);
    }
    return count;
}
public static IEnumerable<IEnumerable<T>> PowerSet<T>(
    IEnumerable<T> src, 
    int minSetSize = 0, 
    int maxSetSize = int.MaxValue)
{
    // we want fast random access to the source, so we'll
    // need to ToArray() it
    var cached = src.ToArray();
    var setSize = Math.Pow(2, cached.Length);
    for(int i=0; i < setSize; i++)
    {
        var subSetSize = CountBits(i);
        if(subSetSize < minSetSize || 
           subSetSize > maxSetSize)
        {
            continue;
        }
        T[] set = new T[subSetSize];
        var temp = i;
        var srcIdx = 0;
        var dstIdx = 0;
        while(temp > 0)
        {
            if((temp & 0x01) == 1)
            {
                set[dstIdx++] = cached[srcIdx];
            }
            temp >>= 1;
            srcIdx++;            
        }
        yield return set;
    }
    yield break;
}

和一个快速测试平台：

void Main()
{
    var src = "ABCDEF";
    var combos = PowerSet(src, 3, 6);
    // hairy joins for great prettiness
    Console.WriteLine(
        string.Join(" , ", 
            combos.Select(subset => 
                string.Concat("[", 
                    string.Join(",", subset) , "]")))
    );
}

输出：

[A,B,C] , [A,B,D] , [A,C,D] , [B,C,D] , [A,B,C,D] , [A,B,E] , [A,C,E] , [B,C,E] , [A,B,C,E] , 
[A,D,E] , [B,D,E] , [A,B,D,E] , [C,D,E] , [A,C,D,E] , [B,C,D,E] , [A,B,C,D,E] , [A,B,F] , 
[A,C,F] , [B,C,F] , [A,B,C,F] , [A,D,F] , [B,D,F] , [A,B,D,F] , [C,D,F] , [A,C,D,F] , 
[B,C,D,F] , [A,B,C,D,F] , [A,E,F] , [B,E,F] , [A,B,E,F] , [C,E,F] , [A,C,E,F] , [B,C,E,F] , 
[A,B,C,E,F] , [D,E,F] , [A,D,E,F] , [B,D,E,F] , [A,B,D,E,F] , [C,D,E,F] , [A,C,D,E,F] , 
[B,C,D,E,F] , [A,B,C,D,E,F]

以上是 计算一个字符串的所有可能组合 的全部内容， 来源链接： utcz.com/qa/412802.html

回到顶部