Bağımsız değişken olarak harf dizisi ve o mektupları bir dizi alır bir işlev yazmak için seçmek istiyorum.

8 harf bir dizi sağlamak ve 3 harfli olan seçmek için. O zaman almak gerekir:

8! / ((8 - 3)! * 3!) = 56

Dizi (veya kelime) karşılığında 3 harfli her oluşan.

Art of Computer Programming Volume 4: Fascicle 3 özel durumu açıklamak nasıl daha iyi uyabilecek bunlardan bir ton var.

Gri Kodları

Göreceksiniz ki bir sorun tabi bellek ve çok hızlı bir şekilde, set -- 20 element ile ilgili sorunlar var²⁰C3= 1140. Ve eğer en iyi modifiye edilmiş gri bir kod algoritması kullanmak kümesi üzerinde yineleme yapmak istiyorsanız bellekte hepsini tutarak değil. Bunların çoğu, ve farklı kullanımlar için, elementlerin mesafeye göre vardır. Ardışık uygulamalar arasındaki farklılıkları en üst düzeye çıkarmak istiyor muyuz? en aza indirmek? vesaire.

Orijinal kağıtların gri kodları anlatan:

1. Some Hamilton Paths and a Minimal Change Algorithm
2. Adjacent Interchange Combination Generation Algorithm

İşte bazı diğer Gazeteler konuyu kapsayan:

1. An Efficient Implementation of the Eades, Hickey, Read Adjacent Interchange Combination Generation Algorithm (PDF, Pascal kodu ile)
2. Combination Generators
3. Survey of Combinatorial Gray Codes (PostScript)
4. An Algorithm for Gray Codes

Chase'in Twiddle (algoritma)

Phillip J Chase, `Algorithm 382: Combinations of M out of N Objects(1970) '

The algorithm in C...

Kurb sırada Kombinasyonları (Tokaları Algoritma 515) dizin

Ayrıca o dizin tarafından bir arada (kurb sırada), dizin sağdan sola endeksine göre değişim miktar olması gerektiğini fark başvurabilirsiniz.

Yani, bir kümesi {1,2,3,4,5,6}... üç unsur {1,2,3} istediğimizde unsurları arasındaki fark, tek ve sırayla olduğunu söyleyebiliriz. {1,2,4} bir değişiklik vardır, ve lexicographically sayısı 2. 'Değişiklikler' son etapta biri için hesapları kurb değişim sipariş. sayısı İkincisi, bir değişim {1,3,4} bir değişiklik var, ama ikincisi daha değiştirmek için hesaplar.

Anlattığım yöntem yapılanması gibi görünüyor gibi, bu dizin için ayarlamak çok zor olan ters ... ... yapmalıyız. Bu Buckles sorunu çözdü. C to compute them diğer küçük değişiklikler ile her zaman 0...n çalışıyoruz bu yüzden kümeleri dizini yerine bir sayı kümesi aralığında kullandım, biraz yazdım. Not:

1. Duş sırasız olduğundan, {1,3,2} = {1,2,3} --onları kurb için Sipariş ettik.
2. Bu yöntem örtülü bir 0 ilk fark kümesi başlatmak için vardır.

Kurb sırada Kombinasyonları (McCaffrey) dizin

Bu kavram kavramak ve Tokaları iyileştirmeler olmadan bu program için daha kolaydır 16*:,*. Neyse ki, kombinasyonları çoğaltmak üretmek değil:

Set, $x_k...x_1 \\mathbb{N}$ maksimize $i = C(x_1,k) F(x_2,k-1) ... C(x_k,1)$, $C(n,r) = {n \choose r}$.

Örneğin: $27 = C(6,4) C(5,3) C(2,2) C(1,1)$. Yani, dört şey 27 kurb kombinasyonu: {1,2,5,6}, şunlara bak istersen dizinleri vardır. Aşağıda örnek (bunun gibi), choose işlevi, okuyucu için sol gerektirir:

(* this will find the [x] combination of a [set] list when taking [k] elements *)
let combination_maccaffery set k x =
    (* maximize function -- maximize a that is aCb              *)
    (* return largest c where c < i and choose(c,i) <= z        *)
    let rec maximize a b x =
        if (choose a b ) <= x then a else maximize (a-1) b x
    in
    let rec iterate n x i = match i with
        | 0 -> []
        | i ->
            let max = maximize n i x in
            max :: iterate n (x - (choose max i)) (i-1)
    in
    if x < 0 then failwith "errors" else
    let idxs =  iterate (List.length set) x k in
    List.map (List.nth set) (List.sort (-) idxs)