Random sequence with no duplicates

[sao123]

i need suggestions for the most efficient way to do this in C++

I need to generate the numbers 1 to 8 in a random sequence with no duplicates.

currently I am stuck doing int X = (rand() %8) + 1 in a loop but then I am going to have to check one by one for duplicates, which is a royal pain in the ass.


Is there a math forumla which will randomly generate numbers sich as 12345678, 28745613, 86574231, etc? I can mod them by 10.

I do not want to make an array of all 40320 possibilities and randomly choosing from that either.


Maybe I could start with 1 2 3 4 5 6 7 8 and having a random scrambling algorithm?


This is as close as I could come...

#include<iostream>
#include<ctime>
#include<cstdlib>

using namespace std;

int A[8] = {1,2,3,4,5,6,7,8};

void main()
{
srand((unsigned)time(0));

for(int i=0; i<8; i++)
{
int X = rand() % (8-i);
swap(A[X], A[7-i]);
}

for(int j=0; j<8; j++)
{
cout << A[j] << " ";
}

}

void swap(int& x, int& y)
{
int temp = x;
x = y;
y = temp;
}

 

[nickbits]

Yes start with 1-8 in an array and shuffle them around X amount of times until they a sufficently random.

 

[mundane]

Why don't you have a vector of candidates (1-8), and iterate through eight times (the eighth is a gimme, as it would be of length 1 at that time). For each iteration, randomly index one, remove it, and append to the return value. This approach avoids the duplicate/collision checks you would otherwise have to run (either inserting 1-8 into random positions, or filling eight positions with random values).

 

[esun]

http://en.wikipedia.org/wiki/Knuth_shuffle

 

[Rangoric]

NM, other suggestions work better.

 

[sao123]

Originally posted by: esun
http://en.wikipedia.org/wiki/Knuth_shuffle

thx, looks like I inadvertantly stumbled upon Durstenfeld's version of this without even realizing it.