查找列表的所有子集

Question

我有一个列表,我需要输出列表的每个子集

例如abcde

会输出到

 a
 b
 c  
 d 
 e 
 ab  
 ac  
 ad 
 ae

 abc
 abd 
 abe
 bcd
 bce
 ....
 abcde

我相信正确的术语是组合,任何元素都不应该在同一行上重复

我打算用一系列循环尝试这个,但我甚至不确定我们是否要开始

有什么建议？

Answer 1

这将生成您想要的集合,但是以不同的顺序(我在结尾按字母排序,您也希望按长度排序).

你最终得到:

ab abc abcd abcde abce ... d de e

因此,每个可能的子集(除了空字符串),同时保持原始列表的顺序.

我们的想法是将每个元素添加到不断增长的列表中.对于每个新元素,首先添加它,然后将其添加到所有现有元素.

所以,从'a'开始.

继续'b'.将其添加到列表中.我们现在有{'a','b'}.

将它添加到现有元素,所以我们有'ab'.现在我们有{'a','b','ab'}.

然后'c',并将其添加到现有元素中以获得'ac','bc','abc':{'a','b','ab','c','ac','bc', ABC'}.直到我们完成为止.

        string set = "abcde";

        // Init list
        List<string> subsets = new List<string>();

        // Loop over individual elements
        for (int i = 1; i < set.Length; i++)
        {
            subsets.Add(set[i - 1].ToString());

            List<string> newSubsets = new List<string>();

            // Loop over existing subsets
            for (int j = 0; j < subsets.Count; j++)
            {
                string newSubset = subsets[j] + set[i];
                newSubsets.Add(newSubset);
            }

            subsets.AddRange(newSubsets);
        }

        // Add in the last element
        subsets.Add(set[set.Length - 1].ToString());
        subsets.Sort();

        Console.WriteLine(string.Join(Environment.NewLine, subsets));

Answer 2

如果您只需要原始列表中元素的组合,则可以将问题转换为以下内容:您有一个大小为N的位数组,并且您希望找到数组元素的所有可能选择.例如,如果您的原始列表是

a b c d e

然后你的阵列可以

0 1 0 0 0

这导致输出

b

或阵列可以

1 0 1 1 0

返回

acd

这是一个简单的递归问题,可以在一段O(2^n)时间内解决

编辑为递归算法添加伪代码:

CreateResultSet(List<int> currentResult, int step)
{
    if (the step number is greater than the length of the original list)
    {
        add currentResult to list of all results
        return
    }
    else
    {
        add 0 at the end of currentResult
        call CreateResultSet(currentResult, step+1)

        add 1 at the end of currentResult
        call CreateResultSet(currentResult, step+1)
    }
}

for every item in the list of all results
display the result associated to it (i.e. from 1 0 1 1 0 display acd)