This is NOT the best way to do this. However, it shows some of the qualities of a set and how one might go about making one. A simple ArrayList shuffle is the least amount of code but also gives you the least amount of control. The previous answers would/should be sufficient for your needs. This is just my 2 cents.
EDIT: The fun part of this code is the halting problem applies.
Anudeep - when you say "without repetition", what about 1232 or 1241? Does it count as "repetition" if the repeated digits are not adjacent to each other? The algorithms given thus far do not allow any repetition at all, even non-adjacent repetition. But your post isn't entirely clear on this point, so this might be something worth considering.
Joined: Oct 13, 2005
I was away enjoying the fresh air and fireworks at Whitby, but people worked out the correct history without my help
Rooks Forgenal wrote:A simple ArrayList shuffle is the least amount of code but also gives you the least amount of control.
Can you explain that? I'm not saying that one has to do a shuffle, but whenever I hear the words 'random' and either 'unique' or 'distinct' used together, it's what immediately springs to my mind.
1. It's execution time is predictable and constant.
2. It works for choosing any number of objects from 2 to n from a set of size n.
3. It gets more efficient the more objects you need to choose; the "pick a random object I haven't picked yet" method gets less efficient.
4 It is likely to be the "most" random form of such a selection for a given RNG (Random Number Generator).
The reason for #4 is that the 'shuffle' algorithm itself uses the RNG exactly once for each element, and can actually be proved to be as random as possible, given the constraints of a shuffle. Your method is more like a cache, where you have 'hits' and 'misses'; and it's the misses that may highlight any skews in your RNG.
Oddly enough, you don't even need to shuffle the entire list/array in order to select a bunch of objects, viz:Note: the above method will obviously change the contents of data; but it can be called repeatedly with no loss of randomness. It's basically a partial Fisher-Yates shuffle.
Joined: Jun 05, 2009
I LOVE that code. I love it because I can predict its runtime it is simple and short.
Rooks Forgenal wrote:Let's make it generic, shall we?
If you want to make it really generic, how about:The only method you'd need to add is:
public T remove() which removes an item at random from the Bag. Sound familiar?
Joined: Mar 05, 2008
Hmmm, that remove() sounds deceptively similar to an existing API method, but isn't.
I was thinking of something more like
This way you don't need to spend time copying the original source, and you don't change the source. You can just internally create an int for all the indices, lazily shuffle them (even lazily initializing them if you want), and use the shuffled indices to view the source.
Joined: Mar 05, 2008
For the earlier generic code, I would at least make it a generic method, not a method on a generic class. I.e. change
The type can be inferred from both srcArray and TClass, no need to get it from the parent class as well. And if we use collections instead of arrays, we don't need TClass either - we can infer the whole thing. Which leads to the API in my previous post.