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



  • 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"}
    


  • I'd give a look at next_permutation.



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



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



  • @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");
    }
    


  • @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.



  • 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?



  • 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.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".



  • @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!


Log in to reply
 

Looks like your connection to Qt Forum was lost, please wait while we try to reconnect.