c++ - 如何在 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 235 241 243 245 251 253 254 312 314 315 321 324 325 341 342 345 351 352 354 412 413 415 421 423 425 431 432 435 451 452 453 512 513 514 521 523 524 531 532 534 541 542 543