कैसे हर संभव एक मैट्रिक्स में आसन्न अक्षरों का प्रयोग कर शब्द को खोजने के लिए

Question

मैं निम्नलिखित परीक्षण मैट्रिक्स है:

 
a l i 
g t m 
j e a 

मैं एक एल्गोरिथ्म मेरे लिए किसी दिए गए न्यूनतम लंबाई से हर संभव शब्द खोजने में मदद करता है कि बनाने के लिए करना चाहते हैं केवल आसन्न अक्षरों का उपयोग कर अधिकतम लंबाई।

उदाहरण के लिए:

न्यूनतम: 3 अक्षरों

अधिकतम: 6 पत्र

परीक्षण मैट्रिक्स के आधार पर, मैं निम्नलिखित परिणाम होना चाहिए:

• अली
• एएलएम
• alg
• alt
• अति
• एटीएम
• ATG
• ...
• atmea

आदि

मेरे द्वारा बनाए गए एक परीक्षण कोड (सी #) एक कस्टम है वर्ग जो पत्रों का प्रतिनिधित्व करता है।

प्रत्येक पत्र अपने पड़ोसियों को जानता है और पीढ़ी के काउंटर (ट्रैवर्सल के दौरान उनका ट्रैक रखने के लिए) है।

public class Letter 
{ 
    public int X { get; set; } 
    public int Y { get; set; } 

    public char Character { get; set; } 

    public List<Letter> Neighbors { get; set; } 

    public Letter PreviousLetter { get; set; } 

    public int Generation { get; set; } 

    public Letter(char character) 
    { 
     Neighbors = new List<Letter>(); 
     Character = character; 
    } 

    public void SetGeneration(int generation) 
    { 
     foreach (var item in Neighbors) 
     { 
      item.Generation = generation; 
     } 
    } 
} 

मैं पता लगा कि अगर मैं इसे गतिशील होना चाहता हूँ, यह प्रत्यावर्तन के आधार पर किया जाना है:

यहाँ अपने कोड है।

दुर्भाग्यवश, निम्न कोड पहले 4 शब्द बनाता है, फिर बंद हो जाता है। यह कोई आश्चर्य की बात नहीं है, क्योंकि निर्दिष्ट पीढ़ी के स्तर से रिकर्सन रोक दिया गया है।

मुख्य समस्या यह है कि रिकर्सन केवल एक स्तर देता है लेकिन शुरुआती बिंदु पर वापस जाना बेहतर होगा।

private static void GenerateWords(Letter input, int maxLength, StringBuilder sb) 
    { 
     if (input.Generation >= maxLength) 
     {    
      if (sb.Length == maxLength) 
      { 
       allWords.Add(sb.ToString()); 
       sb.Remove(sb.Length - 1, 1); 
      }     
      return; 
     } 
     sb.Append(input.Character); 
     if (input.Neighbors.Count > 0) 
     { 
      foreach (var child in input.Neighbors) 
      { 
       if (input.PreviousLetter == child) 
        continue; 
       child.PreviousLetter = input; 
       child.Generation = input.Generation + 1; 
       GenerateWords(child, maxLength, sb); 
      } 
     } 
    } 

तो, मुझे थोड़ा फंस लगता है, कोई विचार है कि मुझे आगे कैसे बढ़ना चाहिए?

Answer 1

यहां से, आप इसे ग्राफ ट्रैवर्सल समस्या के रूप में देख सकते हैं। आप प्रत्येक दिए गए पत्र से शुरू करते हैं, लंबाई के प्रत्येक पथ को min_size से max_size, 3 और 6 के साथ अपने उदाहरण में उन मानों को ढूंढते हैं। मैं एक पुनरावर्ती दिनचर्या का सुझाव देता हूं जो शब्दों को ग्रिड के माध्यम से पथ बनाता है। यह कुछ जैसा दिखता है; अपनी वरीयताओं के साथ प्रकार और छद्म कोड को प्रतिस्थापित करें।

<array_of_string> build_word(size, current_node) { 
    if (size == 1) return current_node.letter as an array_of_string; 
    result = <empty array_of_string> 
    for each next_node in current_node.neighbours { 
     solution_list = build_word(size-1, next_node); 
     for each word in solution_list { 
      // add current_node.letter to front of that word. 
      // add this new word to the result array 
     } 
    } 
    return the result array_of_string 
} 

क्या यह आपको समाधान के लिए ले जाता है?

Answer 2

इस तरह की समस्याओं को हल करते समय, मैं अपरिवर्तनीय कक्षाओं का उपयोग करता हूं क्योंकि सब कुछ कारण के लिए इतना आसान है। निम्नलिखित कार्यान्वयन विज्ञापन hocImmutableStack का उपयोग करता है क्योंकि यह एक को लागू करने के लिए बहुत सरल है। उत्पादन कोड में मैं संभवतः प्रदर्शन सुधारने के लिए System.Collections.Immutable में देखना चाहता हूं (visited स्पष्ट मामले को इंगित करने के लिए ImmutableHashSet<> होगा)।

तो मुझे एक अपरिवर्तनीय ढेर की आवश्यकता क्यों है? वर्तमान चरित्र पथ का ट्रैक रखने के लिए और मैट्रिक्स के अंदर "स्थान" का दौरा किया। चूंकि नौकरी के लिए चयनित उपकरण अपरिवर्तनीय है, इसे रिकर्सिव कॉल नीचे भेजना कोई ब्रेनर नहीं है, हम जानते हैं कि यह नहीं बदला जा सकता है इसलिए मुझे प्रत्येक पुनरावर्तन स्तर में अपने आविष्कारों के बारे में चिंता करने की ज़रूरत नहीं है।

तो एक अपरिवर्तनीय ढेर को लागू करने दें।

हम भी एक सहायक वर्ग Coordinates कि हमारे मैट्रिक्स अंदर "स्थान" समाहित लागू करेंगे, हमें समानता और शब्दार्थ लिए एक सुविधाजनक तरीका किसी विशेष स्थान पर की वैध पड़ोसियों प्राप्त करने के लिए मूल्य दे देंगे। यह स्पष्ट रूप से काम में आ जाएगा।

public class ImmutableStack<T>: IEnumerable<T> 
{ 
    private readonly T head; 
    private readonly ImmutableStack<T> tail; 

    public static readonly ImmutableStack<T> Empty = new ImmutableStack<T>(default(T), null); 
    public int Count => this == Empty ? 0 : tail.Count + 1; 

    private ImmutableStack(T head, ImmutableStack<T> tail) 
    { 
     this.head = head; 
     this.tail = tail; 
    } 

    public T Peek() 
    { 
     if (this == Empty) 
      throw new InvalidOperationException("Can not peek an empty stack."); 

     return head; 
    } 

    public ImmutableStack<T> Pop() 
    { 
     if (this == Empty) 
      throw new InvalidOperationException("Can not pop an empty stack."); 

     return tail; 
    } 

    public ImmutableStack<T> Push(T value) => new ImmutableStack<T>(value, this); 

    public IEnumerator<T> GetEnumerator() 
    { 
     var current = this; 

     while (current != Empty) 
     { 
      yield return current.head; 
      current = current.tail; 
     } 
    } 

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); 
} 

struct Coordinates: IEquatable<Coordinates> 
{ 
    public int Row { get; } 
    public int Column { get; } 

    public Coordinates(int row, int column) 
    { 
     Row = row; 
     Column = column; 
    } 

    public bool Equals(Coordinates other) => Column == other.Column && Row == other.Row; 
    public override bool Equals(object obj) 
    { 
     if (obj is Coordinates) 
     { 
      return Equals((Coordinates)obj); 
     } 

     return false; 
    } 

    public override int GetHashCode() => unchecked(27947^Row^Column); 

    public IEnumerable<Coordinates> GetNeighbors(int rows, int columns) 
    { 
     var increasedRow = Row + 1; 
     var decreasedRow = Row - 1; 
     var increasedColumn = Column + 1; 
     var decreasedColumn = Column - 1; 
     var canIncreaseRow = increasedRow < rows; 
     var canIncreaseColumn = increasedColumn < columns; 
     var canDecreaseRow = decreasedRow > -1; 
     var canDecreaseColumn = decreasedColumn > -1; 

     if (canDecreaseRow) 
     { 
      if (canDecreaseColumn) 
      { 
       yield return new Coordinates(decreasedRow, decreasedColumn); 
      } 

      yield return new Coordinates(decreasedRow, Column); 

      if (canIncreaseColumn) 
      { 
       yield return new Coordinates(decreasedRow, increasedColumn); 
      } 
     } 

     if (canIncreaseRow) 
     { 
      if (canDecreaseColumn) 
      { 
       yield return new Coordinates(increasedRow, decreasedColumn); 
      } 

      yield return new Coordinates(increasedRow, Column); 

      if (canIncreaseColumn) 
      { 
       yield return new Coordinates(increasedRow, increasedColumn); 
      } 
     } 

     if (canDecreaseColumn) 
     { 
      yield return new Coordinates(Row, decreasedColumn); 
     } 

     if (canIncreaseColumn) 
     { 
      yield return new Coordinates(Row, increasedColumn); 
     } 
    } 
} 

ठीक है, अब हम एक विधि है कि मैट्रिक्स एक बार शब्द पात्रों में से एक निर्धारित न्यूनतम संख्या है और एक निर्दिष्ट अधिकतम से अधिक नहीं है कि लौटने प्रत्येक स्थिति का दौरा पार करता जरूरत है।

public static IEnumerable<string> GetWords(char[,] matrix, 
              Coordinates startingPoint, 
              int minimumLength, 
              int maximumLength) 

यह सही दिखता है। अब, जब recursing हम क्या पात्रों हम अपने द्वारा देखे गए का ट्रैक रखने की जरूरत है, यही कारण है कि हमारे अपरिवर्तनीय ढेर का उपयोग कर आसान है, इसलिए हमारे पुनरावर्ती विधि तरह दिखेगा:

static IEnumerable<string> getWords(char[,] matrix, 
            ImmutableStack<char> path, 
            ImmutableStack<Coordinates> visited, 
            Coordinates coordinates, 
            int minimumLength, 
            int maximumLength) 

अब बाकी बस पाइपलाइन है और तारों को जोड़ने:

public static IEnumerable<string> GetWords(char[,] matrix, 
              Coordinates startingPoint, 
              int minimumLength, 
              int maximumLength) 
    => getWords(matrix, 
       ImmutableStack<char>.Empty, 
       ImmutableStack<Coordinates>.Empty, 
       startingPoint, 
       minimumLength, 
       maximumLength); 


static IEnumerable<string> getWords(char[,] matrix, 
            ImmutableStack<char> path, 
            ImmutableStack<Coordinates> visited, 
            Coordinates coordinates, 
            int minimumLength, 
            int maximumLength) 
{ 
    var newPath = path.Push(matrix[coordinates.Row, coordinates.Column]); 
    var newVisited = visited.Push(coordinates); 

    if (newPath.Count > maximumLength) 
    { 
     yield break; 
    } 
    else if (newPath.Count >= minimumLength) 
    { 
     yield return new string(newPath.Reverse().ToArray()); 
    } 

    foreach (Coordinates neighbor in coordinates.GetNeighbors(matrix.GetLength(0), matrix.GetLength(1))) 
    { 
     if (!visited.Contains(neighbor)) 
     { 
      foreach (var word in getWords(matrix, 
              newPath, 
              newVisited, 
              neighbor, 
              minimumLength, 
              maximumLength)) 
      { 
       yield return word; 
      } 
     } 
    } 
} 

और हम कर चुके हैं। क्या यह सबसे सुरुचिपूर्ण या सबसे तेज़ एल्गोरिदम है? शायद नहीं, लेकिन मुझे यह सबसे समझने योग्य और इसलिए बनाए रखने योग्य लगता है। उम्मीद है कि यह आपकी मदद करता है।

अद्यतन नीचे टिप्पणी के आधार पर, मैं कुछ परीक्षण मामलों दौड़े हैं जिनमें से एक है:

var matrix = new[,] { {'a', 'l'}, 
         {'g', 't'} }; 
var words = GetWords(matrix, new Coordinates(0,0), 2, 4); 
Console.WriteLine(string.Join(Environment.NewLine, words.Select((w,i) => $"{i:00}: {w}"))); 

और परिणाम की उम्मीद है:

00: ag 
01: agl 
02: aglt 
03: agt 
04: agtl 
05: at 
06: atl 
07: atlg 
08: atg 
09: atgl 
10: al 
11: alg 
12: algt 
13: alt 
14: altg