创建序列的幂集

Question

创建序列的幂集

20

我正在尝试创建一个程序，用于生成序列、字符串或数字的可能组合，这是某种加密/解密程序。我正在使用Visual Studio 2013和C＃。我想做的是从一个序列中生成幂集，但我有点困惑，无法继续进行。以下是代码。

public static void randomSeq()
{
    int temp = 0;
    string seq = "1234";

    var sb = new StringBuilder();
    char[] bits = seq.Select((char c) => c).ToArray();

    Console.Write("Given Sequence: ");
    Console.Write(seq);
    Console.WriteLine();
    Console.WriteLine("Generated possiblities");

    foreach (char item in bits)
        Console.WriteLine(item);
    do
    {
        if (temp <= 2)
        {
            for (int i = temp + 1; i < bits.Length; i++)
            {
                 sb.Append(bits[temp]);
                 sb.Append(bits[i]);
                 Console.WriteLine(sb);
                
                 sb.Clear();
            }
        }
        else if (temp > 2)
        {
            for (int k = 0; k < temp; k++)
                sb.Append(bits[k]);

            for (int l = temp + 1; l < bits.Length; l++)
            {
                sb.Append(bits[temp]);
                sb.Append(bits[l]);
                Console.WriteLine(sb);

                sb.Clear();
            }
        }
        temp++;
    }
    while (temp != bits.Length);
}

我希望这段代码能够通用，即我可以传递任何序列并为我生成一个幂集。然后我想在我的程序中进一步重复使用它。其他部分我可以简单地完成，但是我卡在了如何生成幂集。有人能帮我吗？

- Jamal Hussain

2

看一下这个。http://adrianwithy.com/2012/02/23/c-power-set-builder/ - Sam Leach

1

如果您对此主题感兴趣，您可能想看看我的有关生成序列的n元笛卡尔积的文章以及有关生成系列的所有排列的系列。http://ericlippert.com/2013/04/15/producing-permutations-part-one/ 和 http://ericlippert.com/2010/06/28/computing-a-cartesian-product-with-linq/ - Eric Lippert

4个回答

9

SergeyS的方法是完全合理的。这里有一种替代思路。

为了回答这个问题，我假设“集合”是有限序列。

我们递归地定义函数P如下。

一个集合可以是空集，也可以是单个项H后跟集合T。
P(empty) --> { empty }
P(H : T) -->是P(T)和每个元素与H组合的并集。

让我们试试看。{Apple，Banana，Cherry}的幂集是什么？

它不是空集，因此{Apple，Banana，Cherry}的幂集是{Banana，Cherry}的幂集，再加上将每个元素与Apple组合而成的集合。

因此，我们需要知道{Banana，Cherry}的幂集。它是{Cherry}的幂集加上将每个元素与Banana组合而成的集合。

所以我们需要知道{Cherry}的幂集。它是空集的幂集，加上将每个元素与Cherry组合而成的集合。

所以我们需要知道空集的幂集。它是包含空集的集合。{ {} }

现在将每个元素与Cherry组合并取并集。那就是{ {Cherry}, {} }。这给我们了{ Cherry }的幂集。记住，我们需要它来找到{Banana，Cherry}的幂集，所以我们将其与每个元素前面加上Banana组合起来，并得到{ {Banana, Cherry}, {Banana}, {Cherry}, {}}，这就是{Banana，Cherry}的幂集。

现在我们需要它来获取{Apple，Banana，Cherry}的幂集，所以将其与每个元素后面加上Apple组合起来，我们就有了{ {Apple, Banana, Cherry}, {Apple, Banana}, {Apple, Cherry}, {Apple}, {Banana, Cherry}, {Banana}, {Cherry}, {}}，完成了。

代码应该很容易编写。首先我们需要一个helper方法：

static IEnumerable<T> Prepend<T>(this IEnumerable<T> tail, T head)
{
    yield return head;
    foreach(T item in tail) yield return item;
}

现在，代码是算法描述的简单翻译：

static IEnumerable<IEnumerable<T>> PowerSet<T>(this IEnumerable<T> items)
{
    if (!items.Any())
        yield return items; // { { } } 
    else
    {
        var head = items.First();
        var powerset = items.Skip(1).PowerSet().ToList();
        foreach(var set in powerset) yield return set.Prepend(head); 
        foreach(var set in powerset) yield return set;
     }
}

听明白了吗？

----------- 更新 ----------------

Sergey指出我的代码有一个像Schlemiel the Painter算法那样的问题，因此会消耗大量时间和内存；很好地捕捉到了问题 Sergey。这里是一个使用不可变栈的高效版本：

class ImmutableList<T>
{
    public static readonly ImmutableList<T> Empty = new ImmutableList<T>(null, default(T));
    private ImmutableList(ImmutableList<T> tail, T head)
    {
        this.Head = head;
        this.Tail = tail;
    }
    public T Head { get; private set; }
    public ImmutableList<T> Tail { get; private set; }
    public ImmutableList<T> Push(T head)
    {
        return new ImmutableList<T>(this, head);
    }
    public IEnumerable<ImmutableList<T>> PowerSet()
    {
        if (this == Empty)
            yield return this;
        else
        {
            var powerset = Tail.PowerSet();
            foreach (var set in powerset) yield return set.Push(Head);
            foreach (var set in powerset) yield return set;
        }
    }
}

- Eric Lippert

1

想法不错，但从性能角度来看，实现并不太好。在我的电脑上，当处理20个元素时程序会因为内存溢出异常而崩溃（在崩溃时使用了超过1.5GB的内存）。 - SergeyS

@SergeyS：说得好，由于LINQ执行的延迟特性，这里发生了很多不必要的重复计算。我来修复一下。试试现在；一点点ToList可能会有很大的区别。 - Eric Lippert

3

Eric，我认为算法是多项式还是指数并不重要。如果可以优化10倍，那么肯定值得去做 :) 关于指数算法，以非递归方式实现它们非常有趣。 - SergeyS

3

如果你有特定的目标大小，那么优化很可能是值得追求的。我的观点是：假设你可以以速度X合理处理大小为40的情况。然后你做了很多优化，将其提高到速度10X。现在突然间，你可以合理地处理大小为43的情况，而不是400。在优化指数级算法的常数因子方面花费的努力并没有给你带来大的回报，就像优化多项式算法的常数因子一样。 - Eric Lippert

2

@SergeyS：这并不是说你的方法是错误的；这是一个很好的方法。这也是一个很好的例子，说明最直接的LINQ解决方案有时会因为意外的重新计算和隐藏的成本而出乎意料地低效。 - Eric Lippert

显示剩余8条评论

2

同样的算法SergeyS提到了使用Linq（其中inputSet是输入，outputPowerSet是输出）：

int setLength = inputSet.Count;
int powerSetLength = 1 << setLength;
for (int bitMask = 0; bitMask < powerSetLength; bitMask++)
{
    var subSet = from x in inputSet 
                 where ((1 << inputSet.IndexOf(x)) & bitMask) != 0 
                 select x;
    outputPowerSet.Add(subSet.ToList());
}

- uriel

谢谢您的答复！ - Jamal Hussain

我遇到了一些不想要的结果，稍微调整了一下，现在应该会更好了。将子集更改为 var subSet = input.Where((u, i) => ((1 << i) & bitMask) != 0).Select(x => x);。 - matthijsb

1

你的整个解决方案的一行版本（其中e是任何可枚举的对象）：Enumerable.Range(0, (int)Math.Pow(2, e.Count())).Select(b => e.Where((x, i) => ((1 << i) & b) != 0)) - Allon Guralnek

0

很晚才加入游戏，但为什么不采用以下方法呢？它似乎比这里发布的建议要简单得多：

    /*
    Description for a sample set {1, 2, 2, 3}:
    Step 1 - Start with {}:
    {}
    Step 2 - "Expand" previous set by adding 1:
    {}
    ---
    {1}
    Step 3 - Expand previous set by adding the first 2:
    {}
    {1}
    ---
    {2}
    {1,2}
    Step 4 - Expand previous set by adding the second 2:
    {}
    {1}
    {2}
    {1,2}
    ---
    {2}
    {1,2}
    {2,2}
    {1,2,2}
    Step 5 - Expand previous set by adding 3:
    {}
    {1}
    {2}
    {1,2}
    {2}
    {1,2}
    {2,2}
    {1,2,2}
    ---
    {3}
    {1,3}
    {2,3}
    {1,2,3}
    {2,3}
    {1,2,3}
    {2,2,3}
    {1,2,2,3}
    Total elements = 16 (i.e. 2^4), as expected.
    */

    private static void PowerSet(IList<int> nums, ref IList<IList<int>> output)
    {
        // ToDo: validate args
        output.Add(new List<int>());
        ExpandSet(nums, 0, ref output);
    }

    private static void ExpandSet(IList<int> nums, int pos, ref IList<IList<int>> output)
    {
        if (pos == nums.Count)
        {
            return;
        }

        List<int> tmp;
        int item = nums[pos];

        for (int i = 0, n = output.Count; i < n; i++)
        {
            tmp = new List<int>();
            tmp.AddRange(output[i]);
            tmp.Add(item);
            output.Add(tmp);
        }

        ExpandSet(nums, pos + 1, ref output);
    }

- davidfg

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- SergeyS · Accepted Answer

如果熟悉位运算，生成幂集就很容易了。对于包含N个元素的集合，将会有2^N个子集，这些子集都属于幂集（包括空集和初始集）。因此，每个元素都将被标记为IN或OUT（换句话说，是1或0）。

考虑到这一点，我们可以将集合的子集表示为位掩码，然后通过枚举所有可能的位掩码，就可以构建出整个幂集。为了做到这一点，我们需要检查位掩码中的每个位，并在那个位置上为1时取输入集合的元素。下面是以string（字符集合）作为输入的示例。它可以轻松地改写为适用于任何类型值的集合。

private static List<string> PowerSet(string input)
{
    int n = input.Length;
    // Power set contains 2^N subsets.
    int powerSetCount = 1 << n;
    var ans = new List<string>();

    for (int setMask = 0; setMask < powerSetCount; setMask++)
    {
        var s = new StringBuilder();
        for (int i = 0; i < n; i++)
        {
            // Checking whether i'th element of input collection should go to the current subset.
            if ((setMask & (1 << i)) > 0)
            {
                s.Append(input[i]);
            }
        }
        ans.Add(s.ToString());
    }

    return ans;
}

示例

假设您的输入为字符串"xyz"，它包含3个元素，则幂集将包含2^3 == 8个元素。如果您从0到7进行迭代，则会得到以下表格。列：（10进制整数；比特表示（2进制）；初始集合的子集）。

0   000    ...
1   001    ..z
2   010    .y.
3   011    .yz
4   100    x..
5   101    x.z
6   110    xy.
7   111    xyz

你会注意到第三列包含了初始字符串"xyz"的所有子集。

另一种方法（速度快两倍）和通用实现

受 Eric 的想法启发，我实现了这个算法的另一种变体（现在没有位操作了）。而且我把它做成了通用的。我相信这段代码是为了计算幂集而编写的最快的代码之一。它的复杂度与位操作方法相同，为O(n * 2^n)，但对于这种方法，常量减半。

public static T[][] FastPowerSet<T>(T[] seq)
{
    var powerSet = new T[1 << seq.Length][];
    powerSet[0] = new T[0]; // starting only with empty set

    for (int i = 0; i < seq.Length; i++)
    {
        var cur = seq[i];
        int count = 1 << i; // doubling list each time
        for (int j = 0; j < count; j++)
        {
            var source = powerSet[j];
            var destination = powerSet[count + j] = new T[source.Length + 1];
            for (int q = 0; q < source.Length; q++)
                destination[q] = source[q];
            destination[source.Length] = cur;
        }
    }
    return powerSet;
}