İlk n sayıdan k tanesini seç
Görev tanımı
Problem
İki tam sayı n ve k verildiğinde, 1 ile n arasından k farklı sayı seçmenin her yolunu döndür. Bir seçimin içindeki sıra önemli değil; bu yüzden her seçimi artan sırada yaz ve seçimleri artan sözlük sırasıyla döndür.
Örnekler
Input: n = 4, k = 2
Output: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
Neden: 4'ün 2'li kombinasyonu 6
Input: n = 3, k = 3
Output: [[1, 2, 3]]
Neden: hepsini almanın tek bir yolu var
Input: n = 2, k = 0
Output: [[]]
Neden: edge case: hiçbir şey seçmemek tam olarak bir seçimdir, boş seçim
İpuçları
0 / 3
Bir seçimi sayı sayı kur. Her seçimi artan sırada tutmak ve [1, 2]'den sonra [2, 1] üretmemek için yalnız en son eklediğin sayıdan büyük sayıları ekle.
Bir başlangıç değeriyle özyinelemeli çağır: start'tan yukarı doğru bir x sayısı seç, start = x + 1 ile kendini çağır, sonra x'i çıkar ve bir sonrakini dene. Seçim k sayıya ulaştığında bir kopyasını kaydet.
Döngüyü buda: hâlâ m sayıya daha ihtiyacın varsa x'ten başlamak yalnız x + m - 1 <= n olduğunda işe yarar; bu yüzden döngü n yerine n - m + 1'de durabilir.
- Hedef zaman
- O(k · C(n, k))
- Hedef alan
- O(k · C(n, k))
Çözüm
Bu, k derinliğinde kesilmiş alt küme karar ağacıdır. Her seviye seçimin bir sonraki sayısına karar verir ve bir sonraki başlangıç olarak x + 1 vermek her seçimin artan sırada kurulmasını garanti eder; böylece her sayı kümesi tam bir kez üretilir, çıktı da bedavaya sözlük sırasıyla çıkar. Özyinelemeli çağrı (recursive call) dönünce sayı pop edilir; bu, paylaşılan pick listesini döngünün bulduğu hale geri getirir. Döngünün üst sınırı budama (pruning) adımıdır: yeterince sayı toplayamayacak bir dala hiç girilmez. C(n, k) seçim var ve her birini kopyalamak O(k) tutar; zaman O(k × C(n, k)), özyineleme derinliği k.
def choose(n, k):
out, pick = [], []
def build(start):
if len(pick) == k:
out.append(pick[:]) # record a copy, pick keeps changing
return
need = k - len(pick)
for x in range(start, n - need + 2): # leave room for the numbers still needed
pick.append(x)
build(x + 1)
pick.pop() # undo before trying the next x
build(1)
return out
print(choose(4, 2)) # -> [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
print(choose(3, 3)) # -> [[1, 2, 3]]
print(choose(2, 0)) # -> [[]]Kodda değil de fikirde mi takıldın? Alt kümeler bunu anlatıyor.