5

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

例如，如果我有集合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;
    }

然后我可以将该方法称为：

在此处输入图像描述

4

7 回答 7

6

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

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

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

于 2012-04-29T17:58:13.487 回答
5

这是对 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;
    }
}
于 2013-02-11T21:16:49.020 回答
2

我知道这个问题有点老了，但我一直在寻找答案，但在这里找不到任何好处，所以我想分享这个解决方案，它是在这个博客中找到的改编版：http: //praseedp.blogspot.com.br /2010/02/subset-generation-in-c.html

我只将类转换为泛型类：

public class SubSet<T>
{
    private IList<T> _list;
    private int _length;
    private int _max;
    private int _count;

    public SubSet(IList<T> list)
    {
        if (list== null)
            throw new ArgumentNullException("lista");
        _list = list;
        _length = _list.Count;
        _count = 0;
        _max = (int)Math.Pow(2, _length);
    }


    public IList<T> Next()
    {
        if (_count == _max)
        {
            return null;
        }
        uint rs = 0;

        IList<T> l = new List<T>();            

        while (rs < _length)
        {
            if ((_count & (1u << (int)rs)) > 0)
            {
                l.Add(_list[(int)rs]);                    
            }
            rs++;
        }
        _count++;
        return l;            
    }
}

要使用此代码，您可以执行以下操作：

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

        lst.AddRange(new string[] {"A", "B", "C" });

        SubSet<string> subs = new SubSet<string>(lst);

        IList<string> l = subs.Next();

        while (l != null)
        {

            DoSomething(l);
            l = subs.Next();
        }

请记住：此代码仍然是 O(2^n)，如果您在列表中传递类似 20 个元素的内容，您将获得 2^20= 1048576 个子集！

编辑：正如 Servy 所建议的，我添加了一个带有 interator 块的实现以与 Linq 和 foreach 一起使用，新类是这样的：

private class SubSet<T> : IEnumerable<IEnumerable<T>>
    {
        private IList<T> _list;
        private int _length;
        private int _max;
        private int _count;

        public SubSet(IEnumerable<T> list)
        {
            if (list == null)
                throw new ArgumentNullException("list");
            _list = new List<T>(list);
            _length = _list.Count;
            _count = 0;
            _max = (int)Math.Pow(2, _length);
        }

        public int Count
        {
            get { return _max; }
        }



        private IList<T> Next()
        {
            if (_count == _max)
            {
                return null;
            }
            uint rs = 0;

            IList<T> l = new List<T>();

            while (rs < _length)
            {
                if ((_count & (1u << (int)rs)) > 0)
                {
                    l.Add(_list[(int)rs]);
                }
                rs++;
            }
            _count++;
            return l;
        }

        public IEnumerator<IEnumerable<T>> GetEnumerator()
        {
            IList<T> subset;
            while ((subset = Next()) != null)
            {
                yield return subset;
            }
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
    }

你现在可以像这样使用它：

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

        lst.AddRange(new string[] {"A", "B", "C" });

        SubSet<string> subs = new SubSet<string>(lst);

        foreach(IList<string> l in subs)
        {
            DoSomething(l);
        }

感谢Servy的建议。

于 2013-02-11T18:47:28.363 回答
1

它不给出重复值；

不要在子集的开头添加 int 数组的值

正确的程序如下：

class Program
    {
        static HashSet<List<int>> SubsetMaker(int[] a, int sum)
        {
            var set = a.ToList<int>();
            HashSet<List<int>> subsets = new HashSet<List<int>>();
            subsets.Add(new List<int>());
            for (int i =0;i<set.Count;i++)
            {
                //subsets.Add(new List<int>() { set[i]});
                HashSet<List<int>> newSubsets = new HashSet<List<int>>();
                for (int j = 0; j < subsets.Count; j++)
                {
                   var newSubset = new List<int>();
                   foreach (var temp in subsets.ElementAt(j))
                   {
                      newSubset.Add(temp);


                    }
                    newSubset.Add(set[i]);
                    newSubsets.Add(newSubset);

                }
                Console.WriteLine("New Subset");
                foreach (var t in newSubsets)
                {
                    var temp = string.Join<int>(",", t);
                    temp = "{" + temp + "}";
                    Console.WriteLine(temp);
                }
                Console.ReadLine();

                subsets.UnionWith(newSubsets);
            }
            //subsets.Add(new List<int>() { set[set.Count - 1] });
            //subsets=subsets.;
            return subsets;

        }
        static void Main(string[] args)
        {
            int[] b = new int[] { 1,2,3 };
            int suma = 6;
            var test = SubsetMaker(b, suma);
            Console.WriteLine("Printing final set...");
            foreach (var t in test)
            {
                var temp = string.Join<int>(",", t);
                temp = "{" + temp + "}";
                Console.WriteLine(temp);
            }
            Console.ReadLine();

        }
    }
于 2019-03-26T03:35:11.893 回答
0

你不想返回一组列表，你想使用 java 的 set 类型。Set 已经通过只保存每种类型的一个独特元素来完成您正在寻找的部分工作。因此，例如，您不能两次添加 20。它是一种无序类型，因此您可以编写一个组合函数来创建一堆集合，然后返回一个包含这些集合的列表。

于 2012-04-29T17:54:53.557 回答
0

获取特定子集长度的集合的所有子集：

    public static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length) where T : IComparable
    {
        if (length == 1) return list.Select(t => new T[] { t });
        return GetPermutations(list, length - 1).SelectMany(t => list.Where(e => t.All(g => g.CompareTo(e) != 0)), (t1, t2) => t1.Concat(new T[] { t2 }));
    }

    public static IEnumerable<IEnumerable<T>> GetOrderedSubSets<T>(IEnumerable<T> list, int length) where T : IComparable
    {
        if (length == 1) return list.Select(t => new T[] { t });
        return GetOrderedSubSets(list, length - 1).SelectMany(t => list.Where(e => t.All(g => g.CompareTo(e) == -1)), (t1, t2) => t1.Concat(new T[] { t2 }));
    }

测试代码：

        List<int> set = new List<int> { 1, 2, 3 };
        foreach (var x in GetPermutations(set, 3))
        {
            Console.WriteLine(string.Join(", ", x));
        }
        Console.WriteLine();
        foreach (var x in GetPermutations(set, 2))
        {
            Console.WriteLine(string.Join(", ", x));
        }
        Console.WriteLine();
        foreach (var x in GetOrderedSubSets(set, 2))
        {
            Console.WriteLine(string.Join(", ", x));
        }

测试结果：

1, 2, 3
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1

1, 2
1, 3
2, 1
2, 3
3, 1
3, 2

1, 2
1, 3
2, 3
于 2018-06-03T09:29:02.797 回答
0

基于递归的简单算法：

private static List<List<int>> GetPowerList(List<int> a)
    {
        int n = a.Count;
        var sublists = new List<List<int>>() { new List<int>() };
        for (int i = 0; i < n; i++)
        {
            for (int j = i; j < n; j++)
            {
                var first = a[i];
                var last = a[j];
                if ((j - i) > 1)
                {
                    sublists.AddRange(GetPowerList(a
                        .GetRange(i + 1, j - i - 1))
                        .Select(l => l
                        .Prepend(first)
                        .Append(last).ToList()));
                }
                else sublists.Add(a.GetRange(i,j - i + 1));
            }
        }
        return sublists;
    }
于 2020-06-17T21:24:34.300 回答