c++ How can I make an algorithm for finding variations of a set without repetition (i.e. n elements, choose...












6















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?










share|improve this question




















  • 1





    You might use next_permutation on a bitset (of size n, with k true). bitset shows valid item from the vector.

    – Jarod42
    9 hours ago













  • @Jarod42 how do I use next_permutation on bitset? I can't find how to.

    – Pero
    8 hours ago
















6















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?










share|improve this question




















  • 1





    You might use next_permutation on a bitset (of size n, with k true). bitset shows valid item from the vector.

    – Jarod42
    9 hours ago













  • @Jarod42 how do I use next_permutation on bitset? I can't find how to.

    – Pero
    8 hours ago














6












6








6








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?










share|improve this question
















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






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited 2 hours ago









jwodder

33.6k45684




33.6k45684










asked 9 hours ago









PeroPero

406




406








  • 1





    You might use next_permutation on a bitset (of size n, with k true). bitset shows valid item from the vector.

    – Jarod42
    9 hours ago













  • @Jarod42 how do I use next_permutation on bitset? I can't find how to.

    – Pero
    8 hours ago














  • 1





    You might use next_permutation on a bitset (of size n, with k true). bitset shows valid item from the vector.

    – Jarod42
    9 hours ago













  • @Jarod42 how do I use next_permutation on bitset? I can't find how to.

    – Pero
    8 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
9 hours ago







You might use next_permutation on a bitset (of size n, with k true). bitset shows valid item from the vector.

– Jarod42
9 hours ago















@Jarod42 how do I use next_permutation on bitset? I can't find how to.

– Pero
8 hours ago





@Jarod42 how do I use next_permutation on bitset? I can't find how to.

– Pero
8 hours ago












4 Answers
4






active

oldest

votes


















4














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






share|improve this answer































    3














    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);
    }
    }






    share|improve this answer
























    • I am aware of this, but this prints combinations, rather than variations, which is not what I need.

      – Pero
      8 hours ago











    • no need to use popcnt, you can use normal slower way of counting en.wikichip.org/wiki/population_count

      – NoSenseEtAl
      8 hours ago











    • @Pero when you have the combinations, you can use next permutation on these (which are much smaller)

      – Unlikus
      8 hours ago



















    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.






    share|improve this answer

































      1














      //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! ]






      share|improve this answer

























        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
        });


        }
        });














        draft saved

        draft discarded


















        StackExchange.ready(
        function () {
        StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54970636%2fc-how-can-i-make-an-algorithm-for-finding-variations-of-a-set-without-repetiti%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









        4














        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






        share|improve this answer




























          4














          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






          share|improve this answer


























            4












            4








            4







            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






            share|improve this answer













            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







            share|improve this answer












            share|improve this answer



            share|improve this answer










            answered 8 hours ago









            MBoMBo

            49k23050




            49k23050

























                3














                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);
                }
                }






                share|improve this answer
























                • I am aware of this, but this prints combinations, rather than variations, which is not what I need.

                  – Pero
                  8 hours ago











                • no need to use popcnt, you can use normal slower way of counting en.wikichip.org/wiki/population_count

                  – NoSenseEtAl
                  8 hours ago











                • @Pero when you have the combinations, you can use next permutation on these (which are much smaller)

                  – Unlikus
                  8 hours ago
















                3














                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);
                }
                }






                share|improve this answer
























                • I am aware of this, but this prints combinations, rather than variations, which is not what I need.

                  – Pero
                  8 hours ago











                • no need to use popcnt, you can use normal slower way of counting en.wikichip.org/wiki/population_count

                  – NoSenseEtAl
                  8 hours ago











                • @Pero when you have the combinations, you can use next permutation on these (which are much smaller)

                  – Unlikus
                  8 hours ago














                3












                3








                3







                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);
                }
                }






                share|improve this answer













                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);
                }
                }







                share|improve this answer












                share|improve this answer



                share|improve this answer










                answered 8 hours ago









                UnlikusUnlikus

                776




                776













                • I am aware of this, but this prints combinations, rather than variations, which is not what I need.

                  – Pero
                  8 hours ago











                • no need to use popcnt, you can use normal slower way of counting en.wikichip.org/wiki/population_count

                  – NoSenseEtAl
                  8 hours ago











                • @Pero when you have the combinations, you can use next permutation on these (which are much smaller)

                  – Unlikus
                  8 hours ago



















                • I am aware of this, but this prints combinations, rather than variations, which is not what I need.

                  – Pero
                  8 hours ago











                • no need to use popcnt, you can use normal slower way of counting en.wikichip.org/wiki/population_count

                  – NoSenseEtAl
                  8 hours ago











                • @Pero when you have the combinations, you can use next permutation on these (which are much smaller)

                  – Unlikus
                  8 hours ago

















                I am aware of this, but this prints combinations, rather than variations, which is not what I need.

                – Pero
                8 hours ago





                I am aware of this, but this prints combinations, rather than variations, which is not what I need.

                – Pero
                8 hours ago













                no need to use popcnt, you can use normal slower way of counting en.wikichip.org/wiki/population_count

                – NoSenseEtAl
                8 hours ago





                no need to use popcnt, you can use normal slower way of counting en.wikichip.org/wiki/population_count

                – NoSenseEtAl
                8 hours ago













                @Pero when you have the combinations, you can use next permutation on these (which are much smaller)

                – Unlikus
                8 hours ago





                @Pero when you have the combinations, you can use next permutation on these (which are much smaller)

                – Unlikus
                8 hours ago











                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.






                share|improve this answer






























                  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.






                  share|improve this answer




























                    2












                    2








                    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.






                    share|improve this answer















                    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.







                    share|improve this answer














                    share|improve this answer



                    share|improve this answer








                    edited 4 hours ago

























                    answered 4 hours ago









                    Michael VekslerMichael Veksler

                    3,4021517




                    3,4021517























                        1














                        //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! ]






                        share|improve this answer






























                          1














                          //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! ]






                          share|improve this answer




























                            1












                            1








                            1







                            //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! ]






                            share|improve this answer















                            //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! ]







                            share|improve this answer














                            share|improve this answer



                            share|improve this answer








                            edited 5 hours ago

























                            answered 5 hours ago









                            brightprogrammerbrightprogrammer

                            308




                            308






























                                draft saved

                                draft discarded




















































                                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.




                                draft saved


                                draft discarded














                                StackExchange.ready(
                                function () {
                                StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54970636%2fc-how-can-i-make-an-algorithm-for-finding-variations-of-a-set-without-repetiti%23new-answer', 'question_page');
                                }
                                );

                                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







                                Popular posts from this blog

                                How to label and detect the document text images

                                Vallis Paradisi

                                Tabula Rosettana