Sınırı aşmayan rakam dizilimleri
Görev tanımı
Problem
Birbirinden farklı rakamlardan oluşan bir liste ve bir sınır verildiğinde, her rakamı bir sırayla tam bir kez kullanan ve en fazla sınır kadar olan her sayıyı artan sırada döndür. Bir sayı, tek basamaklı 0 değilse 0 ile başlayamaz. En fazla 8 rakam var.
Örnekler
Input: digits = [3, 1, 2], limit = 300
Output: [123, 132, 213, 231]
Neden: 312 ve 321 sınırı aşıyor; rakamları artan sırada denemek sayıları zaten sıralı verir
Input: digits = [0, 2, 1], limit = 999
Output: [102, 120, 201, 210]
Neden: 0 ile başlayan dizilimler atlanır, çünkü 012 aslında iki basamaklı bir sayıdır
Input: digits = [5], limit = 4
Output: []
Neden: edge case: tek dizilim zaten sınırı aşıyor
İpuçları
0 / 3
Sayıyı rakam rakam kur; her rakamı mevcut prefix'te durduğu sürece kullanıldı olarak işaretle, geri çekilirken işareti kaldır.
Önce rakamları sırala. O zaman sayılar sonda sıralamaya gerek kalmadan artan sırada çıkar, çünkü her prefix en küçük sonraki rakamından başlanarak denenir.
Buda: arkasından r rakam daha gelecek bir prefix en az prefix × 10 üzeri r'dir. Bu zaten sınırı aşıyorsa daha büyük her sonraki rakam da aşar, bu yüzden döngüyü durdur.
- Hedef zaman
- O(n · n!)
- Hedef alan
- O(n!)
Kısıtlar
- digits are distinct
- at most 8 digits
Çözüm
Bu, kullanıldı dizisiyle permütasyon şablonu: kullanılmamış bir rakam seç, özyinele, sonra onu serbest bırak. Rakamları önce sıralamak aramanın prefix'leri (önek) artan sırada ziyaret etmesini sağlar, sonuçlar da bedavaya sıralı olur. Sınır ucuz bir budama verir: geri kalanı ne ile doldurursan doldur sayı en az, kalan konum sayısı kadar sola kaydırılmış prefix'tir; bu sınır limiti geçtiği anda bu rakam ve daha büyük her rakam bir break ile atlanabilir. Baştaki sıfır kuralı ilk konumda tek bir koşuldur. En kötü durumda n! dizilimin hepsi kurulur; zaman O(n × n!), alan da çıktı artı özyineleme (recursion) için O(n).
def orderings_up_to(digits, limit):
digits = sorted(digits) # increasing digits give sorted output
used = [False] * len(digits)
out = []
def place(value, length):
if length == len(digits):
out.append(value)
return
for i, d in enumerate(digits):
if used[i] or (length == 0 and d == 0 and len(digits) > 1):
continue # used already, or a leading zero
nxt = value * 10 + d
if nxt * 10 ** (len(digits) - length - 1) > limit:
break # the smallest completion is too big
used[i] = True
place(nxt, length + 1)
used[i] = False # back out
place(0, 0)
return out
print(orderings_up_to([3, 1, 2], 300)) # -> [123, 132, 213, 231]
print(orderings_up_to([0, 2, 1], 999)) # -> [102, 120, 201, 210]
print(orderings_up_to([5], 4)) # -> []Kodda değil de fikirde mi takıldın? Permütasyonlar bunu anlatıyor.