Ja wpadłem na coś takiego:
Powiedzmy, że liczysz tę najkrótszą trasę (http://en.wikipedia.org/wiki/File:Catalan_number_4x4_grid_example.svg). Przyporządkujmy trasom liczby (czy tablicę) w następujący sposób: 000, 001, 002, 011, 111, 012, 003, 112, 022, 013, 023, 113, 122, 123.
Wygenerować kolejną sekwencję zaczynając z danej można następująco:
Zaczynamy od końca. Jeżeli możemy dodać jeden do liczby na danej pozycji to to robimy, jest to możliwe gdy liczba na danej pozycji jest mniejsza niż indeks pozycja oraz przypisujemy tę liczbę na każdej następującej pozycji. Jeżeli nie możemy dodać zmniejszamy indeks o jeden. Przykładowo następnik 023 robimy tak:
Na pozycji 3 jest 3, nie możemy dodać. Sprawdzamy pozycje 2, jest 2, nie możemy dodać. Sprawdzamy pozycję 1, jest 0, możemy dodać i przypisujemy jeden wcześniej sprawdzonym pozycjom, otrzymując 111.
Zamiana na pary punktów:
W celu łatwiejszego opisu algorytmu dodajemy na początku 0 i na końcu n, czyli dla naszego przykładu mamy 01114 (oznaczone jako tab). Teraz idziemy po naszej ścieżce z punktu 0,0, co oznaczę przez row=0, col=0 (teraz numeruje pozycje od 0, nie od 1 jak wcześniej). Num oznaczam numer punktu. Startujemy algorytm z num = 0.
Jeżeli Num jest większe równe niż 2*n kończymy algorytm. Zwiększamy num. Jeżeli tab[col] jest równe row to wrzucamy num na stos i zwiększamy col. Z kolei jeżeli row jest mniejsze, to zwiększamy row o jeden i zabieramy liczbę ze stosu, która z num tworzy parę, którą dodajemy do wyników. Czynność powtórzyć.
Dla 01114 wyjściem tego algorytmu powinien być: [(1,2),(5,6),(4,7),(3,8)]. Dla 01234 będzie [(1,2),(3,4),(5,6),(7,8)].