Art of Computer Programming Volume 4: Fascicle 3 ma mnóstwo takich, które mogą lepiej pasować do twojej konkretnej sytuacji niż to, co opisuję.
Szare Kody
Problem, z którym się zetkniesz, to oczywiście pamięć i dość szybko będziesz miał problemy z 20 elementami w zestawie - 20 C 3 = 1140. A jeśli chcesz iterować po zestawie, najlepiej użyć zmodyfikowanego szarego algorytm kodu, więc nie trzymasz ich wszystkich w pamięci. Generują one następną kombinację z poprzednich i unikają powtórzeń. Istnieje wiele z nich do różnych zastosowań. Czy chcemy zmaksymalizować różnice między kolejnymi kombinacjami? zminimalizować? i tak dalej.
Niektóre z oryginalnych artykułów opisujących szare kody:
- Niektóre ścieżki Hamiltona i algorytm minimalnej zmiany
- Algorytm generowania kombinacji sąsiedniej wymiany
Oto kilka innych artykułów na ten temat:
- Skuteczna implementacja Eadesa, Hickeya, odczytu algorytmu generowania kombinacji przylegającej wymiany (PDF, z kodem w Pascal)
- Generatory kombinowane
- Badanie kombinatoryjnych szarych kodów (PostScript)
- Algorytm dla szarych kodów
Chase's Twiddle (algorytm)
Phillip J Chase, ` Algorytm 382: Kombinacje M z N obiektów (1970)
Algorytm w C ...
Indeks kombinacji w porządku leksykograficznym (algorytm klamry 515)
Możesz także odwoływać się do kombinacji według jej indeksu (w porządku leksykograficznym). Zdając sobie sprawę, że indeks powinien być pewną zmianą od prawej do lewej w oparciu o indeks, możemy skonstruować coś, co powinno odzyskać kombinację.
Mamy więc zestaw {1,2,3,4,5,6} ... i chcemy trzech elementów. Powiedzmy, że {1,2,3} możemy powiedzieć, że różnica między elementami jest jedna, w kolejności i minimalna. {1,2,4} ma jedną zmianę i jest leksykograficznie liczbą 2. Zatem liczba „zmian” na ostatnim miejscu odpowiada jednej zmianie w porządku leksykograficznym. Drugie miejsce, z jedną zmianą {1,3,4}, ma jedną zmianę, ale uwzględnia więcej zmian, ponieważ jest na drugim miejscu (proporcjonalnie do liczby elementów w oryginalnym zestawie).
Metoda, którą opisałem, jest, jak się wydaje, dekonstrukcją od zestawu do indeksu, musimy zrobić odwrotnie - co jest znacznie trudniejsze. W ten sposób Buckles rozwiązuje problem. Napisałem trochę C, aby je obliczyć , z niewielkimi zmianami - użyłem indeksu zbiorów, a nie zakresu liczb, aby przedstawić zbiór, więc zawsze pracujemy od 0 ... n. Uwaga:
- Ponieważ kombinacje są nieuporządkowane, {1,3,2} = {1,2,3} - porządkujemy je jako leksykograficzne.
- Ta metoda ma domyślną wartość 0, aby uruchomić zestaw pierwszej różnicy.
Indeks kombinacji w porządku leksykograficznym (McCaffrey)
Jest inny sposób : jego koncepcja jest łatwiejsza do uchwycenia i zaprogramowania, ale bez optymalizacji Buckles. Na szczęście nie tworzy również duplikatów:
Zestaw, który maksymalizuje , gdzie .
Na przykład: 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1)
. Tak więc 27. kombinacja leksykograficzna czterech rzeczy to: {1,2,5,6}, są to indeksy dowolnego zestawu, na który chcesz spojrzeć. Przykład poniżej (OCaml), wymaga choose
funkcji, pozostawionej czytelnikowi:
(* 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)
Mały i prosty iterator kombinacji
Do celów dydaktycznych podano następujące dwa algorytmy. Implementują iterator i (bardziej ogólne) ogólne kombinacje folderów. Są tak szybkie, jak to możliwe, o złożoności O ( n C k ). Zużycie pamięci jest ograniczone przez k
.
Zaczniemy od iteratora, który wywoła funkcję podaną przez użytkownika dla każdej kombinacji
let iter_combs n k f =
let rec iter v s j =
if j = k then f v
else for i = s to n - 1 do iter (i::v) (i+1) (j+1) done in
iter [] 0 0
Bardziej ogólna wersja wywoła funkcję podaną przez użytkownika wraz ze zmienną stanu, zaczynając od stanu początkowego. Ponieważ musimy przekazać stan między różnymi stanami, nie będziemy używać pętli for, ale zamiast tego będziemy używać rekurencji,
let fold_combs n k f x =
let rec loop i s c x =
if i < n then
loop (i+1) s c @@
let c = i::c and s = s + 1 and i = i + 1 in
if s < k then loop i s c x else f c x
else x in
loop 0 0 [] x