Искусство компьютерного программирования Том 4: Fascicle 3 имеет тонну, которая может соответствовать вашей конкретной ситуации лучше, чем я описываю.
Проблема, с которой вы столкнетесь, - это, конечно, память и довольно быстро, у вас будут проблемы с 20 элементами в вашем наборе - 20C3 = 1140. И если вы хотите итерации по набору, лучше использовать модифицированный серый так что вы не держите их все в памяти. Они генерируют следующую комбинацию из предыдущей и избегают повторений. Их много для разных целей. Разве мы хотим максимизировать различия между последовательными комбинациями? минимизировать? и т. д.
Некоторые из оригинальных работ, описывающих серые коды:
Вот некоторые другие статьи, посвященные теме:
Phillip J Chase, ` Алгоритм 382: Комбинации M из N объектов '(1970)
Алгоритм в C ...
Вы также можете ссылаться на комбинацию по ее индексу (в лексикографическом порядке). Понимая, что индекс должен быть некоторым изменением справа налево на основе индекса, мы можем построить что-то, что должно восстановить комбинацию.
Итак, у нас есть набор {1,2,3,4, 5,6} ... и мы хотим три элемента. Предположим, что {1,2,3} можно сказать, что различие между элементами является одним и по порядку и минимальным. {1,2,4} имеет одно изменение и лексикографически число 2. Таким образом, число «изменений» в последнем месте учитывает одно изменение в лексикографическом порядке. Второе место с одним изменением {1,3,4} имеет одно изменение, но учитывает большее изменение, поскольку оно находится на втором месте (пропорционально количеству элементов в исходном наборе).
метод, который я описал, является деконструкцией, как кажется, от набора к индексу, нам нужно сделать обратное - что намного сложнее. Вот как решает проблема Пряжки . Я написал некоторые C, чтобы вычислить их , с незначительными изменениями. Я использовал индекс наборов, а не диапазон чисел для представления набора, поэтому мы всегда работаем от 0 ... n. Примечание:
Существует другой способ : его концепция легче понять и запрограммировать, но без оптимизаций пряжек. К счастью, он также не создает повторяющихся комбинаций:
Набор , который максимизирует , где .
Пример: 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1)
. Итак, 27-е лексикографическое сочетание четырех вещей: {1,2,5,6}, это индексы того, что вы хотите посмотреть. Пример ниже (OCaml) требует функции choose
, слева от читателя:
(* 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)