0

Есть алгоритм, но он не понятен и не доходчив:

Генерация композиций натурального числа n по заданному рангу m означает: всевозможными способами разбить n на m целых неотрицательных слагаемых. Другими словами, разбить всевозможными способами n записанных подряд единиц на заданное число m частей (допускаются и пустые части). Если в качестве символов-разделителей выбрать нули, то m частей порождаются m-1 разделителями, т.е. m-1 нулями. Таким образом, задача сводится к перебору битовых строк длины q=n+m-1, отсеивая те, в которых число нулей отлично от m-1.

В качестве вспомогательного алгоритма нам понадобится алгоритм порождения всех двоичных последовательностей длины q. Используется битовый массив b[q], b[q-1], ..., b[0], который вначале обнуляется. Для записи порожденной последовательности служат b[q-1], ..., b[0], b[q] – только для технических целей: порождающий цикл завершается, как только b[q] станет равно 1. while b[q]=0 do begin 1. вывод последовательности b[q-1], ..., b[0]; 2. найти первый справа налево нулевой элемент b[i] и заменить его на единицу, а все элементы правее него стереть до нуля. end

1
  • 1
    Кнут, "Искусство программирования", том 4а, раздел 7.2.1.4, алгоритм H - разбиение числа n на m частей. Правда, они все ненулевые, но вам достаточно применить его для всех i от 1 до m, добавляя нужное количество нулей.
    – Harry
    17 апр 2019 в 18:11

1 ответ 1

2

Если ограничений на величину слагаемых нет, то количество разбиений равно Cm-1n-1. И получается очевидным образом именно из предложенного вам подхода: "разбить всевозможными способами n записанных подряд единиц на заданное число m частей". Это метод шаров и перегородок.

Генерацию разбивающих последовательностей организовать несложно. Известный "побитовый" хак выглядит вот так (на С или С++)

unsigned next_combination(unsigned x)
{
  unsigned u = x & -x;
  unsigned v = u + x;
  x = v  + (((v ^ x) / u) >> 2);
  return x;
}

и позволяет вам генерировать все битовые наборы с фиксированным количеством единичных битов в рамках поддерживаемого языком целого типа.

"Нехаковый" алгоритм проще описать без "битовых наборов". Простой алгоритм представляет собой генерацию последовательных m-значных чисел в специальной системе счисления: цифры этой системы лежат в диапазоне [1, n) и в каждом числе всегда идут строго по возрастанию. (Это ни что иное, как комбинаторная система счисления, хотя в каноническом определении цифры обычно убывают.) Каждая цифра - это позиция разделителя между шарами.

Например, для n = 6 и m = 3 генерируем 123, 124, 125, 134, 135, 145, 234, 235, ..., 345. Логика последовательной генерации таких чисел тривиальна

#include <stdio.h>
#include <stdlib.h>

#define N 10u
#define M 3u

int main(void) {
  unsigned digits[M];
  unsigned i;

  for (i = 0; i < M; ++i)
    digits[i] = i + 1;

  do {
    unsigned overflow;

    for (i = 0; i < M; ++i)
      printf("[%u]", digits[i]);
    printf("\n");

    for (i = M - 1, overflow = N; i != -1; --i, --overflow)
      if (++digits[i] < overflow)
        break;

    if (i == -1)
      break;

    for (++i; i < M; ++i)
      digits[i] = digits[i - 1] + 1;

  } while (1);
}

Ваш ответ

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

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