2009-05-12 31 views
5

Se ho una sequenza come segue (diciamo è un IEnumerable<T>):Calcolo tutte le possibili sottosequenze di lunghezza data (C#)

[A, B, C, D, E] 

Allora qual è il modo più pulito per calcolare tutte le possibili (continuo e non continuo) subsequences di una determinata lunghezza? L'ordine dei risultati nel set di risultati non è importante, ma non dovrebbe includere duplicati.

ad es. Se voglio calcolare tutte le possibili sottosequenze di lunghezza 3 set di risultati sarebbe:

[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] 

Per la cronaca, la risposta accettata sotto mi ha dato un buon punto di partenza, ed ecco il codice che ho passato con che viene aggiornato di utilizzare alcuni dei nuovi metodi di estensione 3.5 di .NET:

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++; 
     } 
    } 
} 
+0

Avere IEnumerable è dannoso per voi, perché si andando oltre l'elenco più volte, in modo da avere accesso indicizzatore sarebbe un enorme vantaggio per voi. – DevinB

risposta

5

ho avuto successo con PermuteUtils classe di IANG:

char[] items = new char[] { 'A', 'B', 'C', 'D', 'E' }; 

foreach (IEnumerable<char> permutation in PermuteUtils.Permute(items, 3)) { 
    Console.Write("["); 
    foreach (char c in permutation) { 
     Console.Write(" " + c); 
    } 
    Console.WriteLine(" ]"); 
} 

Risultati in:

 
[ 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 ] 
... 
+0

Non è proprio quello che cerco; sono tutte le permutazioni possibili ma, per esempio [A, D, B] non è una sottosequenza perché non è nello stesso ordine. –

+1

Poi di nuovo, è facile da modificare per dare il risultato giusto così ti darò la risposta accettata. Ta. –

1

qualcosa di simile:

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

vorrei suggerire un algoritmo ricorsivo per questo. Mi dispiace, ma è passato un po 'di tempo da quando ho fatto qualcosa in C#, quindi mi limiterò a dare pseudo-codice qui.

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

Poi a trovare tutte le possibili sequenze sub chiamando allPossible con una iterator che produce tutti gli elementi nella sequenza originale, il length che si desidera che i sub-sequenze, una sequenza vuota di oggetti per currSubSeq, e di un vuoto sequenza di sequenze di articoli per allResults. Sto assumendo la semantica pass-by-reference per tutti i parametri. Scusa se non sono riuscito a darti l'implementazione C# corretta, ma sono sicuro che ne sai più che abbastanza da prendere il mio abbozzo dell'algoritmo e trasformarlo in codice.

Un'ultima cosa. Poiché questo algoritmo è ricorsivo, potresti avere uno stack overflow se lo esegui su una sequenza molto lunga con un grande parametro length poiché l'utilizzo dello stack è O (2^N) dove N = length. Non penso che questo sia un grosso problema perché l'algoritmo ha O (2^N) run-time a causa della natura del problema, quindi non dovresti provare ad eseguirlo con uno spazio abbastanza grande length per eccedere comunque lo stack !

CAVEAT Non ho ancora testato questo pseudo-codice, quindi potrebbe esserci qualcosa di sottile a cui non ho pensato.

+0

@A. Levy: "A" sotto-sequenza non continua "non è una sotto-sequenza." Sta usando la corretta definizione matematica di sottosuccessione, che è esattamente come lui ha descritto. – Kevin

+0

La domanda usa correttamente la "sottosuccessione". E i sottoinsiemi non sono ordinati, quindi è una parola completamente sbagliata da usare anche. – ShreevatsaR

+0

@Kevin e @ShreevatsaR: Grazie a entrambi per aver corretto la mia incomprensione delle sottosequenze. A quanto pare stavo pensando "sottostringa". Ho rimosso quel pezzo di pedanteria ignorante dalla mia risposta. @Greg Beech, se leggi questo commento, forse puoi includere un link a una definizione di sottosequenze in modo che gli ignoranti come me possano essere educati. Ad esempio: http://en.wikipedia.org/wiki/Subsequence –

0

Ecco una soluzione che memorizza lo stato in una serie di bool. Funziona creando i seguenti stati su ciascuna chiamata 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.) 

Questo stato può quindi essere utilizzato per selezionare gli elementi corrispondenti dalla sequenza fornita per ogni stato.

Inizialmente l'inizializzazione.

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

Il codice per passare alla combinazione successiva (sottosuccessione).

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

Infine alcuni metodi di supporto.

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

E un esempio di utilizzo utilizzando una stringa anziché un elenco.

var sequence = "ABCDE"; 

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

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