Java: How to randomly go through an array?

Question

I have an array of size x and I need to go through the list randomly but getting to each element once. What is the most efficient way to do this?

possible duplicate of [Take n random elements from a List?](http://stackoverflow.com/questions/4702036/take-n-random-elements-from-a-liste) — templatetypedef, Sep 14 '11 at 02:38
`but getting to each element once` -- Does this mean you want to get each element only once ? and not get that element again after shuffling ? — Rakesh, Sep 14 '11 at 05:58

score 7 · Accepted Answer · answered Sep 14 '11 at 02:37

What you are looking for is shuffle

try this-

// Create a list
List list = new ArrayList();

// Add elements to list

// Shuffle the elements in the list
Collections.shuffle(list);

// Create an array
String[] array = new String[]{"a", "b", "c"};

// Shuffle the elements in the array
Collections.shuffle(Arrays.asList(array));

score 4 · Answer 2 · answered Sep 14 '11 at 02:37

4

Just shuffle the array and then iterate over it.

Collections.shuffle(Arrays.asList(yourArrayReference));

answered Sep 14 '11 at 02:37

Mahesh

34,573
20
89
115

Collections is not defined. What is collections? – Ben Racicot Jul 20 '16 at 13:37
1

[Java collections](https://docs.oracle.com/javase/tutorial/collections/). Specifically look at Algorithms section. – Mahesh Jul 21 '16 at 15:11

score 2 · Answer 3 · answered Mar 20 '15 at 02:28

Here is a time and space efficient way to do it.

import java.util.Enumeration;
import java.util.Random;

public class RandomPermuteIterator implements Enumeration<Long> {
    int c = 1013904223, a = 1664525;
    long seed, N, m, next;
    boolean hasNext = true;

    public RandomPermuteIterator(long N) throws Exception {
        if (N <= 0 || N > Math.pow(2, 62)) throw new Exception("Unsupported size: " + N);
        this.N = N;
        m = (long) Math.pow(2, Math.ceil(Math.log(N) / Math.log(2)));
        next = seed = new Random().nextInt((int) Math.min(N, Integer.MAX_VALUE));
    }

    public static void main(String[] args) throws Exception {
        RandomPermuteIterator r = new RandomPermuteIterator(100);
        while (r.hasMoreElements()) System.out.print(r.nextElement() + " ");
    }

    @Override
    public boolean hasMoreElements() {
        return hasNext;
    }

    @Override
    public Long nextElement() {
        next = (a * next + c) % m;
        while (next >= N) next = (a * next + c) % m;
        if (next == seed) hasNext = false;
        return  next;
    }
}

That's very unreadable and though scary code. After 5 minutes I still don't see what is does. But if it really traverses through an array (like the OP asked), then the array must be very well hidden. Also this question was already answered 4 years ago. — Jan Groth, Mar 20 '15 at 02:37
It pseudo-randomly enumerates the indices of an array. If you run the above code for instance you will get something like 50 52 3 6 45 40 26 49 92 11 80 2 4 19 86 61 65 44 27 62 5 32 82 9 84 35 38 77 72 7 ... for an array with indices 0..99. — aykutfirat, Mar 20 '15 at 02:49
It is a [linear congruential generator](https://en.wikipedia.org/wiki/Linear_congruential_generator) much like the one used by Java itself. The modulo being sized based on the number of elements in the list means that at most half of the possible values are out of range. — Matthew Franglen, Feb 25 '19 at 20:26

score 0 · Answer 4 · answered Sep 14 '11 at 02:39

You could use a random number generator, which is typically available by default in most object-oriented languages, and use a second array to keep track of what you checked already.

Essentially:

Generate a random number
Search main array for random number
If random number is not in already-checked array...
...then check the element at main array[random]
Add random number to the end of already-checked array

Java: How to randomly go through an array?

4 Answers4