How to generate an array of 256 distinct numbers

Question

I have this:

#include <iostream>    
using namespace std;   
int main()
{
    int a[256];
    int b;
    int k;
    for (int i = 0; i < 256; i ++){
    b = rand()%256;
    k = 0;
        for (int j = 0; j< i; j ++)
        {
            if (a[j] == b){k = 1;}  
        }
    if (k == 0){a[i] = b;}
    if (k==1){i--;}
    }

    return 0;
}

This generates an array of integers from 0 to 255. Each integer only occur once in the array. My problem is that this code takes quite a while to execute because for each new random integer I check whether or not the integer is already in the array. So I have to wait until all the integers from 0 to 255 have showed up as a random number. My question is:

Is there is a better way to do this?

Use a *shuffle*, like you shuffle a deck of cards. Google "fisher yates". — Hans Passant, Feb 22 '14 at 00:51
by the way, why do you need this ? you want to check how much time the random number generator will spend to produce 256 distinct numbers ? — mangusta, Feb 22 '14 at 00:59
@mangusta: I need a random permutation for some cryptography. — Thomas, Feb 22 '14 at 01:00
@HansPassant: Thank you for this. This seems to be what I need. Would you write an answer making it a bit more clear than the Wikipedia article? — Thomas, Feb 22 '14 at 01:00
possible duplicate of [Is this C implementation of Fisher-Yates shuffle correct?](http://stackoverflow.com/questions/3343797/is-this-c-implementation-of-fisher-yates-shuffle-correct) — Hans Passant, Feb 22 '14 at 01:07
@HansPassant: I think I got the Fisher-Yates stuff to work. If you add an answer basically containing your comment from above, I will accept it. — Thomas, Feb 22 '14 at 01:30

score 6 · Answer 1 · answered Feb 22 '14 at 01:01

6

As others mentioned, use std::random_shuffle:

std::vector<int> my_vec(256); //Reserve space for 256 numbers in advance.

for(int n = 0; n < 256; ++n)
{
  my_vec.push_back(n);
}

std::random_shuffle(my_vec.begin(), my_vec.end());

answered Feb 22 '14 at 01:01

Mateusz Grzejek

11,698
3
32
49

`random_shuffle` doesn't create objects, but just moves them around. The code above creates a vector with the 256 distinct numbers in order. `random_shuffle` randomizes their positions. – Gort the Robot Feb 22 '14 at 01:06
In for() loop you insert values from 0 to 255 in that order. So after loop execution, you have vector with unique integer values from range [0;255]. std::random_shuffle does not change container's content - it only changes order of its elements (shuffles them). – Mateusz Grzejek Feb 22 '14 at 01:08

score 1 · Accepted Answer · answered Feb 22 '14 at 01:38

std::random_shuffle is the way to go, as previously mentioned, but just in case you don't want to use it (maybe using ANSI C instead of C++), here's a quick-and-dirty implementation:

#include <stdlib.h>
#include <time.h>

#define SIZE 256

static inline void
swap(int *a, int *b) {
    // Don't swap them if they happen to be the same element 
    // in the array, otherwise it'd be zeroed out
    if (a != b) {
        *a ^= *b;
        *b ^= *a;
        *a ^= *b;
    }
}

int main(void)
{
    int A[SIZE], i;
    // Initialize array with sequential incrementing numbers
    for (i = 0; i < SIZE; ++i)
        A[i] = i;

    // Initialize random seed
    srand(time(NULL));

    // Swap every element of the array with another random element
    for (i = 0; i < SIZE; ++i)
        swap(&A[i], &A[rand() % SIZE]);

    return 0;
}

score 1 · Answer 3 · answered Feb 22 '14 at 03:38

You could try something like this:

int main()
{
    std::vector<int> available(256);
    int a[256];

    for (int i = 0; i < 256; ++i)
        available.push_back(i);

    for (int i = 0; i < 256; ++i)
    {
        int idx = rand() % available.size();
        a[i] = available[idx];
        available.erase(available.begin()+idx);
    }

    // use a[] as needed...

    return 0;
}

score 1 · Answer 4 · answered Feb 22 '14 at 05:32

#include <iostream>
#include <vector>
#include <algorithm>

int main(int argc, const char * argv[])
{
    std::vector<int> items(256);

    std::iota(items.begin(),items.end(),0);

    std::random_shuffle(items.begin(), items.end());

    for(auto i:items)
        std::cout<<i<<"  ";
}

How to generate an array of 256 distinct numbers

4 Answers4

Linked