给定数字与重复的组合算法？ C ++ [英] Algorithm for Combinations of given numbers with repetition? C++

问题描述

所以我N-我必须输入数字，我得到M-这些数字的地方数字，我需要找到所有与给定数字重复的组合。

So I N - numbers I have to input, and I got M - numbers of places for those numbers and I need to find all combinations with repetition of given numbers.

这里是示例：

假设N是3（我必须输入3个数字），并且M是4。
例如，让我们输入数字：6 11和533。
这应该是结果

Let's say that N is 3(I Have to input 3 numbers), and M is 4. For example let's input numbers: 6 11 and 533. This should be result

6,6,6,6

6,6,6,11

6,6,6,533

6,6,6,533

6,6,11,6

...

533,533,533,533

533,533,533,533

当我知道N和M的多少时，我知道如何手动操作：

I know how to do that manualy when I know how much is N and M:

例如，N为3并且M为4：

In example where N is 3 and M is 4:

int main（）
{

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，并且得到正确的结果？

But how can I make algorithm so I can enter N and M via std::cin and I get correct resut?

谢谢。

推荐答案

第一个简短提示：当我们拥有RAII和更快的数据结构时，请不要在C ++中使用 new或C样式的数组。

First one short tip: don't use "new" or C-style arrays in C++ when we have RAII and much faster data structures.

对于您的问题的解决方案，我建议使用递归来构造单独的函数。您说您知道如何手动执行，因此使其成为算法的第一步是逐步拆除手动解决方案。对于这个问题，当您手动解决时，基本上是从所有第一个数字组成的数组开始，然后对于最后一个位置，只需遍历可用数字即可。然后，您转到倒数第二个位置，并再次循环遍历所有可用数字，不同之处在于，对于每个数字，您还必须重复最后一个现场数字循环。这是递归。对于第 n个位置，您必须循环访问所有可用数字，并且对于每个调用，第n + 1个数字均应使用相同的函数。

For the solution to your problem I would suggest making separate function with recursion. You said you know how to do it manually so the first step in making it into algorithm is to tear down you manual solution step by step. For this problem when you solve it by hand you basically start with array of all first numbers and then for last position you just loop through available numbers. Then you go to the second last position and again loop through available numbers just now with the difference that for every number there you must also repeat the last spot number loop. Here is the recursion. For every "n"th position you must loop through available numbers and for every call the same function for "n+1"th number.

这里是一种简化的解决方案，省略了输入处理和精确的打印，以使代码更短，更集中于该问题：

Here is a simplified solution, leaving out the input handling and exact print to keep code shorter and more focused on the problem:

#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;
}

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

If you have any questions feel free to ask.

这篇关于给定数字与重复的组合算法？ C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！