Generate unique random numbers in an Array

[Eric Matthew]

Is there any way to do this without resorting to using ArrayList and Collections.shuffle? I'm just trying to figure out if it is possible using a series of loops and or booleans.

package prayitworks;

public class Bored {

	static int[] lottoBalls = new int[11];
	static int[] tempArray  = new int[11];
	static int counter = 0;
	
	
	
	public static int ranNum() {
		int drawedNum = 1 + (int)(Math.random()* 6);
		return drawedNum;
	}
	
}

Main method below

package prayitworks;

public class BoredHome {

	public static void main(String[] args) {
		for (int i = 0; i < Bored.lottoBalls.length; i++) {
			Bored.lottoBalls[i] = Bored.ranNum();
			System.out.println("Ball # " + i + " has been drawn and is " + Bored.lottoBalls[i]);
			
			//creates a copy of lottoBalls to store the values and test later
			for (int j = 0; j < i; j++) {
				Bored.tempArray[j] = Bored.lottoBalls[i];
			}
		        //below can be ignored, was just trying to brainstorm of something.
			for (int k = 0; k < Bored.lottoBalls.length; k++) {
				int m = 0;
				while (Bored.lottoBalls[k] == Bored.tempArray[m]) {
					Bored.lottoBalls[k] = Bored.ranNum();
				}
				m++;
			}
			
		}
	}

}

Any help would be appreciated.Thank for taking the time to look over.

[Campbell Ritchie]

You can try a Stream

myArray = myRandom.ints(0, 1000)
                  .boxed()
                  .distinct()
                  .limit(50L)
                  .toArray(Integer[]::new);

… will return an Integer[] size 50 with different numbers between 0…999. The distinct() call may require lots of memory if there are large numbers of data to compare.

The way it works is:

1: myRandom is an instance of java.util.Random

2: It has an ints method: in that overriding it returns an unlimited stream of ints (IntStream) randomly chosen between 0 and less than 1000

3: The boxed method changes it from an IntStream to a Stream<Integer>. If you miss this line out you remain with an IntStream.

4: The distinct method removes duplicates. If you look up its documentation you find it can be expensive in memory.

5: The limit method truncates the current stream to 50L elements. When that truncation occurs, all the preceding Streams stop because they are executed lazily.

6: The toArray method changes it to an array; it is a good idea to use the type and ::new which means call the constructor. If you don't use boxed, miss out the argument toArray()

I think that code will work. If you miss out the boxed() call and miss out the argument to toArray, you get an int[] array rather than Integer[].

[Tushar Goel]

How about using hashset? Add elements you want and then iterate it. You will get numbers in random order. But i am not sure how much random they are.

[Campbell Ritchie]

No, the numbers do not come out in random order if you iterate a hash set. The order is difficult to predict, but it is reproducible.
You can on the other hand use a set to confirm that you are not duplicating a number.

[Tushar Goel]

Thanks Campbell. Then if save the number in Set then still we need some mechanism to take random number out.

[Campbell Ritchie]

You don't need to save the numbers in a Set. You can use the Set to confirm that the number has not been used already, and you store the numbers in order of creation elsewhere. Once you have finished confirming uniqueness of the numbers, then you no longer need the set.

By the way: those are not truly random numbers and you shouldn't call them random. I have only just remembered this bit. Random numbers permit duplication and even runs of the same number. I once won £10 on a little game called “heads or tails,” which appears to be popular with schoolchildren, by repeatedly betting on heads, and got a run. I think you would call those numbers something like random selection from a declining population.

[Robert D. Smith]

Campbell Ritchie wrote: I think you would call those numbers something like random selection from a declining population.

I simply refer to it as the non-random random number generator.

By the way, that MyRandom code was really slick. I love learning new stuff, and I have something new to play with. Might work well with a project I am pretending to work on.

Regards,
Robert

[Campbell Ritchie]

Robert D. Smith wrote: . . .
I simply refer to it as the non-random random number generator.

What a lovely name!

By the way, that MyRandom code was really slick. . . .

Thank you. It is (I hope) just a commonplace example of how you can use Streams to make coding easier to read. If you get a Java8 book, it will tell you that is moving from an imperative to a declarative style, where you tell the JVM what you want to do rather than how to do it. Compare that will using a loop

Set<Integer> numbersChosen = new HashSet<>();
Random myRandom = new Random();
int[] numbers = new int[FIFTY];
int index = 0;
while (index < FIFTY)
{
   int random = myRandom.nextInt(1000);
   if (numbersChosen.add(random))
   {
      numbers[index++] = random;
   }
}

Isn't that crystal‑clear! Particularly lines 8 and 10. Aren't they really easy to understand? And having 11 lines as against the earlier example's 5 lines, no 7 when you include two declarations, or is it 6 if you miss out boxed(), it is so much quicker to write

Remember the version of my code where you miss out the boxed call is one line shorter and the last line is simpler, because you simply write .toArray();

[fred rosenberger]

Robert D. Smith wrote:

Campbell Ritchie wrote: I think you would call those numbers something like random selection from a declining population.

I simply refer to it as the non-random random number generator.

In my discrete math class, they use to refer to it as "tile selection from a bag without replacement" - like in Scrabble where you select tiles with letters. Then you have to consider if duplicates are allowed or not - I think there are 12 'E' tiles in Scrabble, for example.

[Campbell Ritchie]

Better name than what I had. But I am bound to forget it before I use it again

[Piet Souris]

I do not think that in general Streams are easier to read than non-stream methods.
Just have a look at the APIs, you'll be in for a shock.

But I agree: they are big fun!

Campbells method is both elegant and short, can't beat that method
(no matter how hard I tried. Kudos!)

Nevertheless, I tried to come up with some alternatives, based on the
old algorithm:

you have a list containing the numbers 1 ... N. Pick some random
number from that list, store it and remove it from the list.
(indeed: drawing without replacement)

Et cetera, until you have the required size or the list becomes
empty. This way you never get a duplicate, at the cost of creating
that list in the first place.

I tried to use both a Java 7 solution and some stream ways, to keep
myself a little bit in shape and maybe for some who are interested.

But again: big fun! And that is why I recommend the Scala course
at Coursera.

Greetz,
Piet

public class Lotto {
    public static void main(String... args) {
        int max = 49, size = 6;
        for (int i = 1; i <= 10; i++) {
            System.out.println("**********************************");
            System.out.println(Arrays.toString(lotto(max,size)));
            System.out.println(Arrays.toString(lotto2(max,size)));
            System.out.println(Arrays.toString(lotto3(max,size)));
            System.out.println(Arrays.toString(lotto4(max,size)));
        }
        
        int[] temp = new Random().ints(1, max + 1).limit(10000).toArray();
        Map<Integer, Integer> freqs = 
                Arrays.stream(temp)
                .boxed()
                .collect(
                    Collectors.groupingBy(
                        i -> i, 
                        HashMap::new, 
                        Collectors.summingInt(p -> 1)
                    )
                )
        ;
        System.out.println("*********************************");
        System.out.println(freqs);
    }
    
    private static int[] lotto(int max, int size) {
        int[] arr = IntStream.rangeClosed(1, max).toArray();
        Random r = new Random();
        return 
            IntStream.range(0, size)
                .map(i -> {int index = r.nextInt(max - i); 
                           int p = arr[index]; 
                           arr[index] = arr[max - i - 1]; 
                           return p;
                          }
                    )
                .toArray()
        ;
    }
    
    private static int[] lotto2(int max, int size) {
        List<Integer> list = 
            IntStream.rangeClosed(1, max).boxed().collect(Collectors.toList());
        Random r = new Random();
        return IntStream
                .range(0, size)
                .map(i -> list.remove(r.nextInt(max - i)))
                .toArray();
    }
    
    private static int[] lotto3(int max, int size) {
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i <= max; i++) list.add(i);
        int[] answer = new int[size];
        Random r = new Random();
        for (int i = 0; i < size; i++) answer[i] = list.remove(r.nextInt(max - i));
        return answer;
    }
    
    private static int[] lotto4(int max, int size) {
        // is Campbells method, only a bit longer
        Random r = new Random();
        return IntStream
            .generate( () -> r.nextInt(max) + 1)
            .distinct()
            .limit(size)
            .toArray()
        ;
    }
}

[Eric Matthew]

Thank you Piet and Ritchie for your replies and possible solutions. Despite how daunting it looks, I really enjoyed looking over them and look forward to learning more.

And thank you Robert for your comment, I don't know why I didn't see it that way before but now looking it that way makes it much more clearer in my head now.

I believe I found a solution that doesn't involve ArrayList, Collections, Streams or anything scary that I haven't learned yet. Just for and if loops.

Here is the code without any comments.

package tuesdayjulydeletelater;
import java.util.Random;

public class LottoSim {
	
	public static void main(String[] args) {
		
		Random ranObj = new Random();
		int[] lottoBalls = new int[10];
		lottoBalls[0] = 1 + ranObj.nextInt(9);
		
		for (int i = 1; i < lottoBalls.length;  ++i) {
		lottoBalls[i] = 1 + ranObj.nextInt(9);
		
			for (int j = 0; j < i; j++) {
				if (lottoBalls[j] == lottoBalls[i]) {
					lottoBalls[i] = 1 + ranObj.nextInt(9);
					j = 0;
				}
			}
			System.out.println("Lotto Ball #" + i + " has been picked and is " + lottoBalls[i]);
		}
	}
}

The code again but with comments.

package tuesdayjulydeletelater;
import java.util.Random;

public class LottoSim {
	
	public static void main(String[] args) {
		
		Random ranObj = new Random();
		int[] lottoBalls = new int[10];
		lottoBalls[0] = 1 + ranObj.nextInt(9);
		
		//Loop that fills the lottoBalls array
		for (int i = 1; i < lottoBalls.length;  ++i) {
		lottoBalls[i] = 1 + ranObj.nextInt(9);
		
			//nested for loop that starts at the initial value of the array, this for loops repeats for as many array elements have been initialized.
			for (int j = 0; j < i; j++) {
				// Nested if statement to see if the initial value of lottoBall array is equal to the current element of the array.
				if (lottoBalls[j] == lottoBalls[i]) {
					//If the above statement is true, then the current array element's value is changed "randomly".
					lottoBalls[i] = 1 + ranObj.nextInt(9);
					// J is set to zero to test again (pseudo recursive).
					j = 0;
				}
			}
			//If the nested if statement is false, no array element is changed, String below is printed and we jump back to the first for loop
			// and go again till the loop condition is false. 
			System.out.println("Lotto Ball #" + i + " has been picked and is " + lottoBalls[i]);
		}
	}
}

Feel free to not hold back and critique any inefficiencies you notice or any adjustments that can be made.

[Campbell Ritchie]

You will be running in quadratic time. Or even cubic time. You will get slow performance if you have a large array.

Two arrays: one to contain the numbers.
The other a boolean[]; whenever you insert a number, you use that as the index for the boolean[], and change the value there. Then you can check whether the number has already been used. Unless you have many millions of possible choices, you shouldn't run out of memory, and that will run in linear time.

Both methods will run forever if your range of possible values is smaller than the size of the arraya.

[Campbell Ritchie]

There is mention of the generate method in my thread from last week. Because generate is unordered, that may cause problems if you want the numbers to maintain their order; I presume that is why you used an array.

If you simply want six numbers between 1 and 49 (as used in the UK national lottery) you can use a set

Set<Integer> balls = new TreeSet<>();
while (balls.size() < SIX)
{
   balls.add(myRandom.nextInt(FORTY_NINE) + 1);
}
for (Integer i : balls)
{
   System.out.println(i);
}

Remember sets do not support order, but a TreeSet is sorted automatically, so the six numbers will be printed in ascending order.