Permutations

+10

Kamu mendapatkan sebuah list nums yang berisi bilangan bulat berbeda. Kembalikan setiap urutan nilai tersebut, masing-masing sebagai list yang menggunakan setiap nilai tepat satu kali, sehingga n nilai menghasilkan n! urutan. Urutkan dalam urutan leksikografis: bandingkan dua urutan posisi demi posisi, dan biarkan perbedaan pertama menentukan urutannya. Untuk [1, 2, 3], urutan [1, 2, 3] berada di posisi pertama dan [3, 2, 1] berada di posisi terakhir.

Fungsi

permute(nums: integer-array) → integer-2d-array

numsinteger-array: nilai-nilai, semuanya berbeda, dalam urutan apa pun
Mengembalikaninteger-2d-array: setiap susunan nilai, dicantumkan dalam urutan leksikografis

Batasan

1 ≤ nums.length ≤ 6
-10 ≤ nums[i] ≤ 10
Semua nilai dalam nums berbeda.
nums dapat muncul dalam urutan apa pun.

Contoh

Input: nums = [3, 1, 2]
Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Penjelasan: Urutan yang dimulai dengan 1 muncul lebih dahulu, dan [1, 2, 3] muncul sebelum [1, 3, 2] karena 2 lebih kecil daripada 3 pada posisi kedua. Urutan input tidak berpengaruh.

Input: nums = [2, -1]
Output: [[-1, 2], [2, -1]]
Penjelasan: Dua nilai dapat ditulis dalam dua urutan. [-1, 2] ditulis terlebih dahulu karena -1 lebih kecil daripada 2.

Pertanyaan lanjutan

Diberikan satu urutan, dapatkah kamu menghasilkan urutan berikutnya dalam urutan leksikografis di tempat, dalam waktu O(n) dan ruang ekstra O(1)?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

n nilai berbeda memiliki n! urutan, yaitu 720 untuk enam nilai, dan kamu harus mencantumkan semuanya, jadi pekerjaan yang diperlukan setidaknya n × n!. Dengan melakukan backtracking pada nilai yang telah diurutkan, selalu mencoba nilai terkecil yang belum digunakan terlebih dahulu, setiap urutan dibentuk satu kali dan dihasilkan dalam urutan leksikografis.

Sisipkan ke setiap celah, lalu urutkan

Intuisi

Bangun susunan satu nilai setiap kali, dimulai dari list kosong. Untuk menambahkan 3 ke [1, 2], sisipkan nilai itu ke masing-masing dari tiga celah: [3, 1, 2], [1, 3, 2] dan [1, 2, 3]. Setiap susunan dari k+1 nilai dibangun tepat satu kali: hapus nilai terbaru, maka kamu akan mendapatkan susunan asalnya, sedangkan posisinya menunjukkan celah yang digunakan.

Susunan-susunan itu tidak muncul secara berurutan: untuk [1, 2, 3], susunan pertama yang dibangun adalah [3, 2, 1]. Jadi, kamu perlu melakukan sort di akhir, dengan sekitar n! × log(n!) perbandingan yang masing-masing melibatkan hingga n nilai, atau kira-kira 720 × 9.5 × 6 ≈ 41,000 pembacaan untuk enam nilai. Cara ini juga menyimpan satu generasi penuh susunan di memori.

Algoritma

Mulai dengan sebuah list yang berisi satu susunan kosong.
Untuk setiap nilai dalam nums, buat list baru: untuk setiap susunan sejauh ini dan setiap celah dari 0 hingga panjangnya, salin susunan tersebut dengan nilai disisipkan pada celah itu.
Ganti list lama dengan list baru.
Urutkan susunan berdasarkan posisi demi posisi, lalu kembalikan semuanya.

def permute(nums):
    perms = [[]]
    for value in nums:
        grown = []
        for perm in perms:
            # Put value into every gap of perm, both ends included.
            for gap in range(len(perm) + 1):
                grown.append(perm[:gap] + [value] + perm[gap:])
        perms = grown
    # Insertion order is not lexicographic, so sort at the end.
    perms.sort()
    return perms

Backtracking dengan array yang digunakan

Intuisi

Isi n slot dari kiri ke kanan: ada n kandidat untuk slot pertama, n-1 untuk slot kedua, dan seterusnya. Sebagai pohon, setiap sisi menempatkan satu nilai lagi dan setiap daun pada kedalaman n adalah satu urutan. Telusuri pohon dengan satu path bersama dan satu penanda used untuk setiap nilai: untuk setiap nilai yang belum dipakai, pilih nilai itu, telusuri satu tingkat lebih dalam, lalu batalkan pilihannya. Membatalkan pilihan akan memulihkan keadaan persis seperti semula, sehingga perulangan mencoba nilai berikutnya dari node yang sama.

Urutannya akan terbentuk dengan benar secara otomatis. Perulangan mencoba nilai terkecil yang belum dipakai terlebih dahulu dan menyelesaikan setiap urutan dengan prefiks tertentu sebelum mengubah prefiks itu, jadi [1, 2, ...] muncul sebelum [1, 3, ...], yang muncul sebelum [2, ...]. Itulah sebabnya kamu mengurutkan nums terlebih dahulu. Pohon ini memiliki sekitar e × n! node, dan setiap node menjalankan perulangan sebanyak n kali: waktu O(n × n!).

Algoritma

Urutkan nilai dan buat array used yang berisi n penanda false.
Tulis explore(). Jika path berisi n nilai, tambahkan salinannya ke hasil lalu kembalikan.
Jika tidak, untuk setiap indeks i dari 0 hingga n-1 yang nilainya belum digunakan: tandai sebagai sudah digunakan dan tambahkan values[i] (pilih), panggil explore() (jelajahi), lalu hapus nilai tersebut dan tandai sebagai belum digunakan (batalkan pilihan).
Panggil explore() sekali dan kembalikan hasilnya.

def permute(nums):
    values = sorted(nums)
    n = len(values)
    result = []
    path = []
    used = [False] * n

    def explore():
        # A full path is a leaf of the decision tree: one finished ordering.
        if len(path) == n:
            result.append(path[:])
            return
        # Smallest unused value first, so the leaves come out in lexicographic order.
        for i in range(n):
            if used[i]:
                continue
            used[i] = True
            path.append(values[i])  # choose
            explore()               # explore
            path.pop()              # un-choose
            used[i] = False

    explore()
    return result

Jebakan dan kasus tepi

Menyimpan path alih-alih salinannya. Semua n! entri akhirnya menjadi daftar yang sama, yang kosong setelah penelusuran selesai.
Mengurungkan hanya separuh pilihan. Jika kamu menghapus nilainya tetapi membiarkan used[i] tetap disetel, nilai itu tidak akan muncul di cabang berikutnya dan kamu akan mendapatkan kurang dari n! urutan.
Tidak mengurutkan nums terlebih dahulu. Urutannya kemudian mengikuti input, sehingga [3, 1, 2] akan tercantum pertama.
Menggunakan method pertukaran (menukar nums[start] dengan setiap posisi setelahnya, melakukan rekursi, lalu menukar kembali) tanpa pengurutan akhir. Untuk [1, 2, 3], hasilnya mencantumkan [3, 2, 1] sebelum [3, 1, 2].
Mencari di path untuk mengetahui apakah suatu nilai sudah digunakan. Biayanya n untuk setiap pemeriksaan dan cara ini gagal saat nilai berulang. Satu penanda untuk setiap indeks memiliki kompleksitas O(1).

Pertanyaan yang sering diajukan3

Berapa banyak permutasi yang dapat dibentuk dari list berisi n elemen berbeda?

n!, dibaca n faktorial: n pilihan untuk posisi pertama, n-1 untuk posisi kedua, hingga satu pilihan untuk posisi terakhir, semuanya dikalikan. Tiga nilai menghasilkan 6 urutan, enam menghasilkan 720, dan sepuluh saja sudah menghasilkan 3,628,800, itulah sebabnya soal permutasi menggunakan n yang kecil.

Berapa kompleksitas waktu untuk menghasilkan semua permutasi?

O(n × n!). Ada n! urutan dan menuliskan masing-masing membutuhkan n langkah, jadi tidak ada method yang lebih cepat jika semuanya harus dikembalikan. Backtracking mencapai batas ini dan, selain output, membutuhkan ruang O(n) untuk jalur, penanda yang digunakan, dan rekursi.

Bagaimana cara menghasilkan permutasi ketika input memiliki duplikat?

Urutkan nilainya dan, di setiap posisi, lewati nilai yang sama dengan nilai sebelumnya saat salinan sebelumnya itu belum digunakan: i > 0, values[i] == values[i-1] dan !used[i-1]. Dengan begitu, nilai yang sama ditempatkan dalam urutan aslinya, sehingga setiap susunan berbeda dibuat satu kali.

def permute(nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

nums = [3, 1, 2]

Output yang diharapkan

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]