Pick non-repeating random number from progressive list

Question

Here is my example - pick random number from 1-20, then from 2-21, 3-22 and so on, while excluding previous picks. I am new to Java, and doing something wrong.

import java.util.Random;
import java.util.ArrayList;
import java.util.List;

public class RandomGenerator {

      static int temp;
    public static void main(String[] args) {

        List<Integer> randomNumberArray = new ArrayList<Integer>(); 

        Random RandomNumber = new Random();

    for (int i = 0; i<=20; i++)
    {
        temp = RandomNumber.nextInt(i+20) +1+i;
        if (!randomNumberArray.contains(temp))
        {
            {
                randomNumberArray.add(temp);
            }

        }

        System.out.println(randomNumberArray);
    }

How does it actually behave, and how is that different from what you expect? — GreyBeardedGeek, Jun 10 '14 at 15:09

score 0 · Answer 1 · answered Jun 10 '14 at 15:16

You aren't excluding previous picks. Something like this will print twenty random numbers (e.g. all random numbers from 1-20).

public static void main(String[] args) {
  java.util.Set<Integer> picked = new TreeSet<Integer>();
  Random rand = new Random();
  while (picked.size() < 20) {
    int temp = 1+rand.nextInt(20);
    if (picked.contains(temp)) {
      continue;
    }
    picked.add(temp);
    System.out.println(temp);
  }
}

I'm not sure I understand your "stepping" idea, but add this for temp and it will do that too -

int temp = 1+picked.size()+rand.nextInt(20+picked.size());

Ceiling Gecko · Accepted Answer · 2014-06-11T22:18:19.780

There are a couple of things to go over.

1) If your number sees that there is a duplicate then it will skip it and continue with the next number, for example if you run it 5 times and it finds a duplicate once, then the resulting list of numbers will have only 4 numbers not 5! since it skipped one. (Not sure if this is what you wanted or not)

2) Your randomly generated number doesn't grow the way you expect it to grow. For example: At the sixth iteration over the loop your random number will generate as:

RandomNumber.nextInt(25) +6;

That means that the number range there isn't 6-26 but 6-30!

Because: nextInt will return an int between 0 and 24 and then that int is added another 6 to it.

EDIT :

To tackle your first problem you can continue to generate numbers until you generate one that is not a duplicate for that single cycle of the for loop.

For this you can utilize the do-while loop so that it executes the number generation at least once before checking whether the number is a duplicate within the for loop.

So you can adjust your for loop from:

for (int i = 0; i<=20; i++)
{
    temp = RandomNumber.nextInt(20) +1+i;
    if (!randomNumberArray.contains(temp))
    {
        {
            randomNumberArray.add(temp);
        }

    }

    System.out.println(randomNumberArray);
}

into:

for (int i = 0; i<=20; i++)
{
    do {
        temp = RandomNumber.nextInt(20) +1+i;
    } while (randomNumberArray.contains(temp));

    randomNumberArray.add(temp);

    System.out.println(randomNumberArray);
}

Notice that the check in the while expression is the opposite (does not have the exclamation mark) of what was in the if expression in the for loop before, since we do want to continue generating new random numbers while our numbers are duplicates.

And since we are still looping within that one cycle of the for loop, it will always generate the number with the appropriate value of i which was set for that for cycle.

You are correct, making the change to nextInt(20), I get a much better result. I am still stuck, however, on how to try for a new random number (if there is a repeat) before advancing i. Thanks for your help. — jsaff1902, Jun 11 '14 at 17:27
@user184662 you can use a **do-while** loop inside the **for** loop, see the edits I made to my post for details regarding this. — Ceiling Gecko, Jun 11 '14 at 22:20

OldCurmudgeon · Answer 3 · 2014-06-10T15:59:41.037

The trick here is to use Collections.shuffle(List list):

    List<Integer> list = Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20);
    Collections.shuffle(list);
    System.out.println(list);

The progressive version goes something like this:

    // Wrap it in an ArrayList so I can modify it.
    List<Integer> list = new ArrayList(Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20));
    for (int i = 21; i < 25; i++) {
        System.out.println(list);
        // Shuffle it.
        Collections.shuffle(list);
        // Grab one.
        Integer take = list.get(0);
        list.remove(take);
        System.out.println("Took " + take);
        // Add my new candidate.
        list.add(i);
    }

Or you could go the whole hog and make it an Iterable:

public static class CreepingRandom implements Iterable<Integer> {

    // The starting list.
    private final List<Integer> start;
    // How many steps to add.
    private final int steps;
    // What int to start adding.
    private final int from;

    public CreepingRandom(int initialSize, int from, int steps) {
        // Make my start list.
        start = new ArrayList<Integer>(initialSize);
        // Fill it.
        for (int i = 1; i <= initialSize; i++) {
            start.add(i);
        }
        // Remember where to start from.
        this.from = from;
        // Remember how many steps.
        this.steps = steps;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new CreepingIterator();
    }

    private class CreepingIterator implements Iterator<Integer> {

        // Track how many I've delivered.
        int delivered = 0;
        // The next number to add.
        int add = from;
        // My current list.
        final ArrayList<Integer> list = new ArrayList(start);

        @Override
        public boolean hasNext() {
            return delivered < steps;
        }

        @Override
        public Integer next() {
            // Shuffle it.
            Collections.shuffle(list);
            // Pull one out.
            Integer next = list.get(0);
            // Add my new one in.
            list.set(0, add++);
            // Count them.
            delivered += 1;
            return next;
        }

    }

}

public void test() {
    for (Integer i : new CreepingRandom(20, 21, 100)) {
        System.out.println(i);
    }
}

    private class CreepingIterator implements Iterator<Integer> {

        // Track how many I've delivered.
        int delivered = 0;
        // The next number to add.
        int add = from;
        // My current list.
        final ArrayList<Integer> list;

        CreepingIterator() {
            // Copy the start list - Use LinkedList for efficiency of add and removeFirst.
            list = new ArrayList(start);
        }

        @Override
        public boolean hasNext() {
            return delivered < steps;
        }

        @Override
        public Integer next() {
            // Shuffle it.
            Collections.shuffle(list);
            // Pull one out.
            Integer next = list.get(0);
            // Add my new one in.
            list.set(0, add++);
            // Count them.
            delivered += 1;
            return next;
        }

    }

}

public void test() {
    for (Integer i : new CreepingRandom(20, 21, 100)) {
        System.out.println(i);
    }
}

I think this doesn't work as the OP expects, the probabilities are different. For example, 21 can't be at the first place in case of polling two elements. — Danstahr, Jun 10 '14 at 15:28
@Danstahr - printed `[16, 5, 18, 11, 12, 14, 6, 0, 2, 19, 8, 3, 13, 7, 15, 4, 20, 17, 9, 10, 1]` for me - is that not right? — OldCurmudgeon, Jun 10 '14 at 15:30

score 0 · Answer 4 · edited May 23 '17 at 12:20

Since the range of allowed elements isn't too big, you can also hold the pool of all possible numbers and pick one of them. You can use e.g. RandomSet from this answer.

import java.util.*;
import java.lang.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
    static class RandomSet<E> extends AbstractSet<E> {

        List<E> dta = new ArrayList<E>();
        Map<E, Integer> idx = new HashMap<E, Integer>();

        public RandomSet() {
        }

        public RandomSet(Collection<E> items) {
            for (E item : items) {
                idx.put(item, dta.size());
                dta.add(item);
            }
        }

        @Override
        public boolean add(E item) {
            if (idx.containsKey(item)) {
                return false;
            }
            idx.put(item, dta.size());
            dta.add(item);
            return true;
        }

        /**
         * Override element at position <code>id</code> with last element.
         * @param id
         */
        public E removeAt(int id) {
            if (id >= dta.size()) {
                return null;
            }
            E res = dta.get(id);
            idx.remove(res);
            E last = dta.remove(dta.size() - 1);
            // skip filling the hole if last is removed
            if (id < dta.size()) {
                idx.put(last, id);
                dta.set(id, last);
            }
            return res;
        }

        @Override
        public boolean remove(Object item) {
            @SuppressWarnings(value = "element-type-mismatch")
            Integer id = idx.get(item);
            if (id == null) {
                return false;
            }
            removeAt(id);
            return true;
        }

        public E get(int i) {
            return dta.get(i);
        }

        public E pollRandom(Random rnd) {
            if (dta.isEmpty()) {
                return null;
            }
            int id = rnd.nextInt(dta.size());
            return removeAt(id);
        }

        @Override
        public int size() {
            return dta.size();
        }

        @Override
        public Iterator<E> iterator() {
            return dta.iterator();
        }
    }
    public static void main (String[] args) throws java.lang.Exception
    {
        RandomSet<Integer> rs = new RandomSet<Integer>();
        for (int i = 0; i < 20; ++i) {
            rs.add(i);
        }

        int count = 50;

        Random r = new Random();

        for (int i = 0; i < count; i++) {
            System.out.println(rs.pollRandom(r));
            rs.remove(i);
            rs.add(i + 20);
        }
    }
}

Using the smart structure the overall time complexity is O(N + K), where N is the number of requested polls and K is the size of the pool.

Running Ideone example : http://ideone.com/Sfltr7

Pick non-repeating random number from progressive list

4 Answers4