例如,(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;
}
我怎样才能制作一个更快的算法?
此代码按字典顺序从 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
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句