如何在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-loops的情况.有人能帮我吗？我是一个无知的人:

编辑:更好地解释我在寻找的是更多的例子.

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

编辑2:或者,如果您更喜欢更直观(数学？)的问题,那么您就去了.

考虑m维度.有了m2,你剩下一个N尺寸矩阵.我正在寻找这个矩阵的上(或下)三角形,包括对角线.让我们转向m = 3,矩阵成为一个三维立方体(如果你愿意的话,还是Tensor),现在我正在寻找包括对角平面的上(或下)四面体.对于比3更高的尺寸,我正在寻找超立方体的超四面体,包括超对角线平面.

Answer 1

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

以下通用算法允许客户端一次访问长度为 N, r 个项目的序列的每个组合或排列。

用法示例：

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只是一个中介，并且您的实际工作然后在其他地方使用它，您可以避免中介并简单地执行无论您需要直接在函子体内进行什么工作。

这是一个完整的工作示例，使用提供的链接中的代码。

因为你想要的是重复的组合而不仅仅是组合。下面是一个在此基础上实现此功能的示例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;
    });
}

维基百科关于组合的文章很好地说明了它的作用：它获取数字 [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}}。

因此，通常要使用它，您有一个向量或包含元素的东西，并使用该算法生成的范围作为该容器的索引。然而，在您的情况下，由于元素只是从 1 到 N 的数字，您可以通过向每个索引添加 1 来直接使用索引：

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';
});

完整示例

另一种实现可以返回表示每个类别计数的向量。例如，早期的 {{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;
    });
}