获取集合的所有子集

Question

我正在尝试创建一个方法来返回一个集合的所有子集。

例如，如果我有收藏，10,20,30 我想获得以下输出

        return new List<List<int>>()
        {
            new List<int>(){10},
            new List<int>(){20},
            new List<int>(){30},
            new List<int>(){10,20},
            new List<int>(){10,30},
            new List<int>(){20,30},
            //new List<int>(){20,10}, that substet already exists
            // new List<int>(){30,20}, that subset already exists
            new List<int>(){10,20,30}
        };

因为集合也可以是字符串的集合，例如我想创建一个通用方法。这是我根据这个解决方案制定的。

    static void Main(string[] args)
    {
        Foo<int>(new int[] { 10, 20, 30});
    }

    static List<List<T>> Foo<T>(T[] set)
    {

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

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

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

            // Loop over existing subsets
            for (int j = 0; j < subsets.Count; j++)
            {
                var tempList = new List<T>();
                tempList.Add(subsets[j][0]);
                tempList.Add(subsets[i][0]);
                var newSubset = tempList;
                newSubsets.Add(newSubset);
            }

            subsets.AddRange(newSubsets);
        }

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

        //Console.WriteLine(string.Join(Environment.NewLine, subsets));
        return null;
    }

---

编辑

对不起，这是错误的，我仍然得到重复...

    static List<List<T>> GetSubsets<T>(IEnumerable<T> Set)
    {
        var set = Set.ToList<T>();

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

        subsets.Add(new List<T>()); // add the empty set

        // Loop over individual elements
        for (int i = 1; i < set.Count; i++)
        {
            subsets.Add(new List<T>(){set[i - 1]});

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

            // Loop over existing subsets
            for (int j = 0; j < subsets.Count; j++)
            {
                var newSubset = new List<T>();
                foreach(var temp in subsets[j])
                    newSubset.Add(temp);

                newSubset.Add(set[i]);


                newSubsets.Add(newSubset);
            }

            subsets.AddRange(newSubsets);
        }

        // Add in the last element
        subsets.Add(new List<T>(){set[set.Count - 1]});
        //subsets.Sort();

        return subsets;
    }

然后我可以调用该方法为：

Answer 1

这是一个基本算法，我使用以下技术来制作单人拼字游戏（报纸上的）。

让你的集合有n元素。增加一个从 0 到 的整数2^n。对于每个生成器编号位掩码，整数的每个位置。如果i整数的第 th 个位置是，1则选择i集合的第 th 个元素。对于从0到的每个生成的整数，2^n执行上述 bitmasting 和选择将为您提供所有子集。

这是一个帖子：http : //phoxis.org/2009/10/13/allcombgen/

Answer 2

这是对 Marvin Mendes 在此答案中提供的代码的改编，但重构为具有迭代器块的单个方法。

public static IEnumerable<IEnumerable<T>> Subsets<T>(IEnumerable<T> source)
{
    List<T> list = source.ToList();
    int length = list.Count;
    int max = (int)Math.Pow(2, list.Count);

    for (int count = 0; count < max; count++)
    {
        List<T> subset = new List<T>();
        uint rs = 0;
        while (rs < length)
        {
            if ((count & (1u << (int)rs)) > 0)
            {
                subset.Add(list[(int)rs]);
            }
            rs++;
        }
        yield return subset;
    }
}