Karty – omówienie rozwiązania

O co chodzi w zadaniu?

Dostajemy liczbę n i pewną permutację, czyli po prostu ciąg różnych liczb od 1 do n. Naszym zadaniem jest wygenerowanie następnej permutacji w porządku leksykograficznym (czyli takim jak alfabetyczny) lub wypisanie słowa „BRAK”, gdy otrzymany ciąg jest ostatnią z nich.

Jak się za to zabrać?

Spójrzmy na kilka przykładowych par kolejnych permutacji:

           1 4 2 8 7 6 5 3               ->                       1 4 3 2 5 6 7 8

           2 3 1 4                             ->                       2 3 4 1

           5 4 3 2 1                          ->                       BRAK

Zauważmy, że permutacja jest ostatnią, jeśli jej kolejne liczby układają się w ciąg malejący. Więc jeśli rozpatrywana permutacja nie jest ostatnia, musi być liczba która łamie tę zasadę. Spójrzmy jeszcze raz na pierwszy przykład:

1 4 2 8 7 6 5 3

Jak można zauważyć, pierwsza liczba od prawej, której prawy sąsiad jest większy to 2. następnie znajdujemy pierwszą liczbę, która jest od niej większa (bo chcemy “zwiększyć” tę permutację o najmniejszą wartość) i zamieniamy je miejscami. Otrzymujemy coś takiego:

1 4 3 8 7 6 5 2

Liczby znajdujące się za zamienioną (wyżej wytłuszczone) tworzą ciąg malejący. Dzieje się tak, ponieważ wcześniej nie znaleźliśmy tam liczby, która łamię zasadę ciągu malejącego, a „nowa” liczba jest mniejsza niż wyjściowa. Żeby otrzymać odpowiedź wystarczy go obrócić:

1 4 3 2 5 6 7 8

Link do kodu

https://ideone.com/Xv1xys

Autor: Daniel Wujkowski

Dodaj komentarz

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

*