c++ - 如何在 C++ 中避免这种 for 循环困惑？

Question

我需要对从 1 到 N 的所有可能的数字集进行编程，以获得任意数量的 m 整数，无需排列。

由于我不知道如何更好地解释它，这里有一些例子:

对于 m = 2

vector<vector<int>> box;    
int N = 5;

for(int i = 1; i <= N; i++) {
    for(int j = N; j >= i; j--) {
        vector<int> dummy;
        dummy.push_back(i);
        dummy.push_back(j);
        box.push_back(dummy);
    }
}

对于 m = 3

vector<vector<int>> box;    
int N = 5;  

for(int i = 1; i <= N; i++) {
    for(int j = N; j >= i; j--) {
        for(int k = N; k >= j; k--) {
            vector<int> dummy;
            dummy.push_back(i);
            dummy.push_back(j);
            dummy.push_back(k);
            box.push_back(dummy);
        }
    }
}

这工作得很好，结果正是我需要的。但是就像已经提到的那样，m 可以是任意的，我懒得为 m = 37 或其他任何东西实现它。 N 和 m 是已知值，但会在程序运行时发生变化。必须有比 m = 37 情况下实现一行 37-for 循环更好的方法来实现这一点。有人能帮我吗？我有点无能为力:\

编辑:为了更好地解释我在这里寻找的是一些更多的例子。

假设 N = 5 和 m = 4，1223 对我来说是一个可行的解决方案，124 不是因为它太短了。假设我已经找到 1223 作为解决方案，而不需要 2123、2213 或此数字的任何其他排列。

edit2:或者，如果您更喜欢更直观(数学？)的问题表述，您可以这样做。

考虑 m 维度。当 m 为 2 时，您将得到一个 N 大小的矩阵。我正在寻找这个矩阵的上(或下)三角形，包括对角线。让我们移动到 m = 3，矩阵变为 3 维立方体(如果您愿意，也可以是 Tensor)，现在我正在寻找上(或下)四面体，包括对角平面。对于大于 3 的维度，我正在寻找包括超对角平面在内的超立方体的超四面体。

Answer 1

http://howardhinnant.github.io/combinations.html

The following generic algorithms permit a client to visit every combination or permuation of a sequence of length N, r items at time.

示例用法:

std::vector<std::vector<int>> box;  

std::vector<int> v(N);
std::iota(begin(v), end(v), 1);

for_each_combination(begin(v), begin(v) + M, end(v), [](auto b, auto e) {
    box.emplace_back(b, e);
    return false;
});

上面的代码只是将每个组合插入到 box 中作为示例，但您可能不想真正这样做:假设 box 只是一个中介并且你的实际工作然后在其他地方使用它，你可以避免中介，直接在仿函数的主体中直接做你需要的任何工作。

这是一个 complete, working example使用提供的链接中的代码。

---

因为您想要的是重复的组合，而不仅仅是组合。下面是在 for_each_combination() 之上实现它的示例:

template<typename Func>
void for_each_combination_with_repetition(int categories, int slots, Func func) {
    std::vector<int> v(slots + categories - 1);
    std::iota(begin(v), end(v), 1);

    std::vector<int> indices;
    for_each_combination(begin(v), begin(v) + slots, end(v), [&](auto b, auto e) {
        indices.clear();
        int last = 0;
        int current_element = 0;

        for(;b != e; ++last) {
            if (*b == last+1) {
                indices.push_back(current_element);
                ++b;
            } else {
                ++current_element;
            }
        }
        func(begin(indices), end(indices));
        return false;
    });
}

维基百科 article on combinations很好地说明了这是在做什么:它获取数字 [0, N + M - 1) 的所有组合(不重复)，然后寻找结果中的“差距”。间隙表示从一个元素的重复到下一个元素的重复的过渡。

您传递给该算法的仿函数被赋予一个范围，该范围包含指向包含您正在组合的元素的集合的索引。例如，如果你想从 {x,y} 的集合中获取所有三个元素的集合，你想要的结果是 {{x,x,x}, {x,x,y}, {x,y, y}, {y,y,y}}，此算法通过将索引范围返回到(有序的)集合 {x,y} 中来表示:{{0,0,0}, {0,0,1} , {0,1,1}, {1,1,1}}。

所以通常要使用它，你有一个 vector 或包含你的元素的东西，并使用这个算法产生的范围作为该容器的索引。但是在您的情况下，由于元素只是从 1 到 N 的数字，您可以通过向每个索引加一来直接使用索引:

for_each_combination_with_repetition(N, M, [&](auto b, auto e) {
    for(; b != e; ++b) {
        int index = *b;
        std::cout << index + 1 << " ";
    }
    std::cout << '\n';
});

Complete example

---

另一种实现可以返回表示每个类别计数的 vector 。例如。较早的 {{x,x,x}, {x,x,y}, {x,y,y}, {y,y,y}} 结果可以表示为:{{3,0} {2, 1},{1,2},{0,3}}。修改实现以生成此表示，而不是像这样:

template<typename Func>
void for_each_combination_with_repetition(int categories, int slots, Func func) {
    std::vector<int> v(slots + categories - 1);
    std::iota(begin(v), end(v), 1);

    std::vector<int> repetitions(categories);
    for_each_combination(begin(v), begin(v) + slots, end(v), [&](auto b, auto e) {
        std::fill(begin(repetitions), end(repetitions), 0);

        int last = 0;
        int current_element = 0;

        for(;b != e; ++last) {
            if (*b == last+1) {
                ++repetitions[current_element];
                ++b;
            } else {
                ++current_element;
            }
        }
        func(begin(repetitions), end(repetitions));
        return false;
    });
}