如何在C ++中创建一种算法来查找集合的变体而无需重复（即n个元素，选择k）？

Question

例如，(n = 3, k = 2)我已经设置了，{1, 2, 3}并且我需要算法来查找： {1, 2}, {1, 3}, {2, 1}, {2, 3}, {3, 1}, {3, 2}。

我能够使用制作算法next_permutation，但是它的工作速度非常慢n = 10, k = 4（这是我需要的）。

这是我的代码：

#include <iostream>
#include <algorithm>

#define pb push_back

using namespace std;

int main() {
    vector <int> s = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int k = 4; // (n = 10, k = 4)
    map <string, int> m; // To check if we already have that variation

    vector <string> v; // Variations
    do {
        string str = "";
        for (int i = 0; i < k; i++) str += to_string(s[i]);
        if (m[str] == 0) {
            m[str] = 1;
            v.pb(str);
        }
    } while (next_permutation(s.begin(), s.end()));

    return 0;
}

我怎样才能使算法更快呢？

Answer 1

此代码按字典顺序从n生成k个项的排列，为简单起见，打包为整数（因此153对应于（1,5,3））

void GenArrangement(int n, int k, int idx, int used, int arran) {
    if (idx == k) {
        std::cout << arran << std::endl;
        return;
    }

    for (int i = 0; i < n; i++) 
        if (0 == (used & (1 << i))) 
            GenArrangement(n, k, idx + 1, used | (1 << i), arran * 10 + (i + 1));
}

int main()
{
    GenArrangement(5, 3, 0, 0, 0);
}

123 124 125 132 134 135 142 143 145 152 153 154 213 214 215 231 234 241 243 243 251 251 253 254 312 314 315 321 324 324 341 342 345 345 352 354 412 413 413 415 421 423 425 425 431 435 451 452 453 512 435 514521523524531532534541542542543