• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

randomly iterating?

 
Greenhorn
Posts: 11
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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!
 
Ranch Hand
Posts: 539
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
     
    Sheriff
    Posts: 17644
    300
    Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    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).
     
    Ranch Hand
    Posts: 268
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    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
    Posts: 539
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    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
    Posts: 11
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    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.
     
    Opportunity is missed by most people because it is dressed in overalls and looks like work - Edison. Tiny ad:
    a bit of art, as a gift, that will fit in a stocking
    https://gardener-gift.com
    reply
      Bookmark Topic Watch Topic
    • New Topic