1

この問題を解決しようとして、金曜日のほとんどを失いました。

整数のコレクションから一意の順序付けられていないセットのリストを生成します。

[要素が元のコレクションで繰り返される場合、セットを構築する目的で 2 つの別個の要素と見なされます]

私は最終的に次のようになりました。これにより、正しい結果が得られます。もっと効率の良い方法がないか考え中です。

特に、私の Shift() メソッドは、より効率的な形式でどこかに存在する必要があります。私はビット単位の操作にあまり詳しくありません...しかし、おそらくここに当てはまりますか?

    List<int[]> Unique(List<int> intList)
    {
        List<int[]> results = new List<int[]>();

        bool[] toAdd = new bool[intList.Count];
        toAdd[toAdd.Length - 1] = true;

        int totalSets = (int)Math.Pow(2, intList.Count) - 1;

        List<int[]> sets = new List<int[]>();
        for (int i = 0; i < totalSets; i++)
        {
            int[] set = new int[toAdd.Count(p => p)];
            int c = 0;
            for (int j = toAdd.Length - 1; j >= 0; j--)
                if (toAdd[j])
                    set[c++] = intList[j];

            Shift(toAdd);
            results.Add(set);
        }

        return results;
    }

    void Shift(bool[] array)        
    {
        bool doShift = true;
        for (int i = array.Length - 1; i >= 0; i--)
        {
            if (doShift) 
                array[i] = !array[i];
            doShift = (doShift && !array[i]);
        }
    }
4

2 に答える 2

2

基本的に、時間の複雑さは常に O(2^n) であるため、期待できる最善の方法は、一定の時間の改善です。とはいえ、実装は次のように簡略化できます。

public static List<int[]> powerSetBit(int[] list) {
    if (list == null)
        throw new ArgumentNullException("list may not be null.");

    if (list.Length > 31)
        throw new ArgumentOutOfRangeException("list must have 31 or fewer items.");

    List<int[]> results = new List<int[]>();

    int count = 1 << list.Length;
    for (int i = 0; i < count; i++) {
        int subsetSize = 0;
        for (int j = 0; j < list.Length && (1 << j) < count; j++)
            if ((i & (1 << j)) > 0)
                subsetSize++;

        int[] subset = new int[subsetSize];
        for (int j = 0, k = 0; j < list.Length && (1 << j) < count; j++)
            if ((i & (1 << j)) > 0)
                subset[k++] = list[j];

        results.Add(subset);
    }

    return results;
}

約 20 項目の入力サイズの場合、既存の実装は私のマシンで実行するのに平均で約 771 ミリ秒かかり、簡略化された実装は私のマシンで実行するのに平均で約 513 ミリ秒かかります。

実装の可読性を向上させることが目標である場合は、再帰的な実装を使用することもできますが、これは少し遅くなります (サンプル テスト ケースでは平均 857 ミリ秒)。

再帰的な解決策は、リストがベキ集合の要素であり、リストの各ベキ セットからその要素の 1 つを除いたものもベキ セット全体の一部であることを観察することによって機能します。セットの重複を防ぐために、トラバーサル ツリーの左側のみが 2 番目の引数を使用して考慮されます。

static class Program {
    static void Main() {
        List<List<int>> lists = powerSet(new List<int>() { 1, 2, 3, 4 });
        foreach (List<int> list in lists)
            Console.WriteLine("{{{0}}}", String.Join(", ", list));
    }

    public static List<List<int>> powerSet(List<int> list) {
        if (list == null)
            throw new ArgumentNullException("list may not be null.");

        return powerSet(list, list.Count);
    }

    public static List<List<int>> powerSet(List<int> list, int j) {
        if (list == null)
            throw new ArgumentNullException("list may not be null.");

        if (j < 0)
            throw new ArgumentOutOfRangeException("j must be not be negative.");

        List<List<int>> results = new List<List<int>>() { new List<int>(list) };

        for (int i = 0; i < j; i++) { 
            int x = list[i];
            list.RemoveAt(i);
            results.AddRange(powerSet(list, i));
            list.Insert(i, x);
        }

        return results;
    }
}
于 2013-09-20T20:23:43.883 に答える