Forums Register Login

randomly iterating?

+Pie Number of slices to send: Send
Apologies for any horrible terminology abuse in the title

I'd like to be able to select each element of an array (or vector etc) randomly, and only select each element once. So if I had {1, 9, 7} I would want to get something like 7 then 1 then 9 returned to me. I've only just started with Java but I've wanted to do this quite a few times already so I wondered if there was some easy way to do this.

I did write my own code (just generating integers to be used as index numbers) so I was hoping someone could tell me that I've ignored some obvious Java class that would do it all for me , or tell me if my own effort is any good.



Cheers!
+Pie Number of slices to send: Send
One way to do this:

  • Copy the array into an ArrayList (or similar List). Use Arrays.asList().
  • Use Collections.shuffle() on the List to get a random ordering.
  • Then, just use a normal iterator.


  • I think that makes pretty good use of the APIs



    --Tim
    +Pie Number of slices to send: Send
    Tim's solution is very good.

    The key here is the shuffling step. Here's a simple way to shuffle in place.



    For some reason, your solution is probably the one most people will come up with the first time they have at it (at least it was for most folks I know, including myself).
    +Pie Number of slices to send: Send
    I've come up against the same problem once or twice. I came up with a different solution each time, here are a few. Before I get started, though, I'll point out that I'm not crazy about the one that's already been proposed as it alters the collection that you're pulling from (by shuffling it), which is rarely a desirable side effect.

    1. Create a visitation map of the collection. Presumably it's an ordered collection of some sort so you can associate a number with each element in the collection, such as with an array. Create a boolean[] of the same size, initializing all the values to false. Pick a random value between 0 and the size of the boolean array. If that boolean is false, mark it true and then visit the corresponding element of the collection. If that boolean is already true, you'll already visited that element of the collection so go to the next boolean until you find a false one (mark it true and visit the corresponding element of the collection, etc). Remember to wrap around the end of the boolean array when necessary. When all the elements are true, everything in the collection has been visited.

    You can do a similar thing if it's more convenient...keep an Object array with references to the actual objects in the collection themselves instead of booleans. Before visiting any element of the collection, mark that reference null in the array (corresponds to true in the boolean array).

    2. Copy the contents of the collection into a LinkedList. Working with the List, generate a random integer between 0 and the size of the list. Remove that object from the list and visit it. Generate a random integer between 0 and the new size of the list. Repeat until list is empty.

    3. Clone the collection, shuffle it, and iterate straight through the shuffled copy. Slightly different: create a LinkedList of Integers from 0 to size of collection. Shuffle it, and iterate straight through, using each value as the index into the collection.

    I've presented a lot of ways to do this because you may not have a direct mapping from indices to items in the collection, depending on what you're doing, and you may find one of these approaches more useful than others as a starting point for munging this number or that.

    sev
    [ June 22, 2004: Message edited by: sever oon ]
    +Pie Number of slices to send: Send
    Sev,

    You're right, my solution does alter the original array. I hadn't realised that. But it's trivial to change:



    This makes good use of library methods, but is probably a constant-factor slower than other methods that don't involve copying the array. Also, it won't work with basic types - you have to change the cast. A suitably intelligent array-copier could fix this I guess.

    On a side note, I think my solution runs in linear time...I'm assuming Collections.shuffle() is linear. Your solution two is gonna run in quadratic time. I'd probably use an ArrayList, and keep track of the maximum 'legal' element - similar to Junilu's shuffle algorithm. Solution 1 runs in worst-case quadratic time (if you randomly generated index 0 every time) but the average time may well be better...I haven't analysed it thoroughly enough

    Anyway, that is not so important. I know efficiency isn't a huge concern here, but all algorithms are of the same simplicity, so choosing the most efficient one is reasonable.



    --Tim

    [ June 22, 2004: Message edited by: Tim West ]
    [ June 22, 2004: Message edited by: Tim West ]
    +Pie Number of slices to send: Send
    Thanks for the help guys, much appreciated - and it's given me plenty to think about . I completely missed the shuffle function while I was browsing through the docs. Still, it gave me a chance to have a stab at my own solution. Thanks again.
    This is awkward. I've grown a second evil head. I'm going to need a machete and a tiny ad ...
    a bit of art, as a gift, that will fit in a stocking
    https://gardener-gift.com


    reply
    reply
    This thread has been viewed 6394 times.
    Similar Threads
    Minimum Value and Sum of Values in Array
    Random Numbers, Why You No Work?
    Tips for improving my code
    It compiles but only part of it runs.
    Java-8 Streams - creating a class with stream() method
    More...

    All times above are in ranch (not your local) time.
    The current ranch time is
    Mar 28, 2024 17:49:19.