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ます。各ジェネレーター番号のビットマスクに対して、整数の各位置。整数のith 位置が である場合は、セットの th 要素を1選択します。iから生成された整数ごとに、上記のビットマスティングと選択を実行すると、すべてのサブセットが取得されます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 sugest として、インターレータ ブロックを使用して実装を追加し、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 に答える
0

リストのセットを返すのではなく、Java のセット タイプを使用します。Set は、各タイプの一意の要素を 1 つだけ保持することで、探しているものの一部を既に実行しています。したがって、たとえば 20 を 2 回追加することはできません。これは順序付けられていない型なので、一連のセットを作成する組み合わせ関数を作成し、それらの連想リストを含むリストを返すことができます。

于 2012-04-29T17:54:53.557 に答える