Trova tutte le combinazioni in una stringa separati

Question

Sto cercando di ottenere tutte le combinazioni in una stringa in C# con questa idea in mente:

Data una stringa come foo voglio ottenere un List<string> con i valori:

Come si può vedere, non è facile come ottenere tutte le sottostringhe ma ottenere TUTTI i caratteri in una stringa separati da spazi.

Ho provato a fare qualcosa di simile:

List<string> result = new List<string>(); 
string text = "foo"; 
for (int i = 1; i < foo.Lenght; i++) 
{ 
    //I'm stucked --> everything I think is too stupid and I don't know how to procede or not fast enough. I'm really stuck. 
} 

EDIT: Ci sono alcune risposte corrette, ma è chiaro che nessuno di loro non va bene in quanto le corde con cui sto lavorando hanno tra i 55 ei 85 caratte ognuna in modo che la migliore funzione nelle risposte mi fornisca qualcosa tra 2^54 e 2^84 combinazioni possibili e questo è solo un po 'eccessivo.

Ora è chiaro che trovare tutte le combinazioni e poi fare qualcosa con loro non lo farà. Dovrò lasciar perdere.

Answer 1

Per prima cosa: se la lunghezza della stringa è n, si ottiene 2^n stringhe come uscita. Quindi, se vuoi trattare stringhe di lunghezza 70, hai un problema.

È possibile utilizzare un contatore, enumerando da -2^n, e trattarlo come una maschera bit per bit: se il primo bit è 1, si inserisce uno spazio tra il primo e il secondo carattere, se è zero, non lo fai.

Quindi, un unsigned long di lunghezza 64 è appena sufficiente per il trattamento di stringhe di lunghezza 65.

un esempio di implementazione, senza ricorsione (è un po 'più dettagliato rispetto agli altri esempi), ma dovrebbe essere molto più veloce di le altre implementazioni per gli ingressi lunghi:

public IEnumerable<string> GetPartitionedStrings(string s) 
    { 
     if (s == null) yield break; 

     if (s == "") 
     { 
      yield return ""; 
      yield break; 
     } 

     if (s.Length > 63) throw new ArgumentOutOfRangeException("String too long..."); 

     var arr = s.ToCharArray(); 
     for(ulong i = 0, maxI = 1UL << (s.Length - 1); i < maxI; i++) 
     { 
      yield return PutSpaces(arr, i); 
     } 
    } 

    public string PutSpaces(char[] arr, ulong spacesPositions) 
    { 
     var sb = new StringBuilder(arr.Length * 2); 
     sb.Append(arr[0]); 

     ulong l = 1; 
     for (int i = 1; i < arr.Length; i++, l <<= 1) 
     { 
      if ((spacesPositions & l) != 0UL) sb.Append(" "); 

      sb.Append(arr[i]); 
     } 

     return sb.ToString(); 
    } 

Probabilmente si potrebbe ottenere via con un campo di bit, ma siamo già in miliardi di stringhe, quindi vorrei provare a riformulare un po 'il problema.

Answer 2

Si potrebbe provare qualcosa di ricorsivo. Si inizia con una stringa, hello.

Per ogni carattere che non è uno spazio, se non è seguito da uno spazio, aggiungerne uno in quella posizione nella stringa ed eseguire la funzione su quella stringa. Nella prima iterazione, si dispone:

• h ello
• he llo
• hel lo
• hell o
• hello

Ripetere fino a quando tutti i personaggi sono seguiti da spazi. Questo creerà i duplicati però.

Answer 3

È possibile farlo utilizzando la ricorsione, a partire da una stringa vuota, si chiama in modo ricorsivo l'aggiunta di uno spazio e senza aggiungerla, e l'aggiunta di carattere corrente:

static IEnumerable<string> SplitString(string s, int max) 
{ 
    return SplitString(s, 0, max, max); 
} 

private static IEnumerable<string> SplitString(string s, int idx, int available, int maxLength) 
{ 
    if (idx == s.Length) yield return string.Empty; 
    else 
    { 
     if (available > 0) 
      foreach (var item in SplitString(s, idx + 1, available - 1, maxLength)) 
       yield return s[idx] + item; 

     if (idx > 0) 
      foreach (var item in SplitString(s, idx + 1, maxLength - 1, maxLength)) 
       yield return " " + s[idx] + item; 
    } 
} 

Per un ingresso come abcde, SplitString("abcde", 3) ottenere questa uscita :

abc de 
abc d e 
ab cde 
ab cd e 
ab c de 
ab c d e 
a bcd e 
a bc de 
a bc d e 
a b cde 
a b cd e 
a b c de 
a b c d e 

Answer 4

Che cosa si potrebbe fare è convertire la stringa in un array di caratteri come questo:

char characters[] = text.toCharArray()

Poi nel ciclo iterate attraverso questa matrice

for (int i = 1; i < foo.Lenght; i++) 
{ 
    System.out.println(characters[i]); 
} 

Answer 5

Ecco un'altra soluzione ricorsiva considerare: risultato

private static IEnumerable<string> Permute(string target) { 
    if (target.Length <= 1) { 
     yield return target; 
     yield break; 
    } 
    var c = target[0]; 
    foreach (var rest in Permute(target.Remove(0, 1))) { 
     yield return c + rest; 
     yield return c + " " + rest; 
    } 
} 

Per stringa di prova produce desiderato. Fondamentalmente combiniamo prima char + spazio o senza spazio + il resto della stringa (senza primo carattere) in modo ricorsivo.

per ottenere una lista, basta fare Permute("foo").ToList();

Per stringa "ABCDE" il risultato è:

abcde 
a bcde 
ab cde 
a b cde 
abc de 
a bc de 
ab c de 
a b c de 
abcd e 
a bcd e 
ab cd e 
a b cd e 
abc d e 
a bc d e 
ab c d e 
a b c d e 

Answer 6

Un certo numero di risposte hanno suggerito soluzioni ricorsive, che va bene. Ma ecco uno schizzo di una soluzione non ricorsiva.

• Supponiamo che la tua parola ha lettere x dove x è inferiore a 64.
• Compute lungo n = 2 ^{(x - 1)}
• Fare un ciclo in cui i va da 0 a n - 1
• Decompone i nei bit bassi (x-1).
• Emettere la prima lettera.
• Se il primo bit è impostato, emettere uno spazio, altrimenti nessuno spazio.
• Emettere la seconda lettera.
• Se il secondo bit è impostato, emettere uno spazio, altrimenti nessuno spazio.
• E così via.

È possibile implementare il metodo fornito dallo schizzo?