random number that doesn't repeat?

Hi golanshahar, your code totally nailed it: killed 2 birds with one stone without the need for random_shuffle(), etc...how do you do it? I reposted the code, but can't really figure out how it works....please explain what happens at the 2 statements below:

Code:

---

                arr[lastItem] = arr[arrIndex];
                arr[arrIndex] = tmp;

---

Also am I on the right track with understanding the rest of the program?

Thanks a lot.

Code:

---

int main()
{
        //Initialize the array to be sampled: 1-20
        int arr[20]={0};

    for(int i=0; i<20; i++)
                arr[i]=i+1;

        //Provide seed of system time to the random # generator.
        srand((unsigned)time(0));

        int lastItem = 20;

        //For each instance of the random number generator.....
        for(int index=0; index<20; index++)
        {
                //name the random number generated.
                int arrIndex = rand()%lastItem;
                //Reduce the number of items from which sampling is to be done, by 1
                lastItem--;

                //call the new last item: 19, tmp.
                int tmp = arr[lastItem];

                //je n'est pas comprendre!
                arr[lastItem] = arr[arrIndex];
                arr[arrIndex] = tmp;

                //traverse the array and write out each value to the screen
                for(int index=0; index<20; index++)
                    cout << arr[index] << endl;
        }

        return 0;
}

---

Quote:

---

Originally Posted by aaadetos

Hi golanshahar, your code totally nailed it: killed 2 birds with one stone without the need for random_shuffle(), etc...

---

Glad i could help :wave:

Quote:

---

Originally Posted by aaadetos

how do you do it? I reposted the code, but can't really figure out how it works....please explain what happens at the 2 statements below:

Code:

---

                arr[lastItem] = arr[arrIndex];
                arr[arrIndex] = tmp;

---

---

well the basic idea is to rand the indexs of the array instead of the data item themselves.
lets look at simple sample
say we have this array:
[1,2,3,4,5]
and we want to shuffle ( or rand() ) the items so each time we will get different permotaion of the 1...5 numbers.

now if you will shuffle the data itself ( what you tried doing in your first post ) of course you can rand() the number lets say 4 more then once! and this is not what we want.

so better idea is to rand() the indexs and each rand() iteration we reduce the rand() limit. meaning:
first time we getting a number from rand between 0-4 (n-1)
lets say 3

the item in the 3rd index is 4 so what we are doing is swapping between the last item and the item we got from rand so our array will look like this:
[1,2,3,5,4]
now we reducing the rand() to rand()%n-1 so we will rand number bewteen 0-3
lets say we rand 1
so again we will swap the item we rand with the pointer to the n-1 so array will look like this:
[1,5,3,2,4]
and so on.....

in that way of action we will always have shuffled array without repeats of the same item.

this is VERY basic trick it is used in games ( like shuffling cards etc ), and images displaying ( When you want to fade in an image but in a way each time you will display different pixel so the result will be like million of pieces of the image building it step by step ( power point for instace have this effect ;) )

anyway glad i could help and hope the idea is more clear now :D

Cheers