1

我在星期五的大部分时间都在尝试解决这个问题：

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

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

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

特别是，我的 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 毫秒）。

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

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 回答
0

由于原始数组中的每个元素即使具有相同的值也被认为是唯一的，因此可以这样处理问题：对于数组中的每个元素，您有两个选择：将其包含在集合中或不将其包含在集合中. 因此，每个元素将解决方案的数量加倍，从而导致解决方案的总数：2 * 2 * 2 ... * 2 - 1 = 2^n - 1。减一是因为您从解决方案中排除了空集。由于解决方案的数量为 2^n - 1，因此您的算法的复杂性不能优于 O(2^n)。您可以做的唯一改进可能是以更紧凑或更易于理解的方式编写算法。

我有以下我认为更简单的代码。我没有测试，所以可能有错误。

// Generate unique sets in the range [k..n) of the input arr. With elements
// from [0..k) already in the prefix.
void Unique(int[] arr, int k, List<int> prefix, List<int[]> solutions)
{
    // Got a solution when we reached the end of array.
    if (k == arr.Length)
    {
        if (prefix.Length > 0)
            solutions.Add(prefix.ToArray());
        return;
    }

    // Exclude arr[k]
    Unique(arr, k + 1, prefix, solutions);

    // Include arr[k]
    prefix.Add(arr[k]);
    Unique(arr, k + 1, prefix, solutions);
    prefix.Remove(arr[k]); // Restore the prefix list
}

List<int[]> Unique(int[] arr)
{
    List<int[]> solutions = new List<int[]>();
    Unique(arr, 0, new List<int>(), List<int[]> solutions);
    return solutions;
}
于 2013-09-20T20:04:21.807 回答