Skip to content
  • Categories
  • Recent
  • Tags
  • Popular
  • Users
  • Groups
  • Search
  • Get Qt Extensions
  • Unsolved
Collapse
Brand Logo
  1. Home
  2. Special Interest Groups
  3. C++ Gurus
  4. How to Shuffle elements of an Array without repeating the same sequence?
Forum Updated to NodeBB v4.3 + New Features

How to Shuffle elements of an Array without repeating the same sequence?

Scheduled Pinned Locked Moved Unsolved C++ Gurus
10 Posts 3 Posters 5.0k Views 3 Watching
  • Oldest to Newest
  • Newest to Oldest
  • Most Votes
Reply
  • Reply as topic
Log in to reply
This topic has been deleted. Only users with topic management privileges can see it.
  • E Offline
    E Offline
    Eduardo12l
    wrote on 25 Jul 2017, 05:06 last edited by Eduardo12l
    #1

    For example if i have the following array:

    int vector[] = {"a", "b", "c"};
    

    i want to get 3 different sequences without repeats. For example i dont want to get

    {"b", "c", "a"} //duplicated
    {"b", "c", "a"} //duplicated
    {"a", "b", "c"}
    
    1 Reply Last reply
    0
    • J Offline
      J Offline
      JohanSolo
      wrote on 25 Jul 2017, 05:50 last edited by
      #2

      I'd give a look at next_permutation.

      `They did not know it was impossible, so they did it.'
      -- Mark Twain

      E 1 Reply Last reply 25 Jul 2017, 16:05
      1
      • J JohanSolo
        25 Jul 2017, 05:50

        I'd give a look at next_permutation.

        E Offline
        E Offline
        Eduardo12l
        wrote on 25 Jul 2017, 16:05 last edited by
        #3

        @JohanSolo But it will give me a no-distribuited result

        J 1 Reply Last reply 25 Jul 2017, 16:34
        0
        • E Eduardo12l
          25 Jul 2017, 16:05

          @JohanSolo But it will give me a no-distribuited result

          J Offline
          J Offline
          JohanSolo
          wrote on 25 Jul 2017, 16:34 last edited by
          #4

          @Eduardo12l I'm not sure to understand what you mean....

          `They did not know it was impossible, so they did it.'
          -- Mark Twain

          E 1 Reply Last reply 25 Jul 2017, 20:35
          0
          • J JohanSolo
            25 Jul 2017, 16:34

            @Eduardo12l I'm not sure to understand what you mean....

            E Offline
            E Offline
            Eduardo12l
            wrote on 25 Jul 2017, 20:35 last edited by
            #5

            @JohanSolo If you run this algorithm you could notice what is the problem of next_permutation

            #include <iostream>
            #include <algorithm>
            #include <string>
            #include <cstdlib>
            using namespace std;
            
            int main() {
            	string vector[] = {"a", "b", "c", "d", "e", "f", "g", "h"};
            	for (int c = 0; c < 20; c++) {
            		std::next_permutation(begin(vector), end(vector));
            		for (int i = 0; i < 8; i++) {
            			cout << vector[i] << " ";
            		}
            		cout << endl;
            		cout << "" << endl;
            	}	
            	system("pause");
            }
            
            J 1 Reply Last reply 26 Jul 2017, 04:33
            0
            • E Eduardo12l
              25 Jul 2017, 20:35

              @JohanSolo If you run this algorithm you could notice what is the problem of next_permutation

              #include <iostream>
              #include <algorithm>
              #include <string>
              #include <cstdlib>
              using namespace std;
              
              int main() {
              	string vector[] = {"a", "b", "c", "d", "e", "f", "g", "h"};
              	for (int c = 0; c < 20; c++) {
              		std::next_permutation(begin(vector), end(vector));
              		for (int i = 0; i < 8; i++) {
              			cout << vector[i] << " ";
              		}
              		cout << endl;
              		cout << "" << endl;
              	}	
              	system("pause");
              }
              
              J Offline
              J Offline
              JohanSolo
              wrote on 26 Jul 2017, 04:33 last edited by JohanSolo
              #6

              @Eduardo12l I'm sorry but I don't. I know what a permutation looks like (moreover the page I gave you shows an example). I'll try once I have a compiler but I don't expect to be surprised.

              In your code the hardcoded 20 is clearly wrong: there are much more permutations for a set of 8 elements (8! is not 20), but that's a detail.

              Edit: in your first post you said you want the 3 permutations of a set with 3 elements. This is wrong again, there are 6 permutations. You should probably define better what you want so that you can be helped.

              `They did not know it was impossible, so they did it.'
              -- Mark Twain

              1 Reply Last reply
              0
              • J Offline
                J Offline
                JohanSolo
                wrote on 26 Jul 2017, 06:29 last edited by JohanSolo
                #7

                OK, now I'm at work and I have several compilers at hand. The result is pretty close to exactly what I expected:

                a b c d e f h g
                a b c d e g f h
                a b c d e g h f
                a b c d e h f g
                a b c d e h g f
                a b c d f e g h
                a b c d f e h g
                a b c d f g e h
                a b c d f g h e
                a b c d f h e g
                a b c d f h g e
                a b c d g e f h
                a b c d g e h f
                a b c d g f e h
                a b c d g f h e
                a b c d g h e f
                a b c d g h f e
                a b c d h e f g
                a b c d h e g f
                a b c d h f e g
                

                What output did you expect?

                `They did not know it was impossible, so they did it.'
                -- Mark Twain

                1 Reply Last reply
                0
                • J Offline
                  J Offline
                  J.Hilk
                  Moderators
                  wrote on 26 Jul 2017, 07:09 last edited by
                  #8

                  I had some time in my break..
                  I think the OP is looking for something like this?

                  #include <QCoreApplication>
                  #include <QVector>
                  #include <QDebug>
                  
                  QVector<QChar> vector {'a','b','c','d','e','f'};
                  
                  uint64_t factorial (uint64_t i){
                      uint64_t fac(1);
                      for(uint64_t j = 1; j <= i; j++)
                          fac = fac*i;
                      return fac;
                  }
                  
                  QList<QVector<QChar>> getAllPermutations(){
                      QList<QVector<QChar>> list;
                  
                      uint64_t max = factorial(vector.size());
                      for(uint64_t i = 0; i< max; i++){
                          std::next_permutation(vector.begin(), vector.end());
                          list.append(vector);
                      }
                      return list;
                  }
                  
                  QList<QVector<QChar>> selectSome(int cnt, QList<QVector<QChar>> pool){
                      QList<QVector<QChar>> list;
                      for(int i = 0; i < cnt; i++){
                          int index = rand()%pool.size();
                          list.append(pool.at(index));
                      }
                      return list;
                  }
                  
                  int main(int argc, char *argv[])
                  {
                      QCoreApplication a(argc, argv);
                  
                      QList<QVector<QChar>> pool = getAllPermutations();
                      QList<QVector<QChar>> selection = selectSome(3,pool);
                  
                      for(auto item : selection)
                          qDebug() << item;
                  
                      return a.exec();
                  }
                  

                  Be aware of the Qt Code of Conduct, when posting : https://forum.qt.io/topic/113070/qt-code-of-conduct


                  Q: What's that?
                  A: It's blue light.
                  Q: What does it do?
                  A: It turns blue.

                  J 1 Reply Last reply 26 Jul 2017, 09:08
                  0
                  • J J.Hilk
                    26 Jul 2017, 07:09

                    I had some time in my break..
                    I think the OP is looking for something like this?

                    #include <QCoreApplication>
                    #include <QVector>
                    #include <QDebug>
                    
                    QVector<QChar> vector {'a','b','c','d','e','f'};
                    
                    uint64_t factorial (uint64_t i){
                        uint64_t fac(1);
                        for(uint64_t j = 1; j <= i; j++)
                            fac = fac*i;
                        return fac;
                    }
                    
                    QList<QVector<QChar>> getAllPermutations(){
                        QList<QVector<QChar>> list;
                    
                        uint64_t max = factorial(vector.size());
                        for(uint64_t i = 0; i< max; i++){
                            std::next_permutation(vector.begin(), vector.end());
                            list.append(vector);
                        }
                        return list;
                    }
                    
                    QList<QVector<QChar>> selectSome(int cnt, QList<QVector<QChar>> pool){
                        QList<QVector<QChar>> list;
                        for(int i = 0; i < cnt; i++){
                            int index = rand()%pool.size();
                            list.append(pool.at(index));
                        }
                        return list;
                    }
                    
                    int main(int argc, char *argv[])
                    {
                        QCoreApplication a(argc, argv);
                    
                        QList<QVector<QChar>> pool = getAllPermutations();
                        QList<QVector<QChar>> selection = selectSome(3,pool);
                    
                        for(auto item : selection)
                            qDebug() << item;
                    
                        return a.exec();
                    }
                    
                    J Offline
                    J Offline
                    JohanSolo
                    wrote on 26 Jul 2017, 09:08 last edited by
                    #9

                    @J.Hilk said in How to Shuffle elements of an Array without repeating the same sequence?:

                    I had some time in my break..
                    I think the OP is looking for something like this?

                    Makes sense, all we were missing was the actual requirement "I want some permutations without repetitions".

                    `They did not know it was impossible, so they did it.'
                    -- Mark Twain

                    J 1 Reply Last reply 26 Jul 2017, 09:33
                    0
                    • J JohanSolo
                      26 Jul 2017, 09:08

                      @J.Hilk said in How to Shuffle elements of an Array without repeating the same sequence?:

                      I had some time in my break..
                      I think the OP is looking for something like this?

                      Makes sense, all we were missing was the actual requirement "I want some permutations without repetitions".

                      J Offline
                      J Offline
                      J.Hilk
                      Moderators
                      wrote on 26 Jul 2017, 09:33 last edited by
                      #10

                      @JohanSolo Actually, now that you say it,
                      theres a chance for repetitions in selectSome

                      QList<QVector<QChar>> selectSome(int cnt, QList<QVector<QChar>> pool){
                          QList<QVector<QChar>> list;
                          QVector<int> usedIndex;
                          int i(0);
                          while(i < cnt && usedIndex.size() < pool.size(){
                              int index = rand()%pool.size();
                              if(!usedIndex.contains(index)){
                                  usedIndex.append(index);
                                  list.append(pool.at(index));
                              }
                         }
                          return list;
                      }
                      

                      this should be better, still not perfect, but at least no repetitions, possible infinite loop when pool.size() > sizeOf(int)? Gets very slow for big cnt!


                      Be aware of the Qt Code of Conduct, when posting : https://forum.qt.io/topic/113070/qt-code-of-conduct


                      Q: What's that?
                      A: It's blue light.
                      Q: What does it do?
                      A: It turns blue.

                      1 Reply Last reply
                      0

                      3/10

                      25 Jul 2017, 16:05

                      7 unread
                      • Login

                      • Login or register to search.
                      3 out of 10
                      • First post
                        3/10
                        Last post
                      0
                      • Categories
                      • Recent
                      • Tags
                      • Popular
                      • Users
                      • Groups
                      • Search
                      • Get Qt Extensions
                      • Unsolved