Creando un conjunto de potencias de una secuencia

Estoy tratando de crear un progtwig que sea una base para crear posibles combinaciones de una secuencia, una cadena o un número. Este es un tipo de progtwig de cifrado / descifrado. Estoy usando Visual Studio 2013 y C #. Lo que estoy tratando de hacer es generar un conjunto de energía fuera de una secuencia, pero estoy un poco confundido y no puedo continuar. Aquí está el código.

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  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); } 

Quiero que este código sea genérico, es decir, paso cualquier secuencia y genera un conjunto de energía para mí. Entonces quiero reutilizarlo más en mi progtwig. Puedo hacer el rest, simplemente estoy atascado en la generación del conjunto de energía. ¿Alguien me puede ayudar?.

El conjunto de potencia es fácil de generar si uno está familiarizado con los bits. Para el conjunto de N elementos, habrá 2^N subconjuntos que irán al conjunto de potencias (incluido el conjunto vacío y el conjunto inicial). Por lo tanto, cada elemento será IN o OUT ( 1 o 0 en otras palabras). Teniendo esto en cuenta, es fácil representar subconjuntos del conjunto como máscaras de bits. A partir de la enumeración de todas las máscaras de bits posibles, es posible construir todos los conjuntos de potencias. Para hacer esto necesitamos examinar cada bit en la máscara de bits y tomar el elemento de conjunto de entrada si hay 1 en ese lugar. A continuación se muestra un ejemplo para la string (colección de caracteres) como entrada. Se puede reescribir fácilmente para que funcione para recostackr valores de cualquier tipo.

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

Ejemplo

Supongamos que tiene la cadena "xyz" como entrada, contiene 3 elementos, que habrá 2^3 == 8 elementos en el conjunto de potencias. Si va a realizar una iteración de 0 a 7 , obtendrá la siguiente tabla. Columnas: (entero de 10 bases; representación de bits (2 bases); subconjunto del conjunto inicial).

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

Puede observar que la tercera columna contiene todos los subconjuntos de la cadena inicial "xyz"


Otro enfoque (dos veces más rápido) y una implementación genérica.

Inspirado por la idea de Eric, he implementado otra variante de este algoritmo (sin bits ahora). También lo hice genérico. Creo que este código es casi el más rápido de lo que se puede escribir para el cálculo de Power Set. Su complejidad es la misma que para el enfoque de bits O(n * 2^n) , pero para este enfoque, la constante se reduce a la mitad.

 public static T[][] FastPowerSet(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; } 

El enfoque de SergeyS es perfectamente razonable. Aquí hay una forma alternativa de pensar en ello.

A los efectos de esta respuesta, voy a suponer que los “conjuntos” son secuencias finitas.

Definimos la función P recursivamente de la siguiente manera.

  • Un conjunto está vacío, o un solo elemento H seguido de un conjunto T.
  • P(empty) --> { empty }
  • P(H : T) --> la unión de P(T) y cada elemento de P(T) precedida con H

Vamos a intentarlo. ¿Cuál es el poder de {Apple, Banana, Cherry} ?

No es un conjunto vacío, por lo que el conjunto de potencias de {Apple, Banana, Cherry} es el conjunto de potencias de {Banana, Cherry} , más los conjuntos formados por Apple de cada uno.

Así que necesitamos saber el conjunto de poder de {Banana, Cherry} . Es el conjunto de potencias de {Cherry} más la forma de conjuntos al añadir Banana a cada uno.

Así que necesitamos saber el conjunto de poder de {Cherry} . Es el conjunto de potencias del conjunto vacío, más los conjuntos que se forman al precargar Cherry a cada uno.

Así que necesitamos saber el conjunto de potencias del conjunto vacío. Es el conjunto que contiene el conjunto vacío. { {} }

Ahora precede cada elemento con Cherry y toma la unión. Eso es { {Cherry}, {} } . Eso nos da el conjunto de poder de { Cherry } . Recuerda que necesitábamos eso para encontrar el conjunto de poder de {Banana, Cherry} , así que lo unimos con el Banana preparado para cada uno y obtenemos { {Banana, Cherry}, {Banana}, {Cherry}, {}} y ese es el conjunto de poder de {Banana, Cherry} .

Ahora necesitábamos eso para obtener el conjunto de poder de {Apple, Banana, Cherry} , así que únalo con Apple adjunto a cada uno y tenemos { {Apple, Banana, Cherry}, {Apple, Banana}, {Apple, Cherry}, {Apple}, {Banana, Cherry}, {Banana}, {Cherry}, {}} y hemos terminado.

El código debe ser sencillo de escribir. Primero necesitaremos un método de ayuda:

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

Y ahora el código es una traducción directa de la descripción del algoritmo:

 static IEnumerable> PowerSet(this IEnumerable 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; } } 

¿Tener sentido?

———– ACTUALIZACIÓN —————-

Sergey señala correctamente que mi código tiene un algoritmo Schlemiel el pintor y, por lo tanto, consume grandes cantidades de tiempo y memoria; buena captura Sergey. Aquí hay una versión eficiente que usa una stack inmutable:

 class ImmutableList { public static readonly ImmutableList Empty = new ImmutableList(null, default(T)); private ImmutableList(ImmutableList tail, T head) { this.Head = head; this.Tail = tail; } public T Head { get; private set; } public ImmutableList Tail { get; private set; } public ImmutableList Push(T head) { return new ImmutableList(this, head); } public IEnumerable> 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; } } } 

El mismo algoritmo que menciona SergeyS usando Linq (donde inputSet es la entrada y outputPowerSet es la salida):

 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()); } 

Muy tarde para el juego, pero ¿por qué no el enfoque de abajo? Parece significativamente más simple que las sugerencias publicadas aquí:

  /* 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 (ie 2^4), as expected. */ private static void PowerSet(IList nums, ref IList> output) { // ToDo: validate args output.Add(new List()); ExpandSet(nums, 0, ref output); } private static void ExpandSet(IList nums, int pos, ref IList> output) { if (pos == nums.Count) { return; } List tmp; int item = nums[pos]; for (int i = 0, n = output.Count; i < n; i++) { tmp = new List(); tmp.AddRange(output[i]); tmp.Add(item); output.Add(tmp); } ExpandSet(nums, pos + 1, ref output); }