About a non-repeat rand function

Question

I tried to generate 25 arrays, each of them should contains number 1 to 25 without repetition and out of order. I executed the code to generate an array, there was no repetition. There were repeating numbers in the array when I tried to map the array into the 2D array.

Here is my code

int permutation(int arraystore[]){

int item[25], index;
for (int x = 0; x < 25; x++)
    item[x] = x;                  //input values into item array

for (int x = 25; x > 0; x--) {
    index = rand() % x;     //generate random numbers
    arraystore[x] = item[index];
    while (index < x - 1) {             
        item[index] = item[index + 1];
        index++;
        }
    }
}

I map the arraystore into the 2d array in main

int main(){
int ddarray[25][25];
for(int j=0;j<25)
    for(int i=0;i<25;i++){
        int array[25];
        permutation(array);
        ddarray[j][i]=array[i];
    }
}

Here are some of results

192,9,7,3,11,20,18,9,23,11,21,5,11,17,5,12,11,3,10,9,2,5,7,7,19, 192,5,0,14,23,22,6,2,20,24,13,12,21,24,21,6,11,21,1,20,5,8,6,12,15, 192,21,6,14,14,11,11,8,17,19,9,24,22,6,24,11,2,22,6,13,2,18,6,14,20,

Did I do any wrong in the permutation function or miss something?

Thank you for answering my question!

Since `arraystore` is a 25 element array, `arraystore[x]` is out of bounds when `x` is 25 and you never visit `arraystore[0]`. You probably meant `arraystore[x - 1]`. — François Andrieux, Mar 04 '19 at 16:10
You may be interested in [`std::shuffle`](https://en.cppreference.com/w/cpp/algorithm/random_shuffle). — François Andrieux, Mar 04 '19 at 16:11
Possible duplicate of [Generating random non repeating number array in C++](https://stackoverflow.com/questions/25878202/generating-random-non-repeating-number-array-in-c) — phuclv, Mar 04 '19 at 16:19
[Non-repeating random number generator](https://stackoverflow.com/q/5382037/995714), [Random array generation with no duplicates](https://stackoverflow.com/q/20734774/995714) — phuclv, Mar 04 '19 at 16:20

Max Langhof · Answer 1 · 2019-03-04T16:23:56.403

There are several things that could/must be improved here.

First off, I would recommend using std::shuffle instead of rolling your own version.
The main issue that makes your program illegal C++: If x is 25, then you try to write to arraystore[x], which is past the end of a 25 element array. You probably want to write to arraystore[x-1].
The main issue that gives you repeating output: You are randomizing a new array for every i in the inner loop and then only use the ith element (so you generate 25*25 arrays with 25 elements each). It can happen (in fact, it is exceedingly likely) that you repeat some elements this way. The correct main would look like this:
```
int main() {
    int ddarray[25][25];
    for (int j=0; j<25; ++j)
    {
        int array[25];
        permutation(array);
        for (int i=0; i<25; i++) {
            ddarray[j][i] = array[i];
        }
    }
}
```
(Note that a ++j was missing in your original code too...)
Your implementation of permutation is pretty inefficient, because it has to move lots of elements for every single output element. The standard Fischer Yates shuffle just swaps the elements at the current output and randomly chosen index.
Finally, I would suggest using std::array (or std::vector) instead of plain arrays. The latter are very inconvenient/surprising to work with (and have no standard-support for different sizes at runtime).

score 2 · Answer 2 · answered Mar 04 '19 at 16:19

A simple implementation in C++11 based on std::shuffle could look like this:

int main() {
   std::random_device rd;
   std::mt19937 g(rd());

   std::array<std::array<int, 25>, 25> ddarray;

   for (auto& a : ddarray) {
      std::iota(a.begin(), a.end(), 1);
      std::shuffle(a.begin(), a.end(), g);
   }    
}

Live demo: https://wandbox.org/permlink/0abgD0Yqv9K1B1D9.

About a non-repeat rand function

2 Answers2