Permutacje, cz. 2 – algorytmy

W poprzednim wpisie programistyczne rozwiązanie zagadki polegało na wygenerowaniu wszystkich permutacji zbioru i sprawdzeniu każdej z nich pod względem spełnienia warunku poprawności. Takie podejście może okazać się najrozsądniejsze w przypadku pracy nad problemami NP-trudnymi (poprzez wygenerowanie wszystkich możliwych rozwiązań i wybranie spośród nich najlepszej).

W dalszej części umieszczam przykłady implementacji w Javie różnych algorytmów generowania permutacji.

Przed rozpoczęciem implementacji

Na początek stworzę klasę zawierającą pomocnicze metody, które będzie można wykorzystywać w dalszej części.

Koncepcja

W związku z tym, że wygenerowanie wszystkich permutacji można wykonać różnymi algorytmami, warto wyodrębnić kilka kroków aby nie DRY. Kolejną ważną uwagą jest to, by nie zapamiętywać wszystkich wyników do zewnętrznej tablicy, a wykorzystać przekazywanie wyniku do obserwatora. Dlaczego? Dlatego, że należy eliminować nieuzasadnione wykorzystywanie pamięci. Permutacja zbioru dziesięciu elementów będzie zawierała ponad trzy miliony możliwości.

Następnie można zdefiniować interfejs algorytmu generowania permutacji:

Są już zdefiniowane interfejsy nasłuchiwania i generowania permutacji. Można przygotować generator:

Dzięki wykorzystaniu wzorca strategii uruchomienie ich generowania będzie wyjątkowo proste, a każdy algorytm będzie utworzony w osobnej klasie. Kod rozpoczęcia generowania będzie wyglądał tak:

ALGORYTMY

 

Permutacje w kolejności antyleksykograficznej

 

Permutacje generowane z minimalną liczbą transpozycji

 

Permutacje generowane z minimalną liczbą transpozycji sąsiednich

Wyniki

Jako dane wejściowe posłuży zbiór liczb {1, 2, 3, 4}. Każda permutacja będzie wypisana na wyjście.

 

Poniżej wyniki wszystkich trzech algorytmów. Na czerwono zaznaczyłem elementy, które zmieniły pozycję w stosunku do poprzedniej permutacji.

LP AntylexStrategy MinTranspositionsStrategy MinAdjacentTranspositionsStrategy
1 [1, 2, 3, 4] [1, 2, 3, 4] [1, 2, 3, 4]
2 [2, 1, 3, 4] [2, 1, 3, 4] [2, 1, 3, 4]
3 [1, 3, 2, 4] [2, 3, 1, 4] [2, 3, 1, 4]
4 [3, 1, 2, 4] [3, 2, 1, 4] [2, 3, 4, 1]
5 [2, 3, 1, 4] [3, 1, 2, 4] [3, 2, 4, 1]
6 [3, 2, 1, 4] [1, 3, 2, 4] [3, 2, 1, 4]
7 [1, 2, 4, 3] [4, 3, 2, 1] [3, 1, 2, 4]
8 [2, 1, 4, 3] [3, 4, 2, 1] [1, 3, 2, 4]
9 [1, 4, 2, 3] [3, 2, 4, 1] [1, 3, 4, 2]
10 [4, 1, 2, 3] [2, 3, 4, 1] [3, 1, 4, 2]
11 [2, 4, 1, 3] [2, 4, 3, 1] [3, 4, 1, 2]
12 [4, 2, 1, 3] [4, 2, 3, 1] [3, 4, 2, 1]
13 [1, 3, 4, 2] [4, 1, 3, 2] [4, 3, 2, 1]
14 [3, 1, 4, 2] [1, 4, 3, 2] [4, 3, 1, 2]
15 [1, 4, 3, 2] [1, 3, 4, 2] [4, 1, 3, 2]
16 [4, 1, 3, 2] [3, 1, 4, 2] [1, 4, 3, 2]
17 [3, 4, 1, 2] [3, 4, 1, 2] [1, 4, 2, 3]
18 [4, 3, 1, 2] [4, 3, 1, 2] [4, 1, 2, 3]
19 [2, 3, 4, 1] [4, 2, 1, 3] [4, 2, 1, 3]
20 [3, 2, 4, 1] [2, 4, 1, 3] [4, 2, 3, 1]
21 [2, 4, 3, 1] [2, 1, 4, 3] [2, 4, 3, 1]
22 [4, 2, 3, 1] [1, 2, 4, 3] [2, 4, 1, 3]
23 [3, 4, 2, 1] [1, 4, 2, 3] [2, 1, 4, 3]
24 [4, 3, 2, 1] [4, 1, 2, 3] [1, 2, 4, 3]

To również może Cię zainteresować:

  • Permutacje i zagadka z trójkątemPermutacje i zagadka z trójkątem Rozwiąż poniższą zagadkę: Rozwiązanie i trochę o permutacjach poniżej. Jednak zachęcam spróbować samodzielnie rozwiązać to zadanie. Rozwiązanie logiczne Warunkiem poprawności jest […]
  • Programowanie i książki matematyczneProgramowanie i książki matematyczne Korzystając z okazji dzisiejszej promocji na książki matematyczne w Helionie, chciałbym zaproponować cztery pozycje dla każdego: Od matematyki do programowania ogólnego Jak napisał w […]
  • Trochę matematyki – maturaTrochę matematyki – matura Matematyka - to jedna z moich pasji. To dziedzina wiedzy, która nigdy się nie znudzi. Jest to wpis archiwalny zawierający rozwiązane przeze mnie zadania na maturze.Z ciekawostek: podczas […]
  • Bielsko-Biała JUG #4, Jarosław Pałka – JIT me baby one more time.Bielsko-Biała JUG #4, Jarosław Pałka – JIT me baby one more time. Wczoraj odbyło się czwarte spotkanie Bielsko-Bialskiej grupy miłośników Javy i programowania (Bielsko-Biała JUG). Tym razem prelekcję przygotował dla nas Jaroslaw Palka - od ponad 15 lat w […]
  • Java i listing wszystkich plików w kataloguJava i listing wszystkich plików w katalogu W ostatnim czasie musiałem przerobić jeden z systemów na wersję wielojęzykową. Chodziło dokładnie o to, aby wszystkie Stringi zostały wywołane przez tzw. wrapper ze wstrzyknięciem pewnego […]
  • Fundamenty języka JavaFundamenty języka Java Niecały miesiąc temu zostałem poproszony przez Strefę Kursów o ocenę ich nowo wydanego materiału dla osób chcących zacząć naukę programowania w Javie: "Fundamenty języka Java". Przerobiłem […]

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *