How can I make an algorithm in C++ for finding variations of a set without repetition (i.e. n elements,...
For example, (n = 3, k = 2)
, I have set {1, 2, 3}
and I need my algorithm to find:
{1, 2}, {1, 3}, {2, 1}, {2, 3}, {3, 1}, {3, 2}
.
I was able to make an algorithm with next_permutation
, but it works very slow for n = 10, k = 4
(which is what I need).
Here's my code:
#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;
}
How can I make an algorithm that does this faster?
c++ algorithm permutation
add a comment |
For example, (n = 3, k = 2)
, I have set {1, 2, 3}
and I need my algorithm to find:
{1, 2}, {1, 3}, {2, 1}, {2, 3}, {3, 1}, {3, 2}
.
I was able to make an algorithm with next_permutation
, but it works very slow for n = 10, k = 4
(which is what I need).
Here's my code:
#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;
}
How can I make an algorithm that does this faster?
c++ algorithm permutation
1
You might usenext_permutation
on abitset
(of size n, with k true). bitset shows valid item from thevector
.
– Jarod42
14 hours ago
@Jarod42 how do I usenext_permutation
onbitset
? I can't find how to.
– Pero
13 hours ago
add a comment |
For example, (n = 3, k = 2)
, I have set {1, 2, 3}
and I need my algorithm to find:
{1, 2}, {1, 3}, {2, 1}, {2, 3}, {3, 1}, {3, 2}
.
I was able to make an algorithm with next_permutation
, but it works very slow for n = 10, k = 4
(which is what I need).
Here's my code:
#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;
}
How can I make an algorithm that does this faster?
c++ algorithm permutation
For example, (n = 3, k = 2)
, I have set {1, 2, 3}
and I need my algorithm to find:
{1, 2}, {1, 3}, {2, 1}, {2, 3}, {3, 1}, {3, 2}
.
I was able to make an algorithm with next_permutation
, but it works very slow for n = 10, k = 4
(which is what I need).
Here's my code:
#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;
}
How can I make an algorithm that does this faster?
c++ algorithm permutation
c++ algorithm permutation
edited 2 hours ago
Peter Mortensen
13.7k1986112
13.7k1986112
asked 14 hours ago
PeroPero
456
456
1
You might usenext_permutation
on abitset
(of size n, with k true). bitset shows valid item from thevector
.
– Jarod42
14 hours ago
@Jarod42 how do I usenext_permutation
onbitset
? I can't find how to.
– Pero
13 hours ago
add a comment |
1
You might usenext_permutation
on abitset
(of size n, with k true). bitset shows valid item from thevector
.
– Jarod42
14 hours ago
@Jarod42 how do I usenext_permutation
onbitset
? I can't find how to.
– Pero
13 hours ago
1
1
You might use
next_permutation
on a bitset
(of size n, with k true). bitset shows valid item from the vector
.– Jarod42
14 hours ago
You might use
next_permutation
on a bitset
(of size n, with k true). bitset shows valid item from the vector
.– Jarod42
14 hours ago
@Jarod42 how do I use
next_permutation
on bitset
? I can't find how to.– Pero
13 hours ago
@Jarod42 how do I use
next_permutation
on bitset
? I can't find how to.– Pero
13 hours ago
add a comment |
4 Answers
4
active
oldest
votes
This code generates arrangements of k items from n in lexicographic order, packed into integer for simplicity (so 153 corresponds to (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
add a comment |
You can iterate over every subset with a bitmask.
for(unsigned int i = 0; i < (1<<10);i++)
When you do not need portable code you could use
__builtin_popcount(int)
To get the number of 1s in the binary representation at least in gcc with an x86 processor.
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);
}
}
I am aware of this, but this prints combinations, rather than variations, which is not what I need.
– Pero
13 hours ago
no need to use popcnt, you can use normal slower way of counting en.wikichip.org/wiki/population_count
– NoSenseEtAl
13 hours ago
@Pero when you have the combinations, you can use next permutation on these (which are much smaller)
– Unlikus
13 hours ago
add a comment |
The slowness is due to generating all n! permutations, even when only a fraction of them is required. Your complexity is around O(n! * k log n), where O(k log n) is an upper bound on the complexity to query the std::map
with all of the permutations.
The answer by MBo is limited to 9 values (1..9). Even if it is extended to printing longer values, they are still limited by number of bits (usually 31 for int, and 64 bit if uint64_t is available).
Here it is:
void print_permutations_impl(std::ostream & out, std::vector<int> & values,
unsigned k, std::vector<int> & permutation_stack)
{
if (k == permutation_stack.size())
{
const char* prefix = "";
for (auto elem: permutation_stack) {
out << prefix << elem;
prefix = ", ";
}
out << 'n';
return;
}
auto end_valid = values.size() - permutation_stack.size();
permutation_stack.push_back(0);
for (unsigned i=0 ; i < end_valid; ++i) {
permutation_stack.back() = values[i];
std::swap(values[i], values[end_valid - 1]);
print_permutations_impl(out, values, k, permutation_stack);
std::swap(values[i], values[end_valid - 1]);
}
permutation_stack.pop_back();
}
void print_permutations(std::ostream & out, const std::vector<int> & values, int k)
{
std::vector<int> unique = values;
std::sort(unique.begin(), unique.end());
unique.erase(std::unique(unique.begin(), unique.end()),
unique.end());
std::vector<int> current_permutation;
print_permutations_impl(out, unique, k, current_permutation);
}
It works in sub-second speed for N=100 and K=2.
add a comment |
//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);
}
}
This will not print in reverse order like you have done in you example. Print by reversing the arrays once and you will get your answer completely!
The idea behind this is :
1. Say you have 5 numbers : 1 2 3 4 5 and you want to choose 3 at a time then
2. Find the sub-arrays in serial order :
1 2 3
2 3 4
3 4 5
4 5 1
5 1 2
3. These will be first n sub-arrays of an array of length n
4. Now, take 1 from 1st sub-array and 3,4 from 2nd sub-array and make another sub-array from these 3 elements, then take 4,5 from 3rd sub-array and do the same. Do not take elements from last two sub arrays as after that the elements will start repeating.
5. Now take 1,2 from first sub-array and take 4 from 2nd sub-arr make one sub-array and take 5 from 3rd sub-arr and make one array
6. Push all these arrays back to the list of arrays you are having.
7. Do the same pattern from the 2nd sub-array but don't take elements from where the fist element of your array starts matching the last element that you will throw back from a sub-array below the array you are working on [ In the previous case the working sub-arr was 1st one and we didn't start taking elements from 4th sub array! ]
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54970636%2fhow-can-i-make-an-algorithm-in-c-for-finding-variations-of-a-set-without-repet%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
This code generates arrangements of k items from n in lexicographic order, packed into integer for simplicity (so 153 corresponds to (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
add a comment |
This code generates arrangements of k items from n in lexicographic order, packed into integer for simplicity (so 153 corresponds to (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
add a comment |
This code generates arrangements of k items from n in lexicographic order, packed into integer for simplicity (so 153 corresponds to (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
This code generates arrangements of k items from n in lexicographic order, packed into integer for simplicity (so 153 corresponds to (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
answered 13 hours ago
MBoMBo
49k23050
49k23050
add a comment |
add a comment |
You can iterate over every subset with a bitmask.
for(unsigned int i = 0; i < (1<<10);i++)
When you do not need portable code you could use
__builtin_popcount(int)
To get the number of 1s in the binary representation at least in gcc with an x86 processor.
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);
}
}
I am aware of this, but this prints combinations, rather than variations, which is not what I need.
– Pero
13 hours ago
no need to use popcnt, you can use normal slower way of counting en.wikichip.org/wiki/population_count
– NoSenseEtAl
13 hours ago
@Pero when you have the combinations, you can use next permutation on these (which are much smaller)
– Unlikus
13 hours ago
add a comment |
You can iterate over every subset with a bitmask.
for(unsigned int i = 0; i < (1<<10);i++)
When you do not need portable code you could use
__builtin_popcount(int)
To get the number of 1s in the binary representation at least in gcc with an x86 processor.
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);
}
}
I am aware of this, but this prints combinations, rather than variations, which is not what I need.
– Pero
13 hours ago
no need to use popcnt, you can use normal slower way of counting en.wikichip.org/wiki/population_count
– NoSenseEtAl
13 hours ago
@Pero when you have the combinations, you can use next permutation on these (which are much smaller)
– Unlikus
13 hours ago
add a comment |
You can iterate over every subset with a bitmask.
for(unsigned int i = 0; i < (1<<10);i++)
When you do not need portable code you could use
__builtin_popcount(int)
To get the number of 1s in the binary representation at least in gcc with an x86 processor.
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);
}
}
You can iterate over every subset with a bitmask.
for(unsigned int i = 0; i < (1<<10);i++)
When you do not need portable code you could use
__builtin_popcount(int)
To get the number of 1s in the binary representation at least in gcc with an x86 processor.
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);
}
}
answered 13 hours ago
UnlikusUnlikus
876
876
I am aware of this, but this prints combinations, rather than variations, which is not what I need.
– Pero
13 hours ago
no need to use popcnt, you can use normal slower way of counting en.wikichip.org/wiki/population_count
– NoSenseEtAl
13 hours ago
@Pero when you have the combinations, you can use next permutation on these (which are much smaller)
– Unlikus
13 hours ago
add a comment |
I am aware of this, but this prints combinations, rather than variations, which is not what I need.
– Pero
13 hours ago
no need to use popcnt, you can use normal slower way of counting en.wikichip.org/wiki/population_count
– NoSenseEtAl
13 hours ago
@Pero when you have the combinations, you can use next permutation on these (which are much smaller)
– Unlikus
13 hours ago
I am aware of this, but this prints combinations, rather than variations, which is not what I need.
– Pero
13 hours ago
I am aware of this, but this prints combinations, rather than variations, which is not what I need.
– Pero
13 hours ago
no need to use popcnt, you can use normal slower way of counting en.wikichip.org/wiki/population_count
– NoSenseEtAl
13 hours ago
no need to use popcnt, you can use normal slower way of counting en.wikichip.org/wiki/population_count
– NoSenseEtAl
13 hours ago
@Pero when you have the combinations, you can use next permutation on these (which are much smaller)
– Unlikus
13 hours ago
@Pero when you have the combinations, you can use next permutation on these (which are much smaller)
– Unlikus
13 hours ago
add a comment |
The slowness is due to generating all n! permutations, even when only a fraction of them is required. Your complexity is around O(n! * k log n), where O(k log n) is an upper bound on the complexity to query the std::map
with all of the permutations.
The answer by MBo is limited to 9 values (1..9). Even if it is extended to printing longer values, they are still limited by number of bits (usually 31 for int, and 64 bit if uint64_t is available).
Here it is:
void print_permutations_impl(std::ostream & out, std::vector<int> & values,
unsigned k, std::vector<int> & permutation_stack)
{
if (k == permutation_stack.size())
{
const char* prefix = "";
for (auto elem: permutation_stack) {
out << prefix << elem;
prefix = ", ";
}
out << 'n';
return;
}
auto end_valid = values.size() - permutation_stack.size();
permutation_stack.push_back(0);
for (unsigned i=0 ; i < end_valid; ++i) {
permutation_stack.back() = values[i];
std::swap(values[i], values[end_valid - 1]);
print_permutations_impl(out, values, k, permutation_stack);
std::swap(values[i], values[end_valid - 1]);
}
permutation_stack.pop_back();
}
void print_permutations(std::ostream & out, const std::vector<int> & values, int k)
{
std::vector<int> unique = values;
std::sort(unique.begin(), unique.end());
unique.erase(std::unique(unique.begin(), unique.end()),
unique.end());
std::vector<int> current_permutation;
print_permutations_impl(out, unique, k, current_permutation);
}
It works in sub-second speed for N=100 and K=2.
add a comment |
The slowness is due to generating all n! permutations, even when only a fraction of them is required. Your complexity is around O(n! * k log n), where O(k log n) is an upper bound on the complexity to query the std::map
with all of the permutations.
The answer by MBo is limited to 9 values (1..9). Even if it is extended to printing longer values, they are still limited by number of bits (usually 31 for int, and 64 bit if uint64_t is available).
Here it is:
void print_permutations_impl(std::ostream & out, std::vector<int> & values,
unsigned k, std::vector<int> & permutation_stack)
{
if (k == permutation_stack.size())
{
const char* prefix = "";
for (auto elem: permutation_stack) {
out << prefix << elem;
prefix = ", ";
}
out << 'n';
return;
}
auto end_valid = values.size() - permutation_stack.size();
permutation_stack.push_back(0);
for (unsigned i=0 ; i < end_valid; ++i) {
permutation_stack.back() = values[i];
std::swap(values[i], values[end_valid - 1]);
print_permutations_impl(out, values, k, permutation_stack);
std::swap(values[i], values[end_valid - 1]);
}
permutation_stack.pop_back();
}
void print_permutations(std::ostream & out, const std::vector<int> & values, int k)
{
std::vector<int> unique = values;
std::sort(unique.begin(), unique.end());
unique.erase(std::unique(unique.begin(), unique.end()),
unique.end());
std::vector<int> current_permutation;
print_permutations_impl(out, unique, k, current_permutation);
}
It works in sub-second speed for N=100 and K=2.
add a comment |
The slowness is due to generating all n! permutations, even when only a fraction of them is required. Your complexity is around O(n! * k log n), where O(k log n) is an upper bound on the complexity to query the std::map
with all of the permutations.
The answer by MBo is limited to 9 values (1..9). Even if it is extended to printing longer values, they are still limited by number of bits (usually 31 for int, and 64 bit if uint64_t is available).
Here it is:
void print_permutations_impl(std::ostream & out, std::vector<int> & values,
unsigned k, std::vector<int> & permutation_stack)
{
if (k == permutation_stack.size())
{
const char* prefix = "";
for (auto elem: permutation_stack) {
out << prefix << elem;
prefix = ", ";
}
out << 'n';
return;
}
auto end_valid = values.size() - permutation_stack.size();
permutation_stack.push_back(0);
for (unsigned i=0 ; i < end_valid; ++i) {
permutation_stack.back() = values[i];
std::swap(values[i], values[end_valid - 1]);
print_permutations_impl(out, values, k, permutation_stack);
std::swap(values[i], values[end_valid - 1]);
}
permutation_stack.pop_back();
}
void print_permutations(std::ostream & out, const std::vector<int> & values, int k)
{
std::vector<int> unique = values;
std::sort(unique.begin(), unique.end());
unique.erase(std::unique(unique.begin(), unique.end()),
unique.end());
std::vector<int> current_permutation;
print_permutations_impl(out, unique, k, current_permutation);
}
It works in sub-second speed for N=100 and K=2.
The slowness is due to generating all n! permutations, even when only a fraction of them is required. Your complexity is around O(n! * k log n), where O(k log n) is an upper bound on the complexity to query the std::map
with all of the permutations.
The answer by MBo is limited to 9 values (1..9). Even if it is extended to printing longer values, they are still limited by number of bits (usually 31 for int, and 64 bit if uint64_t is available).
Here it is:
void print_permutations_impl(std::ostream & out, std::vector<int> & values,
unsigned k, std::vector<int> & permutation_stack)
{
if (k == permutation_stack.size())
{
const char* prefix = "";
for (auto elem: permutation_stack) {
out << prefix << elem;
prefix = ", ";
}
out << 'n';
return;
}
auto end_valid = values.size() - permutation_stack.size();
permutation_stack.push_back(0);
for (unsigned i=0 ; i < end_valid; ++i) {
permutation_stack.back() = values[i];
std::swap(values[i], values[end_valid - 1]);
print_permutations_impl(out, values, k, permutation_stack);
std::swap(values[i], values[end_valid - 1]);
}
permutation_stack.pop_back();
}
void print_permutations(std::ostream & out, const std::vector<int> & values, int k)
{
std::vector<int> unique = values;
std::sort(unique.begin(), unique.end());
unique.erase(std::unique(unique.begin(), unique.end()),
unique.end());
std::vector<int> current_permutation;
print_permutations_impl(out, unique, k, current_permutation);
}
It works in sub-second speed for N=100 and K=2.
edited 9 hours ago
answered 9 hours ago
Michael VekslerMichael Veksler
3,4471517
3,4471517
add a comment |
add a comment |
//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);
}
}
This will not print in reverse order like you have done in you example. Print by reversing the arrays once and you will get your answer completely!
The idea behind this is :
1. Say you have 5 numbers : 1 2 3 4 5 and you want to choose 3 at a time then
2. Find the sub-arrays in serial order :
1 2 3
2 3 4
3 4 5
4 5 1
5 1 2
3. These will be first n sub-arrays of an array of length n
4. Now, take 1 from 1st sub-array and 3,4 from 2nd sub-array and make another sub-array from these 3 elements, then take 4,5 from 3rd sub-array and do the same. Do not take elements from last two sub arrays as after that the elements will start repeating.
5. Now take 1,2 from first sub-array and take 4 from 2nd sub-arr make one sub-array and take 5 from 3rd sub-arr and make one array
6. Push all these arrays back to the list of arrays you are having.
7. Do the same pattern from the 2nd sub-array but don't take elements from where the fist element of your array starts matching the last element that you will throw back from a sub-array below the array you are working on [ In the previous case the working sub-arr was 1st one and we didn't start taking elements from 4th sub array! ]
add a comment |
//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);
}
}
This will not print in reverse order like you have done in you example. Print by reversing the arrays once and you will get your answer completely!
The idea behind this is :
1. Say you have 5 numbers : 1 2 3 4 5 and you want to choose 3 at a time then
2. Find the sub-arrays in serial order :
1 2 3
2 3 4
3 4 5
4 5 1
5 1 2
3. These will be first n sub-arrays of an array of length n
4. Now, take 1 from 1st sub-array and 3,4 from 2nd sub-array and make another sub-array from these 3 elements, then take 4,5 from 3rd sub-array and do the same. Do not take elements from last two sub arrays as after that the elements will start repeating.
5. Now take 1,2 from first sub-array and take 4 from 2nd sub-arr make one sub-array and take 5 from 3rd sub-arr and make one array
6. Push all these arrays back to the list of arrays you are having.
7. Do the same pattern from the 2nd sub-array but don't take elements from where the fist element of your array starts matching the last element that you will throw back from a sub-array below the array you are working on [ In the previous case the working sub-arr was 1st one and we didn't start taking elements from 4th sub array! ]
add a comment |
//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);
}
}
This will not print in reverse order like you have done in you example. Print by reversing the arrays once and you will get your answer completely!
The idea behind this is :
1. Say you have 5 numbers : 1 2 3 4 5 and you want to choose 3 at a time then
2. Find the sub-arrays in serial order :
1 2 3
2 3 4
3 4 5
4 5 1
5 1 2
3. These will be first n sub-arrays of an array of length n
4. Now, take 1 from 1st sub-array and 3,4 from 2nd sub-array and make another sub-array from these 3 elements, then take 4,5 from 3rd sub-array and do the same. Do not take elements from last two sub arrays as after that the elements will start repeating.
5. Now take 1,2 from first sub-array and take 4 from 2nd sub-arr make one sub-array and take 5 from 3rd sub-arr and make one array
6. Push all these arrays back to the list of arrays you are having.
7. Do the same pattern from the 2nd sub-array but don't take elements from where the fist element of your array starts matching the last element that you will throw back from a sub-array below the array you are working on [ In the previous case the working sub-arr was 1st one and we didn't start taking elements from 4th sub array! ]
//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);
}
}
This will not print in reverse order like you have done in you example. Print by reversing the arrays once and you will get your answer completely!
The idea behind this is :
1. Say you have 5 numbers : 1 2 3 4 5 and you want to choose 3 at a time then
2. Find the sub-arrays in serial order :
1 2 3
2 3 4
3 4 5
4 5 1
5 1 2
3. These will be first n sub-arrays of an array of length n
4. Now, take 1 from 1st sub-array and 3,4 from 2nd sub-array and make another sub-array from these 3 elements, then take 4,5 from 3rd sub-array and do the same. Do not take elements from last two sub arrays as after that the elements will start repeating.
5. Now take 1,2 from first sub-array and take 4 from 2nd sub-arr make one sub-array and take 5 from 3rd sub-arr and make one array
6. Push all these arrays back to the list of arrays you are having.
7. Do the same pattern from the 2nd sub-array but don't take elements from where the fist element of your array starts matching the last element that you will throw back from a sub-array below the array you are working on [ In the previous case the working sub-arr was 1st one and we didn't start taking elements from 4th sub array! ]
edited 10 hours ago
answered 10 hours ago
brightprogrammerbrightprogrammer
308
308
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54970636%2fhow-can-i-make-an-algorithm-in-c-for-finding-variations-of-a-set-without-repet%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
You might use
next_permutation
on abitset
(of size n, with k true). bitset shows valid item from thevector
.– Jarod42
14 hours ago
@Jarod42 how do I use
next_permutation
onbitset
? I can't find how to.– Pero
13 hours ago