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

本文关键字：集合 幂集 无序 元素 唯一 | 更新日期: 2023-09-27 18:32:15

我已经失去了大部分的星期五来尝试解决这个问题：

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

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

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

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

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

从根本上说，时间复杂度将始终为 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;
    }
}

由于原始数组中的每个元素即使具有相同的值也被认为是唯一的，因此可以通过以下方式处理问题： 对于数组中的每个元素，您有两种选择：包括它或不将其包含在集合中。因此，每个元素将解的数量加倍，从而得到解决方案的总数：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;
}
相关文章：