0

Допустим у нас есть 6 чисел. 2 4 6 8 12 14. Необходимо получить все комбинации этих чисел в виде сумм без повторений, с возможностью указать сколько чисел из 6 надо выбрать за раз. Т.е. Если мне нужны все комбинации длиной в 3 числа (из 6). То: 2 + 4 + 6 = 12; 2 + 4 + 8 =....... и т.д. Если длиной в 4 из 6 то: 2 + 4 + 6 + 8 =..... Понимаю что это сочетания из комбинаторики, но как это превратить в код - не знаю. Язык c#;

4
  • Кнут, том 4А. Раздел о генерации сочетаний.
    – Harry
    23 авг 2019 в 18:30
  • Главная цель - сами комбинации или их суммы?
    – MBo
    23 авг 2019 в 19:01
  • @MBo в принципе, только их суммы
    – SadFace
    23 авг 2019 в 19:11
  • @Harry Спасибо, посмотрю, хотя читать этого дядьку бывает довольно сложно.
    – SadFace
    23 авг 2019 в 19:12

1 ответ 1

0

Вариант для ситуации, когда сочетаний будет много, а суммы не слишком большие:

Найдите максимальную сумму SMax. Создайте массив A длиной SMax+1, содержащий списки целых - пока пустые, в нулевой элемент добавьте 0.

Для каждого числа V из исходного списка пройдите по массиву A с конца, проверяя, есть ли в A[i - V] непустые списки. Если есть, в A[i] добавьте элементы A[i - V], увеличенные на единицу. Достаточно обрабатывать только те элементы, которые не превышают нужную длину комбинации С.

По окончанию работы те индексы А, в которых список содержит C, представляют собой суммы, которые можно составить.

Для реальных условий (вряд ли С будет более 32) в массиве каждый список можно заменить целым числом, номера единичных битов которого показывают, из скольки исходных элементов может быть составлена данная сумма.

Пример на Delphi

var
  D, A: TArray<Integer>;
  V, S, i, j, C, CMask: Integer;
begin
  D := [3, 5, 6, 8, 9, 14];
  C := 3;
  CMask := (1 shl C) - 1;
  S := SumInt(D); // но лучше взять сумму C наибольших чисел
  SetLength(A, S + 1);
  A[0] := 1;
  for V in D do begin
    for i := S downto V do
      if ((A[i - V] and CMask) > 0) then
        A[i] := A[i] or (A[i - V] shl 1);
  end;
  for i := 1 to S do
    if A[i] and (CMask + 1) > 0 then
      Memo1.Lines.Add(i.ToString);
end;

14
16
17
18
19
20
22
23
25
26
27
28
29
31

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.