aspose file tools*
The moose likes Beginning Java and the fly likes randomly iterating? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "randomly iterating?" Watch "randomly iterating?" New topic
Author

randomly iterating?

Jack Lord
Greenhorn

Joined: Jun 04, 2004
Posts: 11
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!
Tim West
Ranch Hand

Joined: Mar 15, 2004
Posts: 539
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
    Junilu Lacar
    Bartender

    Joined: Feb 26, 2001
    Posts: 4456
        
        6

    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).


    Junilu - [How to Ask Questions] [How to Answer Questions]
    sever oon
    Ranch Hand

    Joined: Feb 08, 2004
    Posts: 268
    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 ]
    Tim West
    Ranch Hand

    Joined: Mar 15, 2004
    Posts: 539
    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 ]
    Jack Lord
    Greenhorn

    Joined: Jun 04, 2004
    Posts: 11
    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.
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: randomly iterating?