c# - 来自元素集合的唯一无序集(幂集)

Question

我星期五的大部分时间都花在了解决这个问题上:

从整数集合生成唯一的无序集合列表。

[如果一个元素在原始集合中重复出现，则在构建集合时将其视为两个独立的元素]

我最终得出了以下结论，得到了正确的结果。我想知道是否有更有效的方法。

特别是，我的 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]);
        }
    }

Answer 1

从根本上说，时间复杂度始终为 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 毫秒)。

递归解决方案的工作原理是观察列表是幂集的一个元素，并且列表中的每个幂集减去其中一个元素也是整个幂集的一部分。为了防止重复集，通过使用第二个参数只考虑遍历树的左侧。

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;
    }
}