LINQ: ¿puede retroceder?

Question

Estoy jugando con LINQ y tengo curiosidad por ver qué puedo hacer con él. Me gustaría saber si es posible tener una consulta LINQ que imponga una condición sobre el conjunto resultante. Por ejemplo, digamos que tengo una Lista de varias palabras, y deseo encontrar conjuntos de palabras que forman una cadena (es decir, la última letra de una palabra = primera letra de la siguiente palabra, sin restricción en la primera o última palabra de la cadena) . Algo así como "hola, viejo, lácteo, amarillo, mundo ...".

De estos conjuntos, me gustaría tomar el conjunto que forma la cadena más larga.

¿Puede LINQ hacer algo como esto?

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

Answer 1

LINQ puede hacer casi cualquier cosa - a pesar de que tenía que introducir una restricción que las palabras sólo pueden aparecer una vez en cualquier cadena de lo contrario seguí recibiendo errores de desbordamiento de pila.

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 dejo para que usted obtenga la cadena de longitud máxima. No quedó claro a partir de su pregunta si la longitud de la cadena es un recuento de la cantidad de palabras o si es la longitud del carácter de las palabras concatenadas.

Aquí es lo último que consiguen 8 genera a partir del código anterior:

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 

disfrutar.

---

Roly quería más de un "algoritmo de retroceso de prólogo" - ¡aunque su pregunta no decía eso! ;-)

aquí está:

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

Este método está dando marcha atrás mediante el uso de un método iterador, la pila de CLR, y las llamadas recursivas. Prolog haría esto de manera más elegante, pero resulta que mi comentario sobre la probable eficacia de este método era incorrecto. En realidad, es aproximadamente dos veces más rápido que mi primer método.

También creo que este segundo método se está alejando del uso de LINQ "puro", pero es más limpio, más pequeño y más eficiente. Sé que preferiría mantener esta versión.

Oh, la clase Working (utilizado para realizar el seguimiento del estado de trabajo) es esencialmente la siguiente:

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

La salida de este enfoque muestra claramente que está dando marcha atrás:

... 
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 
... 

no