Cálculo de todos los posibles sub-secuencias de una determinada longitud (C#)

Question

Si tengo una secuencia de la siguiente manera (digamos que se trata de un IEnumerable<T>):

[A, B, C, D, E] 

entonces ¿cuál es la manera más limpia para calcular todas las posibles (continua y no continuo) subsequences de una longitud determinada? El orden de los resultados en el conjunto de resultados no es importante, pero no debe incluir duplicados.

p. Ej. Si quiero calcular todas las posibles subsecuencias de longitud 3 el conjunto de resultados sería:

[A, B, C] 
[A, B, D] 
[A, B, E] 
[A, C, D] 
[A, C, E] 
[A, D, E] 
[B, C, D] 
[B, C, E] 
[B, D, E] 
[C, D, E] 

---

Para el registro, la respuesta aceptada a continuación me dio un buen punto de partida, y aquí está el código que he ido con el que se actualiza para utilizar algunos de los nuevos métodos de extensión .NET 3.5:

public static IEnumerable<IEnumerable<T>> Subsequences<T>(
    this IEnumerable<T> source, 
    int count) 
{ 
    if (count == 0) 
    { 
     yield return Enumerable.Empty<T>(); 
    } 
    else 
    { 
     var skip = 1; 
     foreach (var first in source) 
     { 
      foreach (var rest in source.Skip(skip).Subsequences(count - 1)) 
      { 
       yield return Enumerable.Repeat(first, 1).Concat(rest); 
      } 

      skip++; 
     } 
    } 
} 

Answer 1

que he tenido éxito con la clase de IANG PermuteUtils:

Resultados: en

 
[ A B C ] 
[ A B D ] 
[ A B E ] 
[ A C B ] 
[ A C D ] 
[ A C E ] 
[ A D B ] 
[ A D C ] 
[ A D E ] 
[ A E B ] 
[ A E C ] 
[ A E D ] 
[ B A C ] 
[ B A D ] 
[ B A E ] 
[ B C A ] 
[ B C D ] 
[ B C E ] 
[ B D A ] 
[ B D C ] 
... 

Answer 2

algo como:

static void Main() 
{ 
    string[] data = { "A", "B", "C", "D", "E" }; 
    WalkSubSequences(data, 3); 
} 

public static void WalkSubSequences<T>(IEnumerable<T> data, int sequenceLength) 
{ 
    T[] selected = new T[sequenceLength]; 
    WalkSubSequences(data.ToArray(), selected, 0, sequenceLength); 
} 
private static void WalkSubSequences<T>(T[] data, T[] selected, 
    int startIndex, int sequenceLength) 
{ 
    for (int i = startIndex; i + sequenceLength <= data.Length; i++) 
    { 
     selected[selected.Length - sequenceLength] = data[i]; 
     if (sequenceLength == 1) 
     { 
      ShowResult(selected); 
     } 
     else 
     { 
      WalkSubSequences(data, selected, i + 1, sequenceLength - 1); 
     } 
    } 
} 

private static void ShowResult<T>(T[] selected) 
{ 
    StringBuilder sb = new StringBuilder(); 
    sb.Append(selected[0]); 
    for (int j = 1; j < selected.Length; j++) 
    { 
     sb.Append(';').Append(selected[j]); 
    } 
    Console.WriteLine(sb.ToString()); 
} 

Answer 3

que sugeriría un algoritmo recursivo para esto. Lo siento, pero ha pasado un tiempo desde que hice algo en C#, así que solo daré pseudocódigo aquí.

function allPossible(iterator, length, currSubSeq, allResults) { 
    // Add the current sub sequence to the results if it is the correct length. 
    if (currSubSeq.length == length) { 
     copy = currSubSeq.copy(); 
     allResults.add(copy); 
    } 
    // If it is too long, return early. 
    else if (currSubSeq.length > length) { 
     return allResults; 
    } 

    // Get the next item from the iterator and handle both cases: 
    // I.E. when it is, and when it isn't in a sub sequence. 
    item = iterator.getNext(); 
    allPossible(iterator, currSubSeq, allResults); 
    currSubSeq.add(item); 
    allPossible(iterator, currSubSeq, allResults); 

    return allResults; 
} 

Entonces encuentras todas las posibles secuencias sub llamando allPossible con un iterator que produce todos los elementos en su secuencia original, el length que desea que sus sub-secuencias, una secuencia vacía de artículos para currSubSeq, y un vacío secuencia de secuencias de elementos para allResults. Estoy asumiendo la semántica de paso por referencia para todos los parámetros. Perdón por no haber podido darle la implementación correcta de C#, pero estoy seguro de que sabe más que suficiente para tomar mi boceto de algoritmo y convertirlo en código.

Una última cosa. Debido a que este algoritmo es recursivo, puede tener un desbordamiento de pila si lo ejecuta en una secuencia muy larga con un parámetro grande length ya que el uso de la pila es O (2^N) donde N = length. No creo que esto sea un gran problema porque el algoritmo tiene O (2^N) tiempo de ejecución debido a la naturaleza del problema, por lo que no debe tratar de ejecutarlo con un número suficientemente grande length para desbordar la pila de todos modos !

CAVEAT No he probado realmente este pseudo-código, por lo que puede haber algo sutil en el que no haya pensado.

Answer 4

Aquí hay una solución que almacena el estado en una matriz de bools. Funciona creando los siguientes estados en cada llamada a Next() (n = 5, k = 3).

 
1 1 1 . . Move last 1 right once. 
1 1 . 1 . Move last 1 right once. 
1 1 . . 1 Move last 1 right once. 
1 . 1 1 . Move the second last 1 right once and all 1s from the right back. 
1 . 1 . 1 Move last 1 right once. 
1 . . 1 1 Move the second last 1 right once (and all 1s from the right back.) 
. 1 1 1 . Move the third last 1 right once and all 1s from the right back. 
. 1 1 . 1 Move last 1 right once. 
. 1 . 1 1 Move the second last 1 right once (and all 1s from the right back.) 
. . 1 1 1 Move the third last 1 right once (and all 1s from the right back.) 

Este estado puede usarse entonces para seleccionar los elementos coresponding de la secuencia suministrada para cada estado.

Primero la inicialización.

public static Boolean[] Initialize(Int32 n, Int32 k) 
{ 
    return Enumerable.Concat(Enumerable.Repeat(true, k), 
          Enumerable.Repeat(false, n - k)).ToArray(); 
} 

El código para pasar a la siguiente combinación (subsecuencia).

public static Boolean Next(this Boolean[] list) 
{ 
    Int32 lastOneIndex = Array.LastIndexOf(list, true); 

    if (lastOneIndex == -1) 
    { 
     return false; // All zeros. 0000000 
    } 
    else if (lastOneIndex < list.Length - 1) 
    { 
     // Move the last one right once. 1100X00 => 11000X0 
     list.MoveBlock(lastOneIndex, lastOneIndex, lastOneIndex + 1); 
    } 
    else 
    { 
     Int32 lastZeroIndex = Array.LastIndexOf(list, false, lastOneIndex); 

     if (lastZeroIndex == -1) 
     { 
      return false; // All ones. 1111111 
     } 
     else 
     { 
      Int32 blockEndIndex = Array.LastIndexOf(list, true, lastZeroIndex); 

      if (blockEndIndex == -1) 
      { 
       // Move all ones back to the very left. 0000XXX => XXX0000 
       list.MoveBlock(lastZeroIndex + 1, lastOneIndex, 0); 

       return false; // Back at initial position. 
      } 
      else 
      { 
       // Move the block end right once. 11X0011 => 110X011 
       list.MoveBlock(blockEndIndex, blockEndIndex, blockEndIndex + 1); 
       // Move the block of ones from the very right back left. 11010XX => 1101XX0 
       list.MoveBlock(lastZeroIndex + 1, lastOneIndex, blockEndIndex + 2); 
      } 
     } 
    } 

    return true; 
} 

Finalmente algunos métodos de ayuda.

public static void MoveBlock(this Boolean[] list, Int32 oldStart, Int32 oldEnd, Int32 newStart) 
{ 
    list.ClearBlock(oldStart, oldEnd); 
    list.SetBlock(newStart, newStart + oldEnd - oldStart); 
} 

public static void SetBlock(this Boolean[] list, Int32 start, Int32 end) 
{ 
    list.SetBlockToValue(start, end, true); 
} 

public static void ClearBlock(this Boolean[] list, Int32 start, Int32 end) 
{ 
    list.SetBlockToValue(start, end, false); 
} 

public static void SetBlockToValue(this Boolean[] list, Int32 start, Int32 end, Boolean value) 
{ 
    for (int i = start; i <= end; i++) 
    { 
     list[i] = value; 
    } 
} 

Y un ejemplo de uso del uso de una cadena en lugar de una lista.

var sequence = "ABCDE"; 

var state = Initialize(sequence.Count(), 5); 

do 
{ 
    Console.WriteLine(new String(sequence.Where((_, idx) => state[idx]).ToArray())); 
} 
while (state.Next());