Arrays & While Loop in Java

Question

Given an array --> int[ ] nums = {0,1,2,3,4,5,6,7,8,9};

How can we loop (using a while) so that each element in the array is chosen randomly at least once? So the loop must keep going until every element is selected once.

I cannot figure out how to even start this on my own, so help would be appreciated!

Record the selected indexes, e.g. in a `BitSet`; check how many bits are set, and stop once there are no unset ones. — Andy Turner, Mar 10 '17 at 21:53
you could store the visited indexes into another array, then each time check if each index of the nums array has been added to the visited array. but this has a slow Runtime performance. However, considering you're using small amount of values, it would be okay. — Ousmane D., Mar 10 '17 at 21:54

score 1 · Answer 1 · answered Mar 10 '17 at 22:00

Assuming you can rearrange the array, you can do something like this:

int numNotPicked = nums.length;
Random r = new Random();
while (numNotPicked > 0) {
  int index = r.nextInt(nums.length);
  System.out.println(nums[index]);

  if (index < numNotPicked) {
    int tmp = nums[numNotPicked-1];
    nums[numNotPicked-1] = nums[index];
    nums[index] = tmp;
    numNotPicked--;
  }
}

Ideone demo

This partitions the array into two parts:

Numbers you've not picked before, with indexes 0 (inclusive) to numNotPicked (exclusive)
Numbers you have picked before, with indexes numNotPicked (inclusive) to nums.length (exclusive)

Then, this picks a random element in the array: if you pick a number in the "not picked before" range, it swaps it with the last element in the "not picked before" part, and decreases numNotPicked by 1.

score 1 · Answer 2 · answered Mar 10 '17 at 22:09

Like Andy said, you could use a BitSet which is a fast/efficient way to do this without changing the original array.

import java.util.BitSet;
import java.util.concurrent.ThreadLocalRandom;

public class JavaTest {
    public static void main(String[] args) {
        int[] numbers = {0,1,2,3,4,5,6,7,8,9};

        // create a BitSet with # of bits == number of indices in numbers
        BitSet set = new BitSet(numbers.length);

        // while not all bits are set in the bitset, do this loop
        while (set.cardinality() < numbers.length) {

        // choose a random number within the [0,N]
        int randomNum = ThreadLocalRandom.current().nextInt(0, numbers.length);

            // set the corrsponding bit in the bitset
            set.set(randomNum);

            // report the number and progress
            System.out.println("New number chosen: "+randomNum+", total indices chosen: "+
                set.cardinality()+" of "+numbers.length);
        }
    }
}

Arrays & While Loop in Java

2 Answers2