1...n 中 k 的组合按字典顺序排列，算法太慢

Question

下面是一种方法（使用回溯法）列出区间 [1,n] 之外的 k 个数字的所有可能组合，按字典顺序。不允许重复。
即：

输入：

5 3

输出：

我想越来越多地构建序列：一旦我将第一个数组元素设置为 1，我只需要从 2 迭代到 e_m - (n - 2) 第二个元素；一旦后者达到 3，那么第三个元素只会从 4 变为 e_m - (n - 3)，等等。我不知道该怎么做，你能帮忙吗？下面的方法构建了所有n个数字≤el_maxim的序列，然后只显示那些递增的..在线编译器不会接受这个，因为它太慢了

#include <iostream>
using namespace std;
int sol[20], n , el_maxim;
void display()
{
    for (int i = 0; i < n; i++)
        cout << sol[i] << " ";
    cout << endl;
}
int okay()
{
    for (int i = 0; i < n - 1; i++)
        if (sol[i] >= sol[i + 1])
            return 0;
    return 1;
}
void bkt(int poz)
{
    if (poz == n)
    {
        okay();
        if (okay() == 1)
            display();
    }
    else
        for (int i = 1; i <= el_maxim; i++)
        {
            sol[poz] = i;
            bkt(poz + 1);
        }
}
int main()
{
    cin >> el_maxim >> n;
    bkt(0);
    return 0;
}

Answer 1

这是一些工作代码。这个想法是记住您使用的最后一个元素，以便不再尝试使用它。您可以使用参数记住函数调用之间的变量。

为了加快速度，您可以删除 okay() 函数，并在到达 pos == n 时始终调用 display()，因为可以保证在到达时您会得到正确答案。我在我的代码中这样做了。

#include <iostream>

using namespace std;
int sol[20], n , el_maxim;
void display()
{
    for (int i = 0; i < n; i++)
        cout << sol[i] << " ";
    cout << endl;
}
void bkt(int poz, int last_element)
{
    if (poz == n)
    {
         display();
    }
    else{
        for (int i = last_element + 1; i <= el_maxim; i++)
        {
            sol[poz] = i;
            bkt(poz + 1, i);
        }
    }
}
int main()
{
    cin >> el_maxim >> n;
    bkt(0, 0);
    return 0;
}

Answer 2

一个简单的详尽搜索就足够了。如果将来不需要数组，我们也可以在 O(K) 额外 space 中完成。

#include <iostream>
#include <vector>

using namespace std;

void foo(vector<int>& sol, int N, int K, int n = 1, int k = 1)
{
    if (k > K)
    {
        for (int e : sol)
            cout << e << ' ';
        cout << endl;
        return;
    }

    for (int i = n; i <= N; ++i)
    {
        sol.push_back(i);
        foo(sol, N, K, i + 1, k + 1);
        sol.pop_back();
    }
}

int main()
{
    int N, K;
    cin >> N >> K;

    vector<int> sol;
    foo(sol, N, K);
}

1...n 中 k 的组合按字典顺序排列，算法太慢

Combinations of k of 1...n in lexycographical order, algorithm too slow

c++

combinatorics

backtracking