递归生成指定子集大小的可重复组合（C++）：代码修正问询

Hey there, let's sort out this problem. The core issue with your current code is that it’s generating permutations (where order matters) instead of combinations (where order doesn’t) because every recursive call starts picking elements from the very beginning of the input vector. For combinations with repetition, we need to enforce that once we select an element at position i, all subsequent elements in the combination are chosen from positions i or later in the input. This way, we never create duplicate ordered pairs, and we get exactly the desired combinations without any inefficient post-processing deduplication.

The Key Modification #

We’ll adjust the recursive helper function to take a start index parameter. This parameter tells the function where to begin iterating in the input vector for the next element in the combination. Here’s how to apply it:

1. Update the helpfunc signature to include the start index.
2. Change the loop to start from start instead of 0.
3. Pass the current index i as the new start parameter in the recursive call.

Modified Full Code #

#include <vector>
#include <iostream>
#include <string>

template <typename T>
void print_2d_vector(std::vector<std::vector<T>>& v) {
    for(int i = 0; i < v.size(); i++) {
        std::cout << "{";
        for(int j = 0; j < v[i].size(); j++) {
            std::cout << v[i][j];
            if(j != v[i].size() - 1) {
                std::cout << ", ";
            }
        }
        std::cout << "}\n";
    }
}

template <typename T>
struct permcomb2 {
    std::vector<std::vector<T>> end_set;
    std::vector<T>* data;
    permcomb2(std::vector<T>& param) : data(&param) {}
    
    // Added 'start' parameter to control iteration starting point
    void helpfunc(std::vector<T>& seen, int depth, int start) {
        if(depth == 0) {
            end_set.push_back(seen);
        } else {
            // Loop from 'start' instead of 0 to avoid permutations
            for(int i = start; i < (*data).size(); i++) {
                seen.push_back((*data)[i]);
                // Pass current index as the new start for next recursion
                helpfunc(seen, depth - 1, i);
                seen.pop_back();
            }
        }
    }
};

template <typename T>
std::vector<std::vector<T>> permtest(std::vector<T>& data, int subset_size) {
    permcomb2<T> helpstruct(data);
    std::vector<T> empty {};
    // Initial call starts at index 0
    helpstruct.helpfunc(empty, subset_size, 0);
    return helpstruct.end_set;
}

using namespace std;
int main() {
    std::vector<std::string> flavors {"Vanilla", "Chocolate", "Strawberry"};
    auto a1 = permtest(flavors, 2);
    cout << "Return all combinations with repetition\n";
    print_2d_vector(a1);
    return 0;
}

Output Verification #

When you run this modified code, it produces the exact expected output:

Return all combinations with repetition
{Vanilla, Vanilla}
{Vanilla, Chocolate}
{Vanilla, Strawberry}
{Chocolate, Chocolate}
{Chocolate, Strawberry}
{Strawberry, Strawberry}

Why This Works #

By restricting each recursive call to start iterating from the current element’s index, we ensure combinations are built in non-decreasing order relative to the input vector. This eliminates any permutations of the same combination, directly generating only the unique combinations with repetition we need. This approach is far more efficient than generating permutations first and deduplicating later, as it avoids wasting cycles creating and discarding duplicate entries entirely.

内容的提问来源于stack exchange，提问作者EllipticalInitial