Jak znaleźć wszystkie możliwe słowa za pomocą sąsiednie litery w matrycy

Question

Mam następującą macierz badawczej:

 
a l i 
g t m 
j e a 

zamierzam stworzyć algorytm, który pomaga mi znaleźć każdą możliwą słowo z danej minimalnej długości do maksymalna długość przy użyciu sąsiednich liter.

Na przykład:

Minimum: 3 litery

maksymalna: 6 liter

Na podstawie matrycy testowej powinien mieć następujące wyniki:

• Ali
• alm
• alg
• alt
• ati
• atm
• ATG
• ...
• atmea

itp

stworzyłem kodu testu (C#), który ma zwyczaj klasa reprezentująca litery.

Każda litera zna swoich sąsiadów i ma licznik generacji (do śledzenia ich podczas przemierzania).

Oto jego kod:

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

zorientowali się, że jeśli ma to być dynamiczna, to musi być oparte na rekurencji.

Niestety, poniższy kod tworzy pierwsze 4 słowa, a następnie zatrzymuje się. Nic dziwnego, ponieważ rekurencja jest zatrzymywana przez określony poziom generacji.

Głównym problemem jest to, że rekursja zwraca tylko jeden poziom, ale lepiej wrócić do punktu początkowego.

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

Czuję, że utknąłem, jak mam postępować?

Answer 1

Z tego miejsca można traktować to jako problem z wykresem wykresu. Zaczynasz od każdej podanej litery, znajdując każdą ścieżkę o długości min_size do max_size, z 3 i 6 jako wartościami w twoim przykładzie. Sugeruję rekurencyjną procedurę, która buduje słowa jako ścieżki przez siatkę. To będzie wyglądać jak poniżej; zamień typy i pseudokodowanie na swoje preferencje.

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

Czy to prowadzi do rozwiązania?

Answer 2

Podczas rozwiązywania tego typu problemów używam niezmiennych klas, ponieważ wszystko jest o wiele łatwiejsze do zrozumienia. Następująca implementacja korzysta z ad hocImmutableStack, ponieważ jest dość prosta w implementacji. W kodzie produkcyjnym prawdopodobnie chciałbym zaglądnąć do System.Collections.Immutable, aby poprawić wydajność (visited byłby to ImmutableHashSet<>, aby wskazać oczywisty przypadek).

Dlaczego więc potrzebuję niezmiennego stosu? Aby śledzić bieżącą ścieżkę znaków i odwiedzane "lokalizacje" wewnątrz macierzy. Ponieważ wybrane narzędzie do pracy jest niezmienne, wysłanie go w dół wywołań rekursywnych nie ma sensu, wiemy, że nie może się zmienić, więc nie muszę się martwić o moje niezmienniki na każdym poziomie rekurencji.

Pozwala więc zaimplementować niezmienny stos.

Zaimplementujemy również klasę pomocniczą Coordinates, która hermetyzuje nasze "lokalizacje" wewnątrz macierzy, da nam wartość semantyki równości i wygodny sposób na uzyskanie ważnych sąsiadów z dowolnej lokalizacji. Będzie oczywiście przydatny.

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

Ok, teraz musimy metodę, która przemierza matrycę odwiedzając każdą pozycję po powracającego słowa, które mają określoną minimalną liczbę znaków i nie przekraczają określonego maksimum.

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

To wygląda dobrze. Teraz, kiedy recursing musimy śledzić jakie znaki odwiedziliśmy, to łatwe przy użyciu naszą niezmienną stos, więc nasz rekurencyjna metoda będzie wyglądać następująco:

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

teraz reszta jest po prostu hydraulicznego i podłączania przewodów:

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

I skończymy. Czy jest to najbardziej elegancki lub najszybszy algorytm? Prawdopodobnie nie, ale uważam, że jest to najbardziej zrozumiałe i dlatego możliwe do utrzymania. Mam nadzieję, że ci to pomoże.

UPDATE oparciu komentarzach poniżej, Zabrakło mi kilka testów, z których jedna jest:

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

a wynik jest oczekiwany:

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