Permutations

+10

Farklı tam sayılardan oluşan bir nums listesi alırsın. Bu değerlerin tüm sıralamalarını döndür; her biri her değeri tam olarak bir kez kullanan bir liste olsun, böylece n değer n! sıralama verir. Bunları sözlük sırasına göre listele: iki sıralamayı konum konum karşılaştır ve ilk farklı konum belirleyici olsun. [1, 2, 3] için bu, [1, 2, 3] listesini ilk, [3, 2, 1] listesini son sıraya koyar.

Fonksiyon

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

numsinteger-array: değerler, hepsi farklı, herhangi bir sırada
Döndürürinteger-2d-array: değerlerin sözlük sırasına göre listelenmiş her sıralaması

Kısıtlar

1 ≤ nums.length ≤ 6
-10 ≤ nums[i] ≤ 10
Tüm nums değerleri birbirinden farklıdır.
nums herhangi bir sırada olabilir.

Örnekler

Girdi: nums = [3, 1, 2]
Çıktı: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Açıklama: Üç değerin 3! = 6 sıralaması vardır. Sıralandığında değerler 1, 2, 3 olur; bu nedenle 1 ile başlayan sıralamalar önce gelir ve ikinci konumda 2, 3'ten küçük olduğu için [1, 2, 3], [1, 3, 2]'den önce gelir. Girdinin sırası önemli değildir.

Girdi: nums = [2, -1]
Çıktı: [[-1, 2], [2, -1]]
Açıklama: İki değer iki farklı sırada yazılabilir. -1, 2'den küçük olduğu için [-1, 2] önce gelir.

Gönderirken +13 gizli test

Ek soru

Bir sıralama verildiğinde, O(n) zamanda ve O(1) ek alan kullanarak sözlük sırasındaki bir sonraki sıralamayı yerinde üretebilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

n farklı değerden oluşan bir listenin n! sıralaması vardır; altı değer için bu sayı 720'dir ve yanıtın hepsini listelemesi gerekir, dolayısıyla iş yükü en az n × n! olur. Zorluk, her sıralamayı bir kez oluşturup sözlük sırasına göre üretmektir. Sıralanmış değerler üzerinde geri izleme yapıp her zaman kullanılmamış en küçük değeri önce denemek, ikisini de aynı anda sağlar.

Her boşluğa ekleyin, ardından sıralayın

Sezgi

Sıralamaları her seferinde bir değer ekleyerek büyütün. Hiç değer yokken tek bir sıralama vardır: boş liste. [1, 2] sıralamasına 3 değerini eklemek için onu üç boşluğun her birine yerleştirin: [3, 1, 2], [1, 3, 2] ve [1, 2, 3]. Bunu elinizdeki her sıralama için yapın; k değerli sıralamalar, k+1 değerli sıralamalara dönüşür.

k+1 değerli her sıralama tam olarak bir kez oluşturulur: En yeni değeri çıkarırsanız, ondan türediği tek sıralamayı elde edersiniz; en yeni değerin konumu da boşluğu belirtir. Böylece sayılar 1, 2, 6, 24 şeklinde ilerler ve n değer, n! sıralama verir.

Bunlar gereken sırada ortaya çıkmaz. [1, 2, 3] için oluşturulan ilk sıralama [3, 2, 1] olur; bu yüzden sonunda konum konum karşılaştırma yapan bir sıralama işlemi gerekir. Pahalı olan kısım bu sıralamadır: n! sıralama için yaklaşık n! × log(n!) karşılaştırma gerekir ve her biri en fazla n değer okur. Altı değer için bu, yaklaşık 720 × 9.5 × 6, yani yaklaşık 41.000 okumadır. Yöntem ayrıca yeni nesli oluştururken sıralamaların bir neslini bellekte tutar.

Algoritma

Tek bir boş sıralama içeren bir listeyle başlayın.
nums içindeki her değer için yeni bir liste oluşturun: şimdiye kadarki her sıralama ve 0'dan uzunluğuna kadar her boşluk için, değerin o boşluğa eklendiği sıralamayı kopyalayın.
Eski listeyi yenisiyle değiştirin.
Sıralamaları konumlarına göre sıralayın ve döndürün.

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

Kullanılmış bir diziyle geri izleme

Sezgi

n yuvayı soldan sağa doldur. İlk yuvada n aday, ikincide n-1 aday vardır ve n! buradan gelir. Bu seçimleri bir ağaç olarak çiz: kök boş bir yoldur, her kenar bir değer daha ekler ve derinliği n olan her yaprak tamamlanmış bir sıralamadır. Sıralı 1, 2, 3 değerleri için kökün çocukları [1], [2] ve [3] olur; [1] düğümünün çocukları [1, 2] ve [1, 3] olur; bunların her birinin bir yaprağı vardır.

Geri izleme, tek bir ortak path ve her değer için bir used bayrağı kullanarak bu ağacı dolaşır. Her düğümde değerler üzerinde döngü kurar ve kullanılmış olanları atlar. Boştaki her değer için seçer (kullanıldı olarak işaretler ve ekler), keşfeder (bir seviye daha derine özyinelemeli çağrı yapar), ardından seçimi geri alır (değeri kaldırır ve boş olarak işaretler). Seçimi geri alma adımı, döngünün önceki durumunu aynen geri yükler; böylece sonraki değer aynı düğümden denenir. Uzunluğu n olan bir yol yapraktır: bir kopyasını kaydet ve dön.

Sıralama kendiliğinden doğru olur. Döngü önce boşta olan en küçük değeri dener ve dolaşım, öneki değiştirmeden önce o önekle başlayan tüm sıralamaları tamamlar. Böylece 1 ile başlayan tüm sıralamalar, 2 ile başlayanlardan önce gelir ve bunların arasında [1, 2, ...], [1, 3, ...] ifadesinden önce gelir. Bu, sözlük sırasıdır. nums değerlerini önce sıralamanın nedeni de budur: döngü indeks sırasına göre ilerler, dolayısıyla indeksler değer sırasına göre olmalıdır.

Ağaçta yaklaşık e × n! düğüm vardır (e yaklaşık 2.72'dir) ve her biri n uzunluğunda bir döngü çalıştırır; bu nedenle zaman karmaşıklığı O(n × n!) olur ve bu, yanıtın boyutuyla aynı mertebededir. Çıktının yanı sıra path, bayraklar ve çağrı yığını da en fazla n girdi tutar.

Algoritma

Değerleri sırala ve n adet false bayraktan oluşan bir used dizisi oluştur.
explore() fonksiyonunu yaz. path içinde n değer varsa, sonuca bir kopyasını ekle ve döndür.
Aksi hâlde, değeri kullanılmamış olan 0 ile n-1 arasındaki her i indeksi için: onu kullanılmış olarak işaretle ve values[i] değerini ekle (seç), explore() fonksiyonunu çağır (keşfet), ardından onu kaldır ve kullanılmamış olarak işaretle (seçimi geri al).
explore() fonksiyonunu bir kez çağır ve sonucu döndür.

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

Tuzaklar ve uç durumlar

Geri izleme hataları neredeyse her zaman geri yüklenmeyen durumdan veya yanlışlıkla paylaşılan durumdan kaynaklanır.

path'in bir kopyası yerine path'i kaydetmek. Yürüyüş bittiğinde boş olan aynı liste, n! girdinin tamamında yer alır.
Bir seçimin yalnızca yarısını geri almak. Değeri kaldırıp used[i]'yi ayarlı bırakırsanız, bu değer sonraki dallarda bir daha görünmez ve n!'den az sıralama döndürürsünüz.
Önce nums'u sıralamamak. Yürüyüş yine de her sıralamayı bulur, ancak bunlar girdinin sırasını izler; dolayısıyla [3, 1, 2] girdisi ilk sırada listelenir.
Son bir sıralama yapmadan takas yöntemini kullanmak ( nums[start]'i sonraki her konumla takas etmek, özyinelemeli çağrı yapmak, sonra tekrar takas etmek). Tüm n! sıralamaları bulur, ancak [1, 2, 3] için [3, 1, 2]'den önce [3, 2, 1]'i listeler.
Kullanılmış bir değeri path içinde arayarak kontrol etmek. Bu yöntem burada yalnızca değerler farklı olduğu için çalışır ve her adımda n maliyet getirir. Her indeks için bir bayrak O(1) maliyetlidir ve değerler tekrarlandığında da çalışır.

Sıkça sorulan sorular4

n farklı öğeden oluşan bir listenin kaç permütasyonu vardır?

n!, n faktöriyel olarak okunur: ilk konum için n seçenek, ikinci için n-1, son konum için bire kadar iner ve hepsi birbiriyle çarpılır. Üç değer 6 sıralama, altı değer 720 sıralama verir; on değer ise şimdiden 3,628,800 sıralama verir. Bu yüzden permütasyon problemlerinde n küçük tutulur.

Tüm permütasyonları üretmenin zaman karmaşıklığı nedir?

O(n × n!). n! sıralama vardır ve her birini yazmak n adım sürer; bu yüzden hepsini döndürmesi gereken hiçbir yöntem daha iyisini yapamaz. Geri izleme bu sınıra ulaşır ve çıktı dışında mevcut yol, kullanılan bayraklar ve özyineleme için O(n) alan gerektirir.

Geri izleme neden sözlükbilimsel sırada permütasyonlar üretir?

Önce mevcut en küçük değeri deneyen derinlik öncelikli bir dolaşmadır. Bir sonraki öneke geçmeden önce, belirli bir önekle başlayan tüm sıralamaları tamamlar ve önekleri küçükten büyüğe doğru dener. Girdi dolaşma başlamadan önce sıralandığı sürece, bu yöntem bir sözlüğün sözcükleri sıralama biçimiyle örtüşür.

Girdide yinelenen değerler olduğunda permütasyonları nasıl üretirsiniz?

Değerleri sırala ve her konumda, önceki kopya kullanılmıyorken önceki değerle aynı olan bir değeri atla: i > 0, values[i] == values[i-1] ve !used[i-1]. Bu, eşit değerlerin özgün sıralarında yerleştirilmesini sağlar; böylece her farklı sıralama bir kez oluşturulur.

Python

def permute(nums):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

nums = [3, 1, 2]

Beklenen

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