r — реализация разбиения и компоновки (комбинаторика) в переполнении стека

Учитывая матрицу размера M а также Nмы хотим заполнить каждую строку целочисленным значением (> = 0), чтобы оно суммировалось до определенного значения.

Обратите внимание, что размерность M а также N предварительно вычисляются с использованием определенной формулы, так что она гарантированно соответствует заполнению при заданном условии (то есть sum_val ниже).

Это реализовано в R под Библиотека разделов.

library(partitions)

# In this example, we impose condition
# that each rows must sum up to 2 in total
# And each row has 5 columns
sum_val <- 2
n <- 5
#The above two parameters are predefined.

t(as.matrix(compositions(sum_val, n)))
[,1] [,2] [,3] [,4] [,5]
[1,]    2    0    0    0    0
[2,]    1    1    0    0    0
[3,]    0    2    0    0    0
[4,]    1    0    1    0    0
[5,]    0    1    1    0    0
[6,]    0    0    2    0    0
[7,]    1    0    0    1    0
[8,]    0    1    0    1    0
[9,]    0    0    1    1    0
[10,]    0    0    0    2    0
[11,]    1    0    0    0    1
[12,]    0    1    0    0    1
[13,]    0    0    1    0    1
[14,]    0    0    0    1    1
[15,]    0    0    0    0    2

Есть ли существующая реализация в C ++?

1

Решение

Вот рекурсивное решение. У вас есть последовательность a где вы отслеживаете номера, которые вы уже установили. Каждый рекурсивный вызов назначит действительные числа одному из этих элементов в цикле, прежде чем рекурсивно вызвать эту функцию для оставшейся части списка.

void recurse(std::vector<int>& a, int pos, int remaining) {
if (remaining == 0) { print(a); return; }
if (pos == a.size()) { return; }
for (int i = remaining; i >= 0; --i) {
a[pos] = i;
recurse(a, pos + 1, remaining - i);
}
}

void print_partitions(int sum_val, int n) {
std::vector<int> a(n);
recurse(a, 0, sum_val);
}

Подтверждение концепции запуска видно на http://ideone.com/oJNvmu.

Ваш комментарий ниже указывает на проблему с производительностью. Хотя представляется весьма вероятным, что ввод-вывод потребляет большую часть вашей производительности, здесь есть итеративное решение, которое позволяет избежать затрат на вызов функции рекурсивного подхода.

void print_partitions(int sum_val, int n) {
int pos = 0, last = n - 1;
int a[n]; // dynamic stack-allocated arrays are a gcc extension
for (int i = 1; i != n; ++i)
a[i] = 0;
a[0] = sum_val;
while (true) {
for (int i = 0; i != last; ++i)
printf("%3d ", a[i]);
printf("%3d\n", a[last]);
if (pos != last) {
--a[pos];
++pos;
a[pos] = 1;
}
else {
if (a[last] == sum_val)
return;
for (--pos; a[pos] == 0; --pos);
--a[pos];
int tmp = 1 + a[last];
++pos;
a[last] = 0;
a[pos] = tmp;
}
}
}

Общая идея и порядок, в котором печатаются вещи, такие же, как и для рекурсивного подхода. Вместо того, чтобы поддерживать счетчик remainingвсе токены (или что-то еще, что вы разделяете) немедленно сбрасываются в место, где они принадлежат для следующего раздела для печати. pos всегда последнее ненулевое поле. Если это не последний, то вы получите следующий раздел, взяв один токен из pos и переместить его на место после этого. Если это последний, то вы берете все жетоны с этого последнего места, находите последнее ненулевое место перед этим и также берете один жетон оттуда, а затем сбрасываете все эти жетоны на место после того, где вы взяли сингл. маркер.

Демо-версия на http://ideone.com/N3lSbQ.

2

Другие решения

Вы можете реализовать это самостоятельно:
такой раздел определяется 6 целыми числами 0 <= x[0] <= x[1] <= x[2] <= x[3] <= 2;
значения в соответствующем ряду — только различия x[0]-0, x[1]-x[0], x[2]-x[1], так далее.
Если число столбцов (5) фиксировано, у вас есть 4 вложенных цикла;
если это не так, вы можете сформулировать проблему рекурсивно.

1

А ты уже прошел курс программирования? Супер скидка!
Прокачать скилл $$$
×