18

我正在尝试创建一个程序，该程序是创建序列、字符串或数字的可能组合的基础。这是某种加密/解密程序。我正在使用 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);
}

我希望这段代码是通用的，即我传递任何序列，它会为我生成一个幂集。然后我想在我的程序中进一步重用它。我可以简单地完成剩下的工作，因为我被困在生成电源组中。有人能帮我吗？。

4

4 回答 4

38

如果熟悉位，则很容易生成幂集。对于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 想法的启发，我实现了该算法的另一个变体（现在没有位）。我也让它通用。我相信这段代码几乎是可以为 Power Set 计算编写的代码中最快的。它的复杂性与 bits 方法相同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;
}
于 2013-11-10T14:53:18.080 回答
7

SergeyS 的方法是完全合理的。这是另一种思考方式。

出于这个答案的目的，我将假设“集合”是有限序列。

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

  • 一个集合要么是空的，要么是单个项目 H 后跟一个集合 T。
  • P(empty) --> { empty }
  • P(H : T) -->的并集P(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附加到 each 结合起来，我们{ {Apple, Banana, Cherry}, {Apple, Banana}, {Apple, Cherry}, {Apple}, {Banana, Cherry}, {Banana}, {Cherry}, {}}已经完成了。

代码应该易于编写。首先我们需要一个辅助方法：

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 算法，因此会消耗大量的时间和内存。很好地抓住谢尔盖。这是一个使用不可变堆栈的高效版本：

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;
        }
    }
}
于 2013-11-10T16:09:12.707 回答
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());
}
于 2014-08-20T08:55:54.620 回答
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);
    }
于 2017-01-16T21:41:32.387 回答