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

我希望这段代码是通用的，即我传递任何序列，它都会为我生成一个幂集。然后我想在我的程序中进一步重用它。我可以做剩下的事情，只要我坚持发电。有人可以帮助我吗？

最佳答案

如果熟悉位，幂集很容易生成。对于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;
}

关于c# - 创建序列的幂集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19890781/