uzyskanie wszystkich możliwych ścieżek DOWN nie i prawej krawędzi w nX n siatki

Question

Problem 15:
rozpoczynające się w górnym lewym rogu 2 x 2 siatki znajduje się 6 trasy (bez nawrotów) do dolnego prawego rogu.
Ile jest tras przez siatkę 20 × 20?

Więc moja próba Problem 15 jest trochę bruteforcy ponieważ staram się uzyskać permutacji wszystkich możliwych ważnych ścieżek przechodząc od prawej do lewej i zmieniając poprzednika pierwszej zmianie kierunku. Na przykład, gdy mam siatkę 2x2 (spójrz na grafikę łącza Problem 15) pierwszą ścieżką, którą wezmę, jest prawy - prawy - dół - dół, a ostatni, który wezmę, to w dół - w dół - w prawo - prawo, co jest również moim kryterium zakończenia. Dodaję możliwe poprawne ścieżki do listy, a także używam tej listy, aby określić, czy poprawna ścieżka została już dodana, czy nie. I aby permutować ścieżkę, zrobię to, o czym wspomniałem wcześniej: przechodzę od prawej do lewej w mojej tablicy (która na grafice będzie w prawym dolnym rogu, gdzie wskazuje grot strzałki) i zmieni pierwszy element, z którego następny element jest inny niż on sam. Tak więc w prawo - w dół - w dół stałoby się prawo - prawo - prawo - dół, co oczywiście jest nieważne, ponieważ musisz mieć taką samą liczbę praw i upadków, aby móc dotrzeć do rogu końcowego. Tak więc pomyślałem, że należy wykonać kolejną pętlę od lewej do prawej i zmienić dowolną liczbę elementów, aby uzyskać prawidłową ścieżkę. W tym przykładzie prawo - prawo - prawo - dół staje się w dół - w prawo - w prawo - w dół.

Ponadto zapomniałem, że nie liczę punktów, liczę krawędzie od lewego górnego rogu do prawego dolnego rogu.

Napisałem już jakiś kod, ale nie działa on wcale.

package projecteuler; 

import java.util.ArrayList; 

public class Projecteuler { 
    public static final int GRIDSIZE = 2; 

    public static void main(String[] args) { 
     ArrayList<boolean[]> paths = new ArrayList<>(); 

     paths.add(new boolean[GRIDSIZE * 2]); 
     for(int i = 0; i < GRIDSIZE; i++) { 
      paths.get(0)[i] = true; 
      paths.get(0)[GRIDSIZE * 2 - 1 - i] = false; 
     } 

     boolean[] buf = paths.get(0).clone(); 
     printArr(buf); 
     boolean tmp; 
     while(!checkTerminate(paths)) { 
      while(paths.contains(buf)) { 
       tmp = buf[buf.length - 1]; 
       for(int i = buf.length - 1; buf[i - 1] != tmp && 0 < i; i--) { 
        buf[i] = !buf[i]; 
        for(int j = 0; checkValid(buf) && j < i; j++) 
         buf[j] = !buf[j]; 
       } 
      } 
      paths.add(buf.clone()); 
      printArr(buf); 
     } 
     System.out.println(paths.size()); 
    } 

    public static boolean checkTerminate(ArrayList<boolean[]> paths) { 
     boolean[] endPath = new boolean[GRIDSIZE * 2]; 
     for(int i = 0; i < GRIDSIZE; i++) { 
      endPath[i] = false; 
      endPath[GRIDSIZE * 2 - 1 - i] = true; 
     } 
     return paths.contains(endPath); 
    } 

    public static boolean checkValid(boolean[] arr) { 
     int countR = 0, 
      countL = 0; 
     for(int i = 0; i < arr.length; i++) 
      if(arr[i]) 
       countR++; 
      else 
       countL++; 

     return countR == countL; 
    } 

    public static void printArr(boolean[] arr) { 
     for(int i = 0; i < arr.length; i++) 
      System.out.print(arr[i] ? "right " : "down "); 
     System.out.println(); 
    } 
} 

To nigdzie niczego nie zmienia.

right right down down 
right right down down 
right right down down 
right right down down ... 

i tak dalej jest wszystko, co wypuszcza. Wydaje się, że kod po prostu nie permutuje mojej ścieżki, ale też nie utknął w żadnej z pętli for. Domyślam się, że moje kryteria funkcji są umieszczone w niewłaściwej kolejności

Pomyślałem także o rozwiązaniu z cofaniem się, tak jak zrobiliśmy to w labiryncie dwa lata temu w szkole, ale chcę sprawdzić, czy to podejście jest w dowolnym miejscu lub nie przed powtórką wszystko.

EDIT:
postaram się wdrożyć obrazy przykładzie siatki 2 x 2 jak najszybciej, ale na stronie internetowej pod maintainance Projekt Euler jest w tej chwili.

Answer 1

Rozwiązaniem jest liczba kombinacji ruchów "w dół" i "w prawo", jakie możemy mieć. Ponieważ nie ma cofania, występuje ruch N w dół i N ruchów w prawo (na dowolnej trasie, dla siatki NxN). Łącznie występuje ruch 2N.

Można je uzyskać za pomocą dwumianowego współczynnik, ⁿ C _R (wym „n wybrać R”), który jest szereg sposobów wyboru r obiektów z n obiektów (z których każdy może być dwie rzeczy). W naszym przypadku "obiekt" jest ruchem w dół lub w prawo. To jest podana przez

Zatem liczba chcemy to:

Dla N = 2 daje 6. Dla N = 20 daje to 137846528820.

Answer 2

Niech krok w prawo być określany jako R i krok w dół jest określany jako D.

W celu dotarcia z lewego górnego rogu do prawego dolnego rogu na wiersze i kolumny siatki m, będziesz trzeba iść w prawo m razy i zejść n razy.

Zasadniczo trzeba będzie uzyskać wszystkie możliwe aranżacje R m i n D's.

---

Przykład: Dla 2 przez 2 siatki, liczba unikalnych permutacji słowa RRDD będzie wiele sposobów, w którym można przejść, a mianowicie.

• RRDD
• RDRD
• DRDR
• RDRR

---

Google formuła do obliczania permutacji liter z powtarzaniem, która jest dana przez:

n!/(r ! * r ! ...), gdzie suma wszystkich r jest n.

This question na Math SE wyskakuje jako pierwszy, gdy szuka liczba powtórzeń list permutacji, a second answer wyjaśnia lepiej moim zdaniem.

---

Aby zwrócić liczbę, a nawet zwrócić ścieżki, nie trzeba w ogóle przechodzić przez labirynt. Po prostu wykonaj obliczenie formuły dla pierwszego i wydrukuj permutacje dla drugiego problemu.

Podanie ścieżek, gdy pewne kroki są wyłączone, to jedyny przypadek, który wymaga przejścia przez labirynt.

---

UPDATE:

Pomaga wyobrazić wzór na permutacji powtarzających literami.

Oto slajd demonstrujący tę sprawę. Zobacz, jak 2 E w końcu powtarza układy podczas generowania permutacji. Zasadniczo każda litera, która jest powtarzana r razy spowoduje r! powielanie, ponieważ wszędzie tam, gdzie układa się tę literę, można ją zastąpić inną taką samą literą bez podawania nowej permutacji.

W ten sposób, jeśli podzielimy całość n! permutacje z r!, otrzymujemy faktyczne unikalne permutacje.

_{Image Source}