1

my goal is to randomly shuffle an array, (from 0 to 9) but every number has to appear in the array only once. I have got two (working) ideas, but I would like to find out how many times must this random2 method iterate to achieve the same level of randomness in array as in the first method (random1).

import java.util.Random;

class RandomStuff {

static Random r;
final static int iteraction = 10;

public static void main (String[] args) {
    r = new Random();
    int[] array = new int[10];
    random1(array);
    random2(array, iteraction);
}

static void random1(int[] array) {
    for(int i = 0; i < array.length; i++) pole[i] = -1;

    for(int i = 0; i < array.length; i++) {
        while(true) {
            int y = r.nextInt(10);
            if(!find(array, y)) {
                array[i] = y;
                break;
            }
        }
    }
}

static void random2(int[] array, int iteraction) {
    for(int i = 0; i <= iteraction; i++) {
        int y1 = r.nextInt(array.length);
        int y2 = r.nextInt(array.length);
        int p = array[y1];
        array[y1] = array[y2];
        array[y2] = p;
    }
}

static boolean find(int[] array , int value) {
    for(int i = 0; i < array.length; i++) {
        if(pole[i] == value) return true;
    }
    return false;
}
}

The first method (random1) works assigning of random numbers and testing, if they are/aren't in the array already. Which seems to be pretty random to me.

The second method (random2) works on swaping two random random values in the array. So the question is, how many times do I have to swap two numbers in the array to achieve the same level of randomness. (or what value shoud the variable iteraction have).

Thanks for any reply.

Vilda
  • 1,675
  • 1
  • 20
  • 50
  • 4
    Perhaps you should just use the [Fisher-Yates shuffle](http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle). – Kevin Apr 01 '14 at 13:27
  • I don't understand the purpose of your "doubly randomness"-ness. If the first method assigns a random number to each element, then what additional benefit are you getting by then shuffling them in the second function? – aliteralmind Apr 01 '14 at 13:30
  • 1
    You could simple assign the numbers from 0 to 9 in your array and then shuffle it, I guess. – Karura91 Apr 01 '14 at 13:32
  • 2
    Possible duplicate: http://stackoverflow.com/questions/1519736/random-shuffling-of-an-array – Alexander_Winter Apr 01 '14 at 13:34
  • I don't want to use any special methods except mine. – Vilda Apr 01 '14 at 13:36
  • Both of them works, I just want to know how many times do I have to shuffle numbers in the second random method. – Vilda Apr 01 '14 at 13:37

2 Answers2

2

How about assigning a random number to each element of the array, arrange the random numbers in order and in that order read the element of the array assigned to that random number

0.64342 0
0.95229 1
0.23047 2
0.82793 3
0.19014 4
0.18528 5
0.15684 6
0.99546 7
0.54524 8
0.90612 9

Order

0.15684 6
0.18528 5
0.19014 4
0.23047 2
0.54524 8
0.64342 0
0.82793 3
0.90612 9
0.95229 1
0.99546 7

numbers 0 to 9 now in random order

jing3142
  • 1,821
  • 1
  • 11
  • 16
1

To answer your original question, "how many times must this random2 method iterate to achieve the same level of randomness in array as in the first method?"

The answer is: it will never achieve the same level of randomness.

For any position that has been swapped, there is an equal chance of it arriving in any position, which means a 10% chance it ends up back where it started.

In each iteration, 2 numbers are swapped (or zero if the number is swapped to its own position). That means there's an 80% chance for any given position to never have been swapped, after 1 iteration. After N iterations, there is still a 0.8^N chance that it was never swapped. If it was swapped, there is a 10% chance it went back where it started. So the probability that any given digit is in its starting position is 10% + 0.8^N. This is always > 10%, so you will never get a perfectly even distribution.

For example, for your choice of 10 iterations, there remains a 10.7% chance for each digit that it never moved, or a total of 19.7% chance it'll be in its starting position. So ten iterations is not even close to enough.

user3294068
  • 340
  • 2
  • 6