LINQ: può tornare indietro?

Question

Sto scherzando con LINQ e sono curioso di vedere cosa posso fare con esso. Vorrei sapere se è possibile avere una query LINQ che impone una condizione sul set risultante. Ad esempio, supponiamo di avere un elenco di più parole e desidero trovare insiemi di parole che formano una catena (cioè l'ultima lettera di una parola = prima lettera della prossima parola, nessun vincolo sulla prima o sull'ultima parola della catena) . Qualcosa come "ciao, vecchio, latte, giallo, mondo ...".

Da questi set, vorrei quindi prendere il set che forma la catena più lunga.

LINQ può fare qualcosa del genere?

var chains = (from word in words 
      select word 
      where result.IsChain()).Max(x => x.Length); 

Answer 1

LINQ può fare quasi tutto - anche se ho dovuto introdurre un vincolo che le parole possono apparire solo una volta in qualsiasi catena altrimenti ho continuato a ottenere gli errori di overflow dello stack.

var words = new[] 
{ 
    "old", "dairy", "yellow", 
    "world", "dog", "dad", 
    "yard", "yolk", "yeah", 
    "king", "weld", "goat", 
    "hello", 
}; 

Func<IEnumerable<IEnumerable<string>>, IEnumerable<string>, IEnumerable<IEnumerable<string>>> lengthenChains = (css, ws) => 
{ 
    var endsWith = from cs in css 
        select new 
        { 
         Letter = cs.Last().Last(), 
         Chain = cs, 
        }; 

    var startsWith = from w in ws 
        select new 
        { 
         Letter = w.First(), 
         Word = w, 
        }; 

    return from ew in endsWith 
      join sw in startsWith on ew.Letter equals sw.Letter 
      where ew.Chain.Contains(sw.Word) == false 
      select ew.Chain.Concat(new[] { sw.Word }); 
}; 

Func<IEnumerable<string>, IEnumerable<IEnumerable<string>>> makeChain = ws => 
     from w in ws 
     select (new[] { w, }).AsEnumerable(); 

Func<IEnumerable<IEnumerable<string>>, IEnumerable<string>, IEnumerable<IEnumerable<string>>> makeChains = null; 

makeChains = (css, ws) => 
    css.Any() 
    ? css.Concat(makeChains(lengthenChains(css, ws), ws)) 
    : Enumerable.Empty<IEnumerable<string>>(); 

var chains = from cs in makeChains(makeChain(words), words) 
      select String.Join(", ", cs.ToArray()); 

chains.Run(chain => Console.WriteLine(chain)); 

Lo lascerò per voi per ottenere la catena di lunghezza massima. Non è chiaro dalla tua domanda se la lunghezza della catena è un conteggio del numero di parole o se è la lunghezza del carattere delle parole concatenate.

Ecco gli ultimi 8 che vengono generati dal codice di cui sopra:

yellow, world, dairy, yeah, hello, old, dad, dog, goat 
yellow, world, dad, dairy, yeah, hello, old, dog, goat 
yellow, weld, dairy, yeah, hello, old, dad, dog, goat 
yellow, weld, dad, dairy, yeah, hello, old, dog, goat 
yeah, hello, old, dairy, yellow, world, dad, dog, goat 
yeah, hello, old, dairy, yellow, weld, dad, dog, goat 
yeah, hello, old, dad, dairy, yellow, world, dog, goat 
yeah, hello, old, dad, dairy, yellow, weld, dog, goat 

godere.

---

Roly voluto più di un "prologo backtracking algoritmo" - anche se la sua domanda non ha detto questo! ;-)

Eccolo:

var starting = from w in words 
       let c = (new[] { w }).AsEnumerable() 
       select new Working(c.ToArray(), words.Except(c).ToArray()); 

var chains = (from cs in Chains(starting) 
       select String.Join(", ", cs.ToArray())).ToArray(); 

IEnumerable<IEnumerable<string>> Chains(IEnumerable<Working> workings) 
{ 
    foreach (var w in workings) 
    { 
     yield return w.Chain; 
     var last = w.Chain.Last().Last(); 
     var nexts = (from r in w.Remaining 
        where r.First() == last 
        let c = (new[] { r }).AsEnumerable() 
        select new Working(w.Chain.Concat(c).ToArray(), w.Remaining.Except(c).ToArray())); 
     foreach (var chain in Chains(nexts)) 
     { 
      yield return chain; 
     } 
    } 
} 

Questo metodo viene facendo marcia indietro utilizzando un metodo iteratore, lo stack CLR, e chiamate ricorsive. Prolog lo farebbe in modo più elegante, ma risulta che il mio commento sulla probabile efficienza di questo metodo era sbagliato. In realtà è circa due volte più veloce del mio primo metodo.

Penso anche che questo secondo metodo si allontani ulteriormente dall'uso del LINQ "puro", ma è più pulito, più piccolo e più efficiente. So che preferirei mantenere questa versione.

Oh, la classe Working (utilizzato per monitorare lo stato di funzionamento) è essenzialmente questo:

class Working 
{ 
    string[] Chain { get; set; } 
    string[] Remaining { get; set; } 
} 

L'uscita da questo approccio mostra con chiarezza che è marcia indietro:

... 
yeah, hello, old, dog 
yeah, hello, old, dog, goat 
yeah, hello, old, dad 
yeah, hello, old, dad, dairy 
yeah, hello, old, dad, dairy, yellow 
yeah, hello, old, dad, dairy, yellow, world 
yeah, hello, old, dad, dairy, yellow, world, dog 
yeah, hello, old, dad, dairy, yellow, world, dog, goat 
yeah, hello, old, dad, dairy, yellow, weld 
yeah, hello, old, dad, dairy, yellow, weld, dog 
yeah, hello, old, dad, dairy, yellow, weld, dog, goat 
yeah, hello, old, dad, dairy, yard 
yeah, hello, old, dad, dairy, yard, dog 
yeah, hello, old, dad, dairy, yard, dog, goat 
yeah, hello, old, dad, dairy, yolk 
yeah, hello, old, dad, dairy, yolk, king 
yeah, hello, old, dad, dairy, yolk, king, goat 
yeah, hello, old, dad, dog 
yeah, hello, old, dad, dog, goat 
... 

non