给定数字与重复组合的算法？ C++

Question

所以 I 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

...

533,533,533,533

当我知道 N 和 M 是多少时，我知道如何手动执行此操作：

在 N 为 3 且 M 为 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;

}

但是我如何制定算法才能通过 std::cin 输入 N 和 M 并得到正确的结果？

谢谢。

Answer 1

通常执行动态嵌套 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});
}

输出

Answer 2

这里有一个解决这个问题的算法，它不使用递归。

假设 n=2 且 m=3。考虑以下对应于这些值的序列：

000 001 010 011 100 101 110 111

这里的意思是，看到0就取第一个数，看到1就取第二个数。因此给定输入数字 [5, 7]，则 000 = 555、001=557、010=575 等

上面的序列看起来与用 2 进制表示从 0 到 7 的数字相同。基本上，如果从 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;
}

输出：

Answer 3

这里完全不需要递归。这是动态规划的典型工作。只需为 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)));

Answer 4

第一个小提示：当我们有 RAII 和更快的数据结构时，不要在 C++ 中使用 "new" 或 C 风格的数组。

为了解决您的问题，我建议使用递归制作单独的函数。你说你知道如何手动完成，所以将其变成算法的第一步是逐步拆除你的手动解决方案。对于这个问题，当您手动解决它时，您基本上从所有第一个数字的数组开始，然后对于最后一个位置，您只需循环可用的数字。然后您转到倒数第二个位置并再次循环刚才可用的数字，不同之处在于对于那里的每个数字您还必须重复最后一个点数循环。这是递归。对于第 "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;
}

如果您有任何问题，请随时提出。

给定数字与重复组合的算法？ C++

Algorithm for Combinations of given numbers with repetition? C++

c++

algorithm

combinations

repeat