创建序列的幂集

一尘不染

创建序列的幂集

algorithm

我正在尝试创建一个程序，该程序是创建序列，字符串或数字的可能组合的基础。这是某种加密/解密程序。我正在使用Visual Studio
2013和C＃。我正在尝试做的是按顺序生成电源，但是我有点困惑，无法继续进行下去。这是代码。

public static void randomSeq(){
    int temp = 0;
    string seq = "1234";
    StringBuilder 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);
}

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

阅读 233

2020-07-28

共1个答案

一尘不染

如果人们熟悉位，就很容易产生功率设定。对于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计算中最快的代码。它的复杂度与位方法相同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;
}

2020-07-28