Next Permutation

Q: Jaka jest złożoność czasowa algorytmu Next Permutation?

O(n) . Jedno przejście od prawej strony znajduje punkt obrotu, drugie znajduje wartość, którą należy zamienić, a jedno odwrócenie naprawia końcowy fragment tablicy. Dodatkowa pamięć wynosi O(1) , ponieważ wszystko odbywa się wewnątrz tablicy.

ŚrednieTablice i napisy Dwa wskaźniki

+10

Otrzymujesz tablicę liczb całkowitych nums, a wartości mogą się powtarzać. Wyobraź sobie wszystkie różne układy tych wartości, uporządkowane alfabetycznie: porównaj dwa układy przy pierwszym indeksie, na którym się różnią, a układ z mniejszą wartością w tym miejscu występuje wcześniej. Zwróć układ, który w tej kolejności występuje bezpośrednio po nums.

Jeśli nums jest już największym układem, nie ma następnego: zwróć najmniejszy, czyli wartości posortowane rosnąco. Dąż do złożoności czasowej O(n) i O(1) dodatkowej pamięci.

Funkcja

nextPermutation(nums: integer-array) → integer-array

numsinteger-array: obecny układ wartości
Zwracainteger-array: następne ułożenie w porządku słownikowym lub wartości posortowane rosnąco, jeśli nums jest największe

Ograniczenia

1 ≤ nums.length ≤ 5000
0 ≤ nums[i] ≤ 1000

Przykłady

Wejście: nums = [2, 5, 4, 1]
Wyjście: [4, 1, 2, 5]
Wyjaśnienie: Ogon 5, 4, 1 opada, więc 2 przed nim musi urosnąć. Najmniejsza wartość ogona większa od 2 to 4; umieść ją tam, a resztę w kolejności rosnącej: [4, 1, 2, 5].

Wejście: nums = [3, 2, 2, 1]
Wyjście: [1, 2, 2, 3]
Wyjaśnienie: Cała tablica spada, więc jest to największe uporządkowanie liczb 3, 2, 2 i 1. Odpowiedź zawija się do najmniejszego uporządkowania: [1, 2, 2, 3].

Wejście: nums = [1, 5, 1]
Wyjście: [5, 1, 1]
Wyjaśnienie: Pierwsza 1 musi wzrosnąć. Ostatnia 1 jest jej równa, a nie większa, więc jedyną wartością, która może ją zastąpić, jest 5, co daje [5, 1, 1].

Pytanie dodatkowe

Jak znaleźć poprzednie uporządkowanie, czyli to, które w kolejności słownikowej znajduje się bezpośrednio przed nums?

Rozwiązanie

Malejący sufiks jest już tak duży, jak pozwalają na to jego wartości, więc następne uporządkowanie zmienia wartość bezpośrednio przed nim — element przestawiany. Zwiększ wartość tego elementu o najmniejszą możliwą wartość, a następnie zmniejsz sufiks tak bardzo, jak to możliwe. Wymaga to dwóch przejść od prawej strony i jednego odwrócenia w tablicy.

Ułóż elementy listy w kolejności

Poprawne, ale nie kończy się na największych testach

Intuicja

Buduj ułożenia metodą przeszukiwania w głąb, zaczynając od posortowanych wartości i zawsze najpierw próbując najmniejszej nieużytej wartości. Dzięki temu powstają w kolejności słownikowej, więc pierwsze ułożenie ściśle większe niż nums jest odpowiedzią; jeśli takiego nie ma, zwróć posortowane wartości. Powtarzające się wartości tworzą niektóre ułożenia dwukrotnie, jak w przypadku 115, 151, 115, 151, 511, 511 dla [1, 1, 5], ale kopia powtarza tylko ułożenie utworzone wcześniej, więc pierwsze większe nadal jest kolejnym.

Liczba ułożeń rośnie jak n!: 12 różnych wartości daje 479,001,600 ułożeń.

Algorytm

Posortuj kopię nums do pool.
Buduj ułożenia metodą w głąb, wybierając nieużyte elementy pool od lewej do prawej.
Gdy ułożenie będzie gotowe, porównaj je z nums pozycja po pozycji.
Zwróć pierwsze ułożenie, które jest większe niż nums.
Jeśli żadne nie jest większe, zwróć pool.

def nextPermutation(nums):
    n = len(nums)
    pool = sorted(nums)  # taking the smallest unused value first gives sorted order
    used = [False] * n
    current = []

    def build():
        # True once current holds the first arrangement greater than nums
        if len(current) == n:
            return current > nums  # Python compares lists in dictionary order
        for i in range(n):
            if not used[i]:
                used[i] = True
                current.append(pool[i])
                if build():
                    return True
                current.pop()
                used[i] = False
        return False

    if build():
        return current
    return pool  # nothing is greater: nums was the largest arrangement

Znajdź element przestawny, zamień miejscami, odwróć sufiks

Intuicja

Pivotem jest pierwsza od prawej wartość mniejsza od swojego prawego sąsiada: 2 w [2, 5, 4, 1]. To najbardziej wysunięta w prawo pozycja, którą można zwiększyć, a zwiększenie najbardziej wysuniętej w prawo możliwej pozycji zapewnia najmniejszy wzrost.

Zamień pivot z najmniejszą wartością w sufiksie, która jest od niego ściśle większa. Sufiks jest malejący, więc jest to najbardziej wysunięta w prawo wartość większa od pivota: 4, co daje [4, 5, 2, 1]. Sufiks nadal jest malejący, ponieważ stary pivot pasuje w miejsce, w którym było 4. Teraz, gdy początek jest większy, sufiks powinien być jak najmniejszy, w kolejności rosnącej, a odwrócenie malejącego ciągu to zapewnia: [4, 1, 2, 5].

Gdy nie ma pivota, tablica jest największym możliwym układem, a odwrócenie jej całej daje najmniejszy. Każdy krok wymaga jednego przejścia lub jednego odwrócenia: czas O(n) i pamięć O(1), choć wersja R zwraca kopię o rozmiarze O(n).

Algorytm

Ustaw i na n-2 i przesuwaj go w lewo, dopóki nums[i] ≥ nums[i + 1].
Jeśli i ≥ 0, ustaw j na n-1 i przesuwaj go w lewo, dopóki nums[j] ≤ nums[i], a następnie zamień miejscami nums[i] i nums[j].
Odwróć część od i + 1 do końca, używając dwóch indeksów przesuwających się ku sobie.
Zwróć nums.

def nextPermutation(nums):
    n = len(nums)
    # 1. the pivot is the last index whose value is smaller than the next one
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        # 2. swap it with the rightmost value that is larger than it
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    # 3. the suffix after the pivot is falling: reverse it to make it rising
    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1
    return nums

Pułapki i przypadki brzegowe

Użycie > zamiast ≥ podczas wyszukiwania pivota. W [3, 2, 2, 1] para 2, 2 nie oznacza wzrostu, a zatrzymanie się w tym miejscu wybiera pivot, którego nie da się zwiększyć.
Zamiana z wartością równą pivotowi. W [1, 5, 1] zamiana dwóch jedynek niczego nie zmienia; szukaj wartości ściśle większej.
Zamiana z największą wartością w sufiksie. W [2, 5, 4, 1] umieszcza to 5 z przodu i pomija wszystkie układy zaczynające się od 4.
Pominięcie przypadku bez pivota. Największy układ musi wrócić posortowany — w tym celu odwróć całą tablicę.
W Rust indeks usize zaczynający się od n-2 powoduje panikę, gdy n = 1, a przejście w lewo poza 0 powoduje panikę, gdy nie ma pivota. Użyj indeksu ze znakiem albo odliczaj od 1.

Najczęstsze pytania3

Jaka jest złożoność czasowa algorytmu Next Permutation?

O(n). Jedno przejście od prawej strony znajduje punkt obrotu, drugie znajduje wartość, którą należy zamienić, a jedno odwrócenie naprawia końcowy fragment tablicy. Dodatkowa pamięć wynosi O(1), ponieważ wszystko odbywa się wewnątrz tablicy.

Dlaczego odwracasz przyrostek zamiast go sortować?

Po zamianie sufiks nadal jest malejący, więc jego odwrócenie już sortuje go w kolejności rosnącej. Odwrócenie zajmuje O(n); sortowanie daje ten sam wynik w O(n log n).

Czy algorytm Next Permutation działa z powtarzającymi się wartościami?

Tak, o ile oba porównania traktują równe wartości jako nienależące do większych. Wyszukiwanie pivota pomija równych sąsiadów za pomocą ≥, a wyszukiwanie elementu do zamiany pomija wartości równe pivotowi za pomocą ≤. Wtedy [1, 5, 1] zmienia się w [5, 1, 1], czyli następne różne uporządkowanie.

def nextPermutation(nums):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argument

nums = [2, 5, 4, 1]

Oczekiwany wynik

[4, 1, 2, 5]