Алгоритм сочетания заданных чисел с повторением? Переполнение стека

Question

Алгоритм сочетания заданных чисел с повторением? Переполнение стека

Поэтому я должен ввести N N чисел, и я получил M — количество мест для этих чисел, и мне нужно найти все комбинации с повторением заданных чисел.

Вот пример:

Допустим, N равно 3 (мне нужно ввести 3 числа), а M равно 4.
Например, давайте введем числа: 6 11 и 533.
Это должно быть результатом

6,6,6,6

6,6,6,11

6,6,6,533

6,6,11,6

…

533533533533

Я знаю, как сделать это вручную, когда я знаю, сколько стоят N и M:

В примере, где N равно 3, а М равно 4:

int main ()
{

int N = 3;
int M = 4;

int *numbers = new int[N + 1];

for (int i = 0; i < N; i++)
cin >> numbers[i];

for (int a = 0; a < N; a++)
for (int b = 0; b < N; b++)
for (int c = 0; c < N; c++)
for (int d = 0; d < N; d++)
{
cout << numbers[a] << " " << numbers[b] << " " << numbers[c] << " " << numbers[d] << endl;
}
return 0;

}

Но как я могу сделать алгоритм, чтобы я мог ввести N и M через std :: cin и получить правильный результат?

Благодарю.

2

algorithm c++combinations repetition

Решение

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

Абсолютно нет необходимости в рекурсии здесь. Это типичная работа для динамического программирования. Просто получите первое решение правильно для n = 1 (1 слот доступно), что означает, что ответ [[6],[11],[533]] и затем переходите один за другим, полагаясь на ранее запомненное решение.

Извините, что я не владею C, но в JS это решение. Я надеюсь, что это помогает.

function combosOfN(a,n){
var res = {};
for(var i = 1; i <= n; i++) res[i] = res[i-1] ? res[i-1].reduce((r,e) => r.concat(a.map(n => e.concat(n))),[])
: a.map(e => [e]);
return res[n];
}

var arr = [6,11,533],
n = 4;
console.log(JSON.stringify(combosOfN(arr,n)));

2

Обычно самый простой способ создания динамических вложенных циклов for — это создать свой собственный стек и использовать рекурсию.

#include <iostream>
#include <vector>

void printCombinations(int sampleCount, const std::vector<int>& options, std::vector<int>& numbersToPrint) {
if (numbersToPrint.size() == sampleCount) {
// got all the numbers we need, print them.
for (int number : numbersToPrint) {
std::cout << number << " ";
}
std::cout << "\n";
}
else {
// Add a new number, iterate over all possibilities
numbersToPrint.push_back(0);
for (int number : options) {
numbersToPrint.back() = number;
printCombinations(sampleCount, options, numbersToPrint);
}
numbersToPrint.pop_back();
}
}void printCombinations(int sampleCount, const std::vector<int>& options)     {
std::vector<int> stack;
printCombinations(sampleCount, options, stack);
}int main()
{
printCombinations(3, {1,2,3});
}

выход

1

Вот алгоритм для решения этой проблемы, который не использует рекурсию.

Допустим, n = 2 и m = 3. Рассмотрим следующую последовательность, которая соответствует этим значениям:

000
001
010
011
100
101
110
111

Смысл этого в том, что когда вы видите 0, вы берете первое число, а когда вы видите 1, вы берете второе число. Таким образом, с учетом входных чисел [5, 7], тогда 000 = 555, 001 = 557, 010 = 575 и т. Д.

Вышеприведенная последовательность выглядит идентично представлению чисел от 0 до 7 в базе 2. В основном, если вы переходите от 0 до 7 и представляете числа в базе 2, у вас есть последовательность выше.

Если вы берете n = 3, m = 4, то вам нужно работать в базе 3:
0000
0001
0002
0010
0011
0012
….

Итак, вы перебираете все числа от 0 до 63 (4 ^ 3-1), представляете их в базе 3 и следуете кодировке: 0 = первое число, 1 = второе число, 2 = третье число и 3 = четвертое число.

В общем случае вы переходите от 0 к M ^ N-1, представляете каждое число в базе N и применяете кодировку 0 = первое число и т. Д.

Вот пример кода:

#include <stdio.h>
#include <math.h>

void convert_to_base(int number, char result[], int base, int number_of_digits) {
for (int i = number_of_digits - 1; i >= 0; i--) {
int remainder = number % base;
number = number / base;
result[i] = '0' + remainder;
}
}int main() {
int n = 2, m = 3;

int num = pow(n, m) - 1;
for (int i = 0; i <= num; i++) {
char str[33];

convert_to_base(i, str, n, m);
printf("%s\n", str);
}

return 0;
}

Выход:

1

Источник

Accepted Answer

Первый краткий совет: не используйте массивы «new» или C-style в C ++, когда у нас RAII и гораздо более быстрые структуры данных.

Для решения вашей проблемы я бы предложил сделать отдельную функцию с рекурсией. Вы сказали, что знаете, как сделать это вручную, поэтому первый шаг в превращении его в алгоритм состоит в том, чтобы постепенно разрушать ваше ручное решение. Для решения этой проблемы, когда вы решаете ее вручную, вы в основном начинаете с массива всех первых чисел, а затем для последней позиции вы просто просматриваете доступные числа. Затем вы переходите на вторую последнюю позицию и снова просматриваете доступные номера только сейчас, с той разницей, что для каждого номера вы также должны повторить цикл последнего места. Вот рекурсия. Для каждой «n» -ой позиции вы должны циклически перебирать доступные номера и для каждого вызова одну и ту же функцию для «n + 1» -го номера.

Вот упрощенное решение, исключающее обработку ввода и точную печать, чтобы сделать код короче и более сфокусированным на проблеме:

#include <vector>
#include <iostream>

void printCombinations(const std::vector<int>& numbers, unsigned size, std::vector<int>& line) {
for (unsigned i = 0; i < numbers.size(); i++) {
line.push_back(numbers[i]);
if (size <= 1) { // Condition that prevents infinite loop in recursion
for (const auto& j : line)
std::cout << j << ","; // Simplified print to keep code shorter
std::cout << std::endl;
line.erase(line.end() - 1);
} else {
printCombinations(numbers, size - 1, line); // Recursion happens here
line.erase(line.end() - 1);
}
}
}

int main() {
std::vector<int> numbers = {6, 11, 533};
unsigned size = 4;
std::vector<int> line;
printCombinations(numbers, size, line);
return 0;
}

Если у вас есть вопросы, не стесняйтесь спросить.

1