/ / Generowanie zestawu permutacji ze względu na zestaw liczb i niektóre warunki na względnych pozycjach elementów - algorytm, permutacja, kombinatoryka, backtracking

Generowanie zestawu permutacji z podaniem zbioru liczb i niektórych warunków dotyczących względnych pozycji elementów - algorytm, permutacja, kombinatoryka, cofanie

Szukam algorytmu, który, biorąc pod uwagę zestawliczb {0, 1, 2, 4, 5 ...} i zestaw warunków dotyczących względnych pozycji każdego elementu, sprawdzi, czy istnieje prawidłowa permutacja. Warunki są zawsze typu "Element na pozycji i w oryginalnej tablicy musi być następny (sąsiadujący) z elementem w pozycji j lub z".
Ostatni i pierwszy element w permutacji są uważane za sąsiednie.

Oto prosty przykład:

Niech liczby będą {0, 1, 2, 3}
i zestaw warunków: a0 musi znajdować się obok a1, a0 musi znajdować się obok a2, a3 musi znajdować się obok a1
Prawidłowym rozwiązaniem tego przykładu będzie {0,1,3,2}.

Zauważ, że każdy obrót / symetria tego rozwiązania jest również prawidłowym rozwiązaniem. Muszę tylko udowodnić, że takie rozwiązanie istnieje.

Inny przykład korzystania z tego samego zestawu:
a0 musi znajdować się obok a1, a0 musi znajdować się obok a3, a0 musi znajdować się obok a2.

Nie ma poprawnego rozwiązania dla tego przykładu, ponieważ liczba może przylegać tylko do 2 liczb.

Jedyny pomysł, jaki mogę teraz wymyślić, to użyć jakiegoś rodzaju cofnięcia.
Jeśli istnieje rozwiązanie, powinno to być cicheszybki. Jeśli nie istnieje rozwiązanie, nie wyobrażam sobie żadnego sposobu na uniknięcie sprawdzenia wszystkich możliwych permutacji. Jak już powiedziałem, obrót lub symetria nie wpływa na wynik dla danej permutacji, dlatego powinno być możliwe zmniejszenie liczby możliwości.

Odpowiedzi:

1 dla odpowiedzi № 1

Sformułuj to jako problem z wykresem. Połącz każdą parę liczb, które muszą znajdować się obok siebie. Będziesz musiał skończyć z wieloma połączonymi komponentami. Każdy komponent ma wiele permutacji (pozwala nazywać je mini-permutacjami), a ty możesz mieć permutację komponentów.

Podczas tworzenia wykresu upewnij się, że każdy komponent jest zgodny z wieloma regułami: bez cykli, bez wierzchołków z więcej niż dwoma wierzchołkami itd.


1 dla odpowiedzi nr 2

Zasadniczo chcesz wiedzieć, czy możesz tworzyćłańcuchy liczb. Każdą liczbę należy umieścić w łańcuchu, który śledzi liczbę i do dwóch sąsiadów. Użyj reguł, aby połączyć łańcuchy. Kiedy dołączysz do dwóch łańcuchów, skończysz z łańcuchem z dwoma luźnymi końcami (sąsiadami) Jeśli uda ci się przejść przez wszystkie zasady bez wyczerpania luźnych końców to działa.


0 dla odpowiedzi № 3

Wprowadziłem rozwiązanie graficzne z niewielkimi modyfikacjami.

Jeśli węzeł ma zbyt wielu sąsiadów, algorytmspadłby jeden brzeg i ponownie sprawdził wykres. Następnie wycofuję się i sprawdzam, czy możliwe jest upuszczenie następnej krawędzi ... Ta metoda daje ten sam wynik, co metoda brute force, którą napisałem.

Pod względem złożoności rozwiązanie to wydaje się byćjest lepsza niż brutalna siła, chociaż nie mogę jej uruchomić na więcej niż 20 liczbach (tylko 8 dla brutalnej siły). W sensie jest to logiczne, ponieważ taki wykres może faktycznie wygenerować podzbiór prawidłowej permutacji na raz, plus w w najgorszym przypadku jest to odpowiednik znalezienia niektórych kompozycji na zbiorze krawędzi, mimo wszystko wraca.

Biorąc pod uwagę, że obrót nie ma żadnego wpływuWażność permutacji, myślałem o ustaleniu a0 w pierwszej pozycji (Można to osiągnąć przez proste obrócenie poprawnej permutacji do momentu, gdy a0 znajduje się na pierwszej pozycji), a następnie spróbuj zbudować rozwiązanie z tego miejsca.

Używając DP, mogę dostać coś lepszego niż wykładnicza złożoność. Ale muszę powiedzieć, że nadal nie jestem pewien, od czego zacząć :)