-1

I have a collection: [1, 2, 3, 4, 5, 6, 7, 8, 9] from which I need to generate a random number of unique elements e.g. 5, 3, 7, 9, next time: 4, 8. My function works well but sometimes throws StackOverflowError because of recursive call on a function that generates random numbers and checks if there is no duplicates already. I wonder how I can prevent this from happening.

lunar
  • 1,172
  • 7
  • 18
  • 29
  • I think [this link](http://stackoverflow.com/questions/11842533/generating-random-unique-data-takes-too-long-and-eats-100-cpu) should help. I had faced a similar issue earlier. But I feel you should post some code. – Abijeet Patro Sep 05 '12 at 02:39
  • Possible duplicate of [What is a StackOverflowError?](http://stackoverflow.com/questions/214741/what-is-a-stackoverflowerror) – Raedwald Jan 22 '16 at 13:30

3 Answers3

1

One solution is to use iteration (a for or while loop) rather than recursion.

Another solution is to start by making a mutable copy of your collection, and whenever you select an element from it, remove that element so that there's no risk of re-selecting it. (But be sure you're making an actual copy of your collection, e.g. new ArrayList<Integer>(originalCollection), so that you aren't removing elements from the original.)

ruakh
  • 175,680
  • 26
  • 273
  • 307
1

You should probably do this without using recursion. A rough sketch of an algorithm that might work better:

  1. Create an empty list
  2. Go through the source array and add each element with 50% probability to the list
  3. Convert the list to an array
  4. Use Arrays.shuffle() on the array to randomly reorder the elements

That should do the job.

Simon
  • 1,814
  • 20
  • 37
0

Each element in your full list is either present or absent in a particular collection of elements. That tells us to use binary.

0b000000000 maps to [ ] i.e. all numbers absent.

0b111111111 maps to [1, 2, 3, 4, 5, 6, 7, 8, 9] i.e. all numbers present.

Any number between the two, treated as binary, will map to a subset of the whole collection.

0b001010101 maps to [3, 5, 7, 9]

Each binary number in the range will map to a unique subset. Your examples imply that ordering might be important. If it is then you will have to deal with it separately. This method will give you up to 2^9 = 512 different combinations.

rossum
  • 15,344
  • 1
  • 24
  • 38