Kombinatoryal sayı sistemi - Combinatorial number system

İçinde matematik ve özellikle kombinatorik, kombinatoryal sayı sistemi derece k (bazı pozitif tam sayılar için k) olarak da anılır Kombinasyonlar, arasındaki bir yazışmadır doğal sayılar (0 dahil alınmıştır) N ve k-kombinasyonlar, olarak temsil edilir kesinlikle azalan diziler c_k > ... > c₂ > c₁ ≥ 0. İkincisi sayı dizileri olduğundan, bunu bir tür sayı sistemi temsil etmek için N, ana yardımcı program bir k-kombinasyonu N tersi yerine. Farklı sayılar, farklı k-kombinasyonlar ve bunları sözlük düzeni; dahası küçük sayılar ${ displaystyle { tbinom {n} {k}}}$ hepsine karşılık k- kombinasyonları { 0, 1, ..., n − 1}. Yazışma boyuta bağlı değildirn setin k-kombinasyonlar buradan alınır, böylece bir harita olarak yorumlanabilir N için k-Alınan kombinasyonlar N; bu görüşe göre yazışma bir birebir örten.

Numara N karşılık gelen (c_k,...,c₂,c₁) tarafından verilir

${ displaystyle N = { binom {c_ {k}} {k}} + cdots + { binom {c_ {2}} {2}} + { binom {c_ {1}} {1}}. }$

Eşsiz bir dizinin herhangi bir sayıya karşılık gelmesi N tarafından gözlemlendi D. H. Lehmer.^[1] Gerçekten bir Açgözlü algoritma bulur k- karşılık gelen kombinasyon N: almak c_k maksimum ile ${ displaystyle { tbinom {c_ {k}} {k}} leq N}$, o zaman al c_{k − 1} maksimum ile ${ displaystyle { tbinom {c_ {k-1}} {k-1}} leq N - { tbinom {c_ {k}} {k}}}$vb. Numarayı bulmak N, yukarıdaki formülü kullanarak k-kombinasyon (c_k,...,c₂,c₁) "sıralama" olarak da bilinir ve zıt işlem (açgözlü algoritma tarafından verilir) "sıralanmamış" olarak bilinir; bu işlemler çoğu ülkede bu isimlerle bilinmektedir. bilgisayar cebir sistemleri, ve hesaplamalı matematik.^[2][3]

Başlangıçta kullanılan "tamsayıların kombinasyonel gösterimi" terimi, "kombinatoryal sayı sistemi" olarak kısaltılmıştır. Knuth,^[4]ayrıca çok daha eski bir referans veren;^[5]"birleşik" terimi James McCaffrey tarafından tanıtıldı ^[6] (önceki terminolojiye veya çalışmaya atıfta bulunmadan).

Aksine faktöriyel sayı sistemi, derecenin kombinatoryal sayı sistemi k değil karışık taban sistem: parça ${ displaystyle { tbinom {c_ {i}} {i}}}$ sayının N "rakam" ile gösterilir c_ben ondan basitçe bir basamak değeriyle çarpılarak elde edilmez.

Kombinatoryal sayı sisteminin ana uygulaması, hızlı hesaplamaya izin vermesidir. k-özellik sıralamasında belirli bir konumda bulunan kombinasyon, açıkça listelemek zorunda kalmadan k- ondan önceki kombinasyonlar; bu, örneğin rastgele oluşturulmasına izin verir k- belirli bir setin kombinasyonları. Numaralandırma k-kombinasyonlar aralarında birçok uygulamaya sahiptir yazılım testi, örnekleme, kalite kontrol ve analizi Piyango oyunlar.

Kombinasyonları sipariş etme

Bir k-bir setin kombinasyonu S alt kümesidir S ile k (farklı) öğeler. Kombinatoryal sayı sisteminin temel amacı, her biri tek bir sayıya göre bir temsil sağlamaktır. ${ displaystyle { tbinom {n} {k}}}$ mümkün k-bir setin kombinasyonları S nın-nin n elementler. Herhangi biri için seçim n, {0, 1, ..., n − 1} böyle bir küme olarak, verilen bir gösterimin gösterimi düzenlenebilir kkombinasyon C değerinden bağımsızdır n (olmasına rağmen n elbette yeterince büyük olmalıdır); başka bir deyişle düşünüyor C daha büyük bir kümenin alt kümesi olarak artırarak n temsil eden sayıyı değiştirmeyecekC. Bu nedenle, kombinatoryal sayı sistemi için kişi sadece C olarak k- setin kombinasyonu N açıkça belirtmeden tüm doğal sayıların n.

Temsil eden sayıların olmasını sağlamak için k- kombinasyonları {0, 1, ..., n − 1} temsil edenlerden daha az k-içerilmeyen kombinasyonlar {0, 1, ..., n − 1}, k- Kombinasyonlar, en büyük unsurları önce karşılaştırılacak şekilde sıralanmalıdır. Bu özelliğe sahip en doğal sipariş sözlüksel sıralama of azalan öğelerinin sırası. Yani 5 kombinasyonu karşılaştırmak C = {0,3,4,6,9} ve C'= {0,1,3,7,9}, bunlardan biri var C önce gelir C', aynı en büyük bölüm 9'a sahip olduklarından, ancak sonraki en büyük bölüm 6'ya C bir sonraki en büyük 7. bölümden küçüktür C'; sözlüksel olarak karşılaştırılan diziler (9,6,4,3,0) ve (9,7,3,1,0) 'dır. Bu sıralamayı tanımlamanın başka bir yolu, kombinasyonların k bir sayının ikili gösteriminde yükseltilmiş bitler, böylece C = {c₁,...,c_k} numarayı tanımlar

${ displaystyle 2 ^ {c_ {1}} + 2 ^ {c_ {2}} + cdots + 2 ^ {c_ {k}}}$

(bu, farklı sayıları herşey sonlu doğal sayı kümeleri); sonra karşılaştırmak kKombinasyonlar, ilişkili ikili sayıları karşılaştırarak yapılabilir. Örnekte C ve C1001011001 sayılarına karşılık gelir₂ = 601₁₀ ve 1010001011₂ = 651₁₀ki yine gösteriyor ki C önce gelir C'. Ancak bu sayı, temsil etmek isteyen kişi değildir. k- ile kombinasyon, çünkü birçok ikili sayının birden fazla yükseltilmiş biti vardır. k; göreceli konumunu bulmak ister C sıralı listesinde (sadece) k-kombinasyonlar.

Bir kombinasyonun siparişteki yeri

Derecenin kombinatoryal sayı sisteminde ilişkili sayı k bir kkombinasyon C sayısı k- kesinlikle daha az olan kombinasyonlar C verilen sırayla. Bu sayı hesaplanabilir C = { c_k, ..., c₂, c₁ } ile c_k > ... > c₂ > c₁ aşağıdaki gibi. Siparişin tanımından her biri için şunu takip eder: kkombinasyon S kesinlikle daha azCbenzersiz bir dizin varben öyle ki c_ben yok S, süre c_k, ..., c_ben+1 mevcut Sve daha büyük bir değer yok c_ben dır-dir. Dolayısıyla bunları gruplayabiliriz k-kombinasyonlar S olası değerlere göre 1, 2, ..., k nın-nin benve her grubu ayrı ayrı sayın. Belirli bir değer için ben içermelidirc_k, ..., c_ben+1 içinde Sve kalan ben unsurları S arasından seçilmelidir c_ben negatif olmayan tamsayılar kesinlikle küçüktür c_ben; dahası böyle bir seçim bir k-kombinasyonlar S kesinlikle daha azC. Olası seçeneklerin sayısı ${ displaystyle { tbinom {c_ {i}} {i}}}$, bu nedenle gruptaki kombinasyonların sayısı ben; toplam rakam k- kesinlikle daha az olan kombinasyonlar C daha sonra

${ displaystyle { binom {c_ {1}} {1}} + { binom {c_ {2}} {2}} + cdots + { binom {c_ {k}} {k}},}$

ve bu dizinin (0'dan başlayarak) C sıralı listesinde k-kombinasyonlar. Açıkçası her biri için var N ∈ N tam olarak bir k-indekste kombinasyonN listede (varsayalım k ≥ 1, çünkü liste sonsuzdur), bu nedenle yukarıdaki argüman her N toplamı olarak tam olarak tek bir şekilde yazılabilir k verilen formun iki terimli katsayıları.

Bulmak kbelirli bir sayı için kombinasyon

Verilen formül, belirli bir ifadenin sözlükbilimsel sıralamasında yer bulmaya izin verir. k-hemen kombinasyon. Tersini bulma süreci k- belirli bir yerde kombinasyon N biraz daha fazla çalışma gerektirir, ancak yine de basittir. Sözlüksel sıralamanın tanımına göre, iki k- en büyük unsurlarında farklılık gösteren kombinasyonlar c_k en büyük elemanlarının sabit bir değerine sahip tüm kombinasyonların listede bitişik olduğu sonucu çıkan en büyük elemanların karşılaştırmasına göre sıralanacaktır. Üstelik en küçük kombinasyon c_k en büyük unsur olduğu gibi ${ displaystyle { tbinom {c_ {k}} {k}}}$, ve o sahip c_ben = ben - hepsi için 1 ben < k (bu kombinasyon için, hariç ifadedeki tüm terimler ${ displaystyle { tbinom {c_ {k}} {k}}}$ sıfırdır). Bu nedenle c_k en büyük sayıdır öyle ki ${ displaystyle { tbinom {c_ {k}} {k}} leq N}$. Eğer k > 1 öğenin kalan öğeleri k- kombinasyondan k − 1sayıya karşılık gelen kombinasyon ${ displaystyle N - { tbinom {c_ {k}} {k}}}$ kombinatoryal derece sisteminde k − 1ve bu nedenle aynı şekilde devam ederek bulunabilir ${ displaystyle N - { tbinom {c_ {k}} {k}}}$ ve k − 1 onun yerine N ve k.

Misal

72. pozisyondaki 5 kombinasyonunu belirlemek istediğinizi varsayalım. ${ displaystyle { tbinom {n} {5}}}$ için n = 4, 5, 6, ... 0, 1, 6, 21, 56, 126, 252, ..., 72'yi geçmeyen en büyüğü 56'dır. n = 8. Bu nedenle c₅ = 8 ve kalan elemanlar pozisyondaki 4-kombinasyonunu oluşturur 72 − 56 = 16. Ardışık değerleri ${ displaystyle { tbinom {n} {4}}}$ için n = 3, 4, 5, ... 0, 1, 5, 15, 35, ..., bunlardan en büyüğü 16'yı geçmeyen 15'tir. n = 6, yani c₄ = 6. Konumda 3-kombinasyon aramaya benzer şekilde devam etmek 16 − 15 = 1 bir bulur c₃ = 3, son birimi kullanır; bu kurar ${ displaystyle 72 = { tbinom {8} {5}} + { tbinom {6} {4}} + { tbinom {3} {3}}}$ve kalan değerler c_ben ile maksimal olanlar ${ displaystyle { tbinom {c_ {i}} {i}} = 0}$, yani c_ben = ben − 1. Böylece 5 kombinasyonunu bulduk {8, 6, 3, 1, 0}.

Excel'de Milli Piyango örneği

Her biri için ${ displaystyle { binom {49} {6}}}$ piyango kombinasyonları c₁ < c₂ < c₃ < c₄ < c₅ < c₆ bir liste numarası var N 0 ile ${ displaystyle { binom {49} {6}} - 1}$ ekleyerek bulunabilir

${ displaystyle { binom {49-c_ {1}} {6}} + { binom {49-c_ {2}} {5}} + { binom {49-c_ {3}} {4}} + { binom {49-c_ {4}} {3}} + { binom {49-c_ {5}} {2}} + { binom {49-c_ {6}} {1}}.}$

Olası sonuçlar listesinde bir İngiliz Milli Piyango sonucu 3,6,15,17,18,35 konumunu bulmak istediğinizi varsayalım. Excel işlevi COMBIN (49,6), sonuç sayısının 13983816 olduğunu gösterir. Şimdi, her bir hücresine 3,6,15,17,18,35 sayıları ve COMBIN (49-3,6) formüllerini koyarsanız COMBIN ( 49-6,5), COMBIN (49-15,4), COMBIN (49-17,3), COMBIN (49-18,2), her birinin altında 49−35. Gerçek değerler yerine hücre referanslarını kullanın, gerçek değerler okunabilirlik için sağlanmıştır. 9366819,962598,46376,4960,465,14 numaralı bir satır alırsınız. Bunları eklemek, 10381232 özel konumunu gösterecektir. 14 elde etmek için COMBIN (49-35,1) formülünü kullanmanız gerekmediğini unutmayın. Bunu yalnızca 49-35 çıkararak elde edebilirsiniz. Ayrıca 49-X'in 6'dan küçük olması durumunda KOMBİN işlevi 0 döndürmez. #SAYI! Dönüştürmek için EĞER ISSAYI işlevi ile birlikte kullanmanız gerekir! 0'a.

Şimdi tersine mühendislik biraz daha karmaşık. Bir hücrede 49 IF deyimi kullanabilir veya COMBIN sonucunun konum numarasından küçük veya ona eşit olması için maksimum bağımsız değişkeni bulmak için çözücüyü kullanabilirsiniz. Bunun yerine 6'ya 49'luk bir tablo kullanalım ve sonuçta ortaya çıkan satır numarasının bağımsız değişken ve bir top numarası olacağı MATCH işlevini kullanalım. Azalan sırada 6'dan 1'e (B1: G1) sütun başlıkları ve artan sırada 1'den 49'a kadar (A2: A50) satır etiketleri yaparsanız (Excel'de dikey olarak artan, yukarıdan aşağıya doğru büyüyen sayılar anlamına gelir). Sonra tabloyu sol üst köşeden başlayarak COMBIN ($ A2, B $ 1) formülüyle doldurursanız. $ işaretleri, dizin değerlerinin her zaman başlık satırından ve etiket sütunundan alınmasını sağlar. #SAYI! sıfırlarla. Bunun gibi bir şey almalısın:

	6	5	4	3	2	11	0	0	0	0	0	12	0	0	0	0	1	23	0	0	0	1	3	34	0	0	1	4	6	45	0	1	5	10	10	56	1	6	15	20	15	67	7	21	35	35	21	78	28	56	70	56	28	89	84	126	126	84	36	910	210	252	210	120	45	1011	462	462	330	165	55	1112	924	792	495	220	66	12...49	13983816	1906884	211876	18424	1176	49

Şimdi, altı hücrelik yeni bir satır oluşturur ve bunları, söz konusu konum numarasına eşit veya daha küçük olan her sütundaki en büyük değerleri bulacak formüllerle doldurursanız: = INDEX (B2: B50, MATCH (10381232 , B2: B50)), hücrelerin geri kalanı

INDEX (C2: C50, MATCH (10381232-SUM (önceki hücreler), C2: C50)) ... INDEX (G2: G50, MATCH (10381232-SUM (önceki hücreler), G2: G50))

Bu size daha önce gördüğünüz bir değer satırı sunar 9366819,962598,46376,4960,465,14 Şimdi bir sonraki satırda ilk hücre yazma = 49-MATCH (10381232, B2: B50) ve benzer şekilde

= 49-MATCH (10381232-9366819, C2: C50) ... = 49-MATCH (10381232-9366819-962598-46376-4960-465, G2: G50)

Yine gerçek değerler yerine hücrelere başvuruları kullanın. Size 3,6,15,17,18,35 numaralı orijinal top numaraları sunulmalıdır.

Artık single = randbetween (1, kombinasyon (49,6)) 'dan yeni bir Piyango numarası kombinasyonu oluşturabilir veya bir eğilim olup olmadığını görmek için önceki sonuçların liste pozisyon numaralarına bakabilirsiniz.

Başvurular

Kombinasyonel sayı sistemi, hepsini listelemek veya geçmek için kullanılabilir. k-Belirli bir sonlu kümenin kombinasyonları, ancak bu bunu yapmanın çok verimsiz bir yoludur. Nitekim, biraz verildiğinde k-kombinasyon, bir sonraki kombinasyonu sözlüksel sıralamada doğrudan bulmak, bir sayıyı bir sayıya dönüştürmekten çok daha kolaydır. k- yukarıda belirtilen yöntem ile kombinasyon. Bir sonraki kombinasyonu bulmak için en küçük olanı bulun ben ≥ 2 bunun için c_ben ≥ c_{ben − 1}+2 (eğer böyle bir şey yoksa benal ben = k+1); sonra artır c_ben−1 tek tek ve hepsini ayarla c_j ile j < ben − 1 asgari değerlerine j − 1. Eğer k-kombinasyon ile temsil edilir karakteristik vektör ile ikili bir değer olarak k bit 1, sonra böyle bir sonraki değer, bitsel aritmetik kullanılarak herhangi bir döngü olmadan hesaplanabilir: C ++ fonksiyon ilerleyecek x o değere veya dönüşe yanlış:

// sonraki k kombinasyonunu bulbool next_combination(imzasız uzun& x) // x'in x'01 ^ a10 ^ b biçiminde olduğunu varsayalım{  imzasız uzun sen = x & -x; // en sağdaki bit 1'i çıkar; u = 0'00 ^ a10 ^ b  imzasız uzun v = sen + x; // sonuncu olmayan bit 0'ı ayarlayın ve sağa temizleyin; v = x'10 ^ a00 ^ b  Eğer (v==0) // sonra v veya x == 0'da taşma    dönüş yanlış; // sonraki k kombinasyonunun temsil edilemeyeceğini işaret eder  x = v +(((v^x)/sen)>>2); // v ^ x = 0'11 ^ a10 ^ b, (v ^ x) / u = 0'0 ^ b1 ^ {a + 2} ve x ← x'100 ^ b1 ^ a  dönüş doğru; // başarılı tamamlama}

Bu denir Gosper kesmek;^[7]karşılık gelen montaj kodu 175. madde olarak tanımlanmıştır. HAKMEM.

Öte yandan, doğrudan k-indekste kombinasyon N kullanışlı uygulamalara sahiptir. Özellikle, rastgele bir k-bir kombinasyonu n-Rastgele bir tamsayı kullanan eleman seti N ile ${ displaystyle 0 leq N <{ tbinom {n} {k}}}$, sadece bu sayıyı karşılık gelen k-kombinasyon. Bir bilgisayar programının her biri hakkında bilgi içeren bir tablo tutması gerekiyorsa k-Belirli bir sonlu kümenin kombinasyonu, indeksin hesaplanması N bir kombinasyonla ilişkilendirildiğinde, tabloya arama yapmadan erişilmesine izin verir.

Ayrıca bakınız

• Faktoriyel sayı sistemi (faktöradikler de denir)
• İlkel sayı sistemi

Referanslar