Jump to content
  • Advertisement
Sign in to follow this  
gorgorath

randomizing an array

This topic is 4491 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

i have a input array, containing 3 million points (x, y, z) but i want to randomize the location of this points in the array. how to quickly( not realtime ) do this without wasting to much memory

Share this post


Link to post
Share on other sites
Advertisement
I think you'll still have to use an algorithm that runs through the whole lot, even if you have three million of them. Run through in order and for each one in normal order, swap it with one other randomly selected one.

Share this post


Link to post
Share on other sites
Quote:
Original post by gorgorath
but how do i know if the one in random order is not used before


I take it you mean you don't want to re-order an element thats already been re-ordered.

1. This is slower, because you have to make an additional check.
2. It doesn't matter, random means random. I think you would be making your algorithm 'less random' by doing the additional check. At the very least its not an improvement.

Share this post


Link to post
Share on other sites
It doesn't matter - it is still a random order. How do you know when you shuffle a deck of cards that a card you are shuffling hasn't been shuffled before?

The only alternative I can see would be to create another array of empty spaces then copy each item from the original list into a random space in the new array, first checking the random space selected hasn't been used but then you have potential indefinate postponement.

Perhaps there is some clever maths algorithm for this I don't know about.

[EDIT] Sorry Dabooksha. Just behind you.

Share this post


Link to post
Share on other sites
See here for a description of a common and uniformly distributed shuffling algorithm (second paragraph in section). Another link in there goes to here which then links to implementations in both C and Java (you'll have to scroll down a wee bit, or search for "Shuffling an array").

Share this post


Link to post
Share on other sites
So let me get this straight - You DO have to make that extra check to get a perfectly uniform distribution? I dont get it.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!