创建序列的功率设定 [英] Creating a power set of a Sequence
问题描述
我想创建一个程序，它是用于创建序列，字符串或数字的可能组合的基地。这是某种加密/解密程序。我使用Visual Studio 2013和C＃。我所要做的就是以发电设置了一个序列，但我有点困惑，不能继续进行。这里是code。
I am trying to create a program that is a base for creating possible combinations of a sequence, string or a number. This is some sort of encryption / decryption program. I am using Visual Studio 2013 and C#. What I am trying to do is to generate a power set out of a sequence, but I am little bit confused and can't proceed any further. Here is the code.
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);
}
我想这code是通用的，即我传递任何序列和它产生的功率为我设置。然后，我想进一步重用它在我的计划。我所能做的只是我停留在产生发电机组的其余部分。有人可以帮我吗？。
I want this code to be generic i.e. I pass any sequence and it generates a power set for me. Then I want to reuse it further in my program. I can do the rest simply I am stuck in generating the power set. Can someone help me?.
推荐答案
发电机组很容易产生，如果一个熟悉位。对于组 N 元素，会有 2 ^ N 子集，这将去幂集（包括空集和初始集）。因此，每一个元素将是要么IN或OUT（ 1 或 0 换句话说）。考虑到这一点，很容易重新设定的位掩码的present子集。不是通过所有可能的位掩码枚举，就可以构建整个发电机组。为了做到这一点，我们需要检查位掩码的每一位，并采取输入设置的元素，如果有 1 在那个地方。下面是示例字符串（字符集）为输入。它可以很容易地重写，以工作为集合的任何类型的值。
Power set is easy to generate if one is familiar with bits. For the set of N elements, there will be 2^N subsets which will go to power set (including empty set and initial set). So each element will be either IN or OUT (1 or 0 in other words). Taking this into consideration, it is easy to represent subsets of the set as bit masks. Than enumerating through all possible bit masks, it is possible construct the whole power sets. In order to do this we need to examine each bit in bit mask and take element of input set if there is 1 in that place. Below is example for string (collection of chars) as input. It can be easily rewritten to work for collection of any type values.
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个碱基整数位重新presentation（2基）;初始设置的子集）
Example
Suppose you have string "xyz" as input, it contains 3 elements, than there will be 2^3 == 8 elements in power set. If you will be iterating from 0 to 7 you will get the following table. Columns: (10-base integer; bits representation (2-base); subset of initial set).
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
You can notice that third column contains all subsets of initial string "xyz"
由Eric的想法的启发，我已经实现了这个算法的另一个变体（无位现在）。我也使得通用的。我相信这code附近是最快的有什么可以对整机运算被写入。它的复杂性是一样的位接近 O（N * 2 ^ n）的，但这种做法不断被减半。
Inspired by Eric's idea, I have implemented another variant of this algorithm (without bits now). Also I made it generic. I believe this code is near to fastest of what can be written for Power Set calculation. Its complexity is the same as for bits approach O(n * 2^n), but for this approach constant is halved.
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;
}
这篇关于创建序列的功率设定的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
