我如何在C++中创建一个算法来寻找集合的变体而不重复(即n个元素，选择k)？
例如，(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;
}我怎样才能让算法做得更快呢？
回答 4
Stack Overflow用户
发布于 2019-03-04 01:09:20
此代码按照字典顺序从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 152 153 154 213 214 215 231 234 235 241 243 245 251 253 254 312 314 315 321 325 341 342 345 351 352 354 412 413 415 421 423 425 431 432 435 451 452 453 512 514 521 523 524 531 532 534 541 542 543
Stack Overflow用户
发布于 2019-03-04 00:53:01
您可以使用位掩码遍历每个子集。
for(unsigned int i = 0; i < (1<<10);i++)当您不需要可移植代码时，可以使用
__builtin_popcount(int)为了获得二进制表示中的1的数量，至少在具有x86处理器的gcc中是这样。
for(unsigned int i = 0; i < (1<<10);i++) {
if(__builtin_popcount(i) == 4) { //Check if this subset contains exactly 4 elements
std::string s;
for(int j = 0; j < 10; j++) {
if(i&(1<<j)) { //Check if the bit on the j`th is a one
s.push_back(to_string(j));
}
}
v.push_back(s);
}
}Stack Overflow用户
发布于 2019-03-04 03:30:25
//finds permutations of an array
#include<iostream>
#include<vector>
using namespace std;
inline void vec_in(vector<unsigned>&, unsigned&);
inline void vec_out(vector<unsigned>&);
inline void vec_sub(vector<vector<unsigned>>&, vector<unsigned>&, unsigned&);
int main(){
unsigned size;
cout<<"SIZE : ";
cin>>size;
vector<unsigned> vec;
vec_in(vec,size);
unsigned choose;
cout<<"CHOOSE : ";
cin>>choose;
vector<vector<unsigned>> sub;
vec_sub(sub, vec, choose);
size=sub.size();
for(unsigned y=0; y<size-2; y++){
for(unsigned j=0; j<choose-1; j++){
vector<unsigned> temp;
for(unsigned i=0; i<=j; i++){
temp.push_back(sub[y][i]);
}
for(unsigned x=y+1; x<size; x++){
if(temp[0]==sub[x][choose-1]){break;}
vector<unsigned> _temp;
_temp=temp;
for(unsigned i=j+1; i<choose; i++){
_temp.push_back(sub[x][i]);
}
sub.push_back(_temp);
}
}
}
cout<<sub.size()<<endl;
for(unsigned i=0; i<sub.size(); i++){
vec_out(sub[i]);
}
return 0;
}
inline void vec_in(vector<unsigned>& vec, unsigned& size){
for(unsigned i=0; i<size; i++){
unsigned k;
cin>>k;
vec.push_back(k);
}
}
inline void vec_out(vector<unsigned>& vec){
for(unsigned i=0; i<vec.size(); i++){
cout<<vec[i]<<" ";
}
cout<<endl;
}
inline void vec_sub(vector<vector<unsigned>>& sub, vector<unsigned>& vec,
unsigned& size){
for(unsigned i=0; i<vec.size(); i++){
//if(i+size==vec.size()){break;}
vector<unsigned> temp;
unsigned x=i;
for(unsigned k=0; k<size; k++){
temp.push_back(vec[x]);
x++;
if(x==vec.size()){x=0;}
}
sub.push_back(temp);
}
}这将不会像您在示例中那样以相反的顺序打印。通过将数组反转一次来打印，您将得到完整的答案！
这背后的想法是：
假设你有5个数字:1，2，3，4，5，然后你想一次选择3
按串行顺序查找子数组：
1 2 3
2 3 4
3 4 5
4 5 1
5 1 2
这些将是长度为n的数组的前n个子数组
现在，从第一个子数组中取1，从第二个子数组中取3,4，并从这3个元素中生成另一个子数组，然后从第三个子数组中取4,5，并执行相同的操作。不要从最后两个子数组中获取元素，因为之后元素将开始重复。
现在从第一个子数组中取1,2，从第二个子数组中取4，生成一个子数组，从第三个子数组中取5，并生成一个数组
将所有这些数组推回到您所拥有的数组列表中。
在第二个子数组中做同样的操作，但是不要从你的数组的第一个元素开始的地方获取元素，而不是从你正在处理的数组下面的一个子数组中抛出的最后一个元素，在前面的例子中，工作子数组是第一个，我们没有开始从第四个子数组中获取元素！
https://stackoverflow.com/questions/54970636
复制相似问题