LINQ - क्या यह बैकट्रैक कर सकता है?

Question

मैं LINQ के साथ गड़बड़ कर रहा हूं और मुझे यह देखने के लिए उत्सुकता है कि मैं इसके साथ क्या कर सकता हूं। मैं जानना चाहता हूं कि LINQ क्वेरी होना संभव है जो परिणामी सेट पर एक शर्त लगाता है। उदाहरण के लिए, मान लें कि मेरे पास कई शब्दों की एक सूची है, और मैं उन शब्दों के सेट ढूंढना चाहता हूं जो एक श्रृंखला बनाते हैं (यानी शब्द का अंतिम अक्षर = अगले शब्द का पहला अक्षर, श्रृंखला में पहले या अंतिम शब्द पर कोई बाधा नहीं) । कुछ "हैलो, पुराना, डेयरी, पीला, दुनिया ..." जैसा कुछ।

इन सेटों से, मैं उस सेट को लेना चाहता हूं जो सबसे लंबी श्रृंखला बनाती है।

क्या LINQ ऐसा कुछ कर सकता है?

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

Answer 1

LINQ लगभग कुछ भी कर सकते हैं - हालांकि मैं एक बाधा है कि शब्द ही किसी भी श्रृंखला में एक बार दिखाई दे सकता है अन्यथा मैं ढेर अतिप्रवाह त्रुटियों हो रही है लागू करने के लिए किया था।

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

अधिकतम लंबाई श्रृंखला प्राप्त करने के लिए मैं इसे आपके लिए छोड़ दूंगा। यह आपके प्रश्न से स्पष्ट नहीं था कि श्रृंखला की लंबाई शब्दों की संख्या की गणना है या यदि यह समेकित शब्दों की वर्ण लंबाई है।

यहाँ पिछले 8 कि उपरोक्त कोड से उत्पन्न हो गया है:

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 

का आनंद लें।

---

रोली एक "prolog उलटे पांव लौटने एल्गोरिथ्म" के और अधिक चाहता था - हालांकि उनके सवाल यह नहीं कहा! ;-)

संदेश यह है:

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

इस विधि पुनरावर्तक विधि, CLR ढेर, और पुनरावर्ती कॉल का उपयोग करके उलटे पांव लौटने से किया जाता है। प्रोलॉग यह और अधिक सुंदरता से करेगा, लेकिन यह पता चला है कि इस विधि की संभावित दक्षता पर मेरी टिप्पणी गलत थी। यह वास्तव में मेरी पहली विधि से लगभग दो गुना तेज है।

मुझे यह भी लगता है कि यह दूसरी विधि "शुद्ध" LINQ के उपयोग से आगे बढ़ रही है, लेकिन यह क्लीनर, छोटी और अधिक कुशल है। मुझे पता है कि मैं इस संस्करण को बनाए रखना चाहता हूं।

ओह, Working वर्ग (काम कर रहे राज्य को ट्रैक किया जाता) अनिवार्य रूप से यह है:

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

इस दृष्टिकोण से उत्पादन स्पष्ट रूप से पता चलता है कि यह उलटे पांव लौटने से किया जाता है:

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

नहीं