Author |
Message |
djdaphalgan
Joined: Jul 19, 2007 Posts: 20 Location: Belgium
|
Posted: Fri Jul 20, 2007 12:09 am Post subject:
Randomizing an array |
|
|
Is there an easy (fast) way to randomize an array? Suppose I have an array of ints [1,2,3,4]. I want that this algoritme radomizes the array (so the output can be for example [4,2,1,3]). I have made a little function that can swap to numvers in the array, and I run this function a few times in a for loop to randomize the array. This kind of works, but isn't there an easier way to do this? (In Java, there is a shuffle functions for Array objects build in to the language) |
|
Back to top
|
|
|
Kassen
Janitor
Joined: Jul 06, 2004 Posts: 7678 Location: The Hague, NL
G2 patch files: 3
|
Posted: Fri Jul 20, 2007 4:49 am Post subject:
|
|
|
No, sorry, you'll have to build one yourself. We don't have automatic array sorting yet either, that could come in handy as well. _________________ Kassen |
|
Back to top
|
|
|
kijjaz
Joined: Sep 20, 2004 Posts: 765 Location: bangkok, thailand
Audio files: 4
|
Posted: Sat Jul 21, 2007 3:15 am Post subject:
|
|
|
Thanks. This is one think I'd like to practice also.
I guess I'll make a simple function for this kind of shuffling.
I consider it a homework heheh, here's my result.
Here's one way I'll do the shuffling:
Code: | fun void IntArrayShuffle(int array[])
{
for(int i; i < array.cap() - 1; i++)
{
// randomize the position to swap
Std.rand2(i, array.cap() - 1) => int WhichToSwap;
// swap
array[i] => int dummy;
array[WhichToSwap] => array[i];
dummy => array[WhichToSwap];
}
}
[1, 2, 3, 4, 5, 6, 7, 8] @=> int array1[];
<<< "Original Array:", "" >>>;
for(int i; i < array1.cap(); i++) <<< "Array[", i,"] = ", array1[i] >>>;
IntArrayShuffle(array1);
<<< "Shuffled Array:", "" >>>;
for(int i; i < array1.cap(); i++) <<< "Array[", i,"] = ", array1[i] >>>; |
The algorithm is really easy to understand:
for each member, swap randomly with any positions that's still not swapped.
hmm I guess this is quite a brute-force algorithm.
but very easy to understand. |
|
Back to top
|
|
|
Kassen
Janitor
Joined: Jul 06, 2004 Posts: 7678 Location: The Hague, NL
G2 patch files: 3
|
Posted: Sat Jul 21, 2007 8:28 am Post subject:
|
|
|
My take (I just wrote this, didn't try to run it).
What I'm doing is that I'm putting each value of the original array back in a random new spot. If the new spot is already taken I'll go to the next free one, looping round if nesicary. Not sure if this is more random then swapping locations in general BUT it's not a full 100% random, this wouldn't be sutiable for crypto, for example. I'm sure the "swap" way has issues too because that algorithem is always going to return the same array as the input was if the input was a array of length 2.
Code: | fun void IntArrayShuffle(int array[])
{
//keeps track of what locations we already wrote to;
int tracker[array.cap()];
//This is what we'll return
int result[array.cap()];
int temp;
for(int i; i < array.cap() - 1; i++)
{
// randomize the place to write to
Std.rand2(i, array.cap() - 1) => temp;
//avoid writing to the same spot twice
while (tracker[temp]) ++temp%array.cap();
array[i] => result[temp];
1 => tracker[temp];
}
//write out again
for(int i; i < array.cap() - 1; i++) result[i] => array[i];
} |
The issue is that after the first value is placed to the new array, then next value is twice as likely to end up im the spot after is as it is to end up on any other spot (etc).
The alternative would be something like this;
Code: | fun void IntArrayShuffle(int array[])
{
//keeps track of what locations we already wrote to;
int tracker[array.cap()];
//This is what we'll return
int result[array.cap()];
Std.rand2(i, array.cap() - 1) => int temp;
for(int i; i < array.cap() - 1; i++)
{
// randomize the place to write to
while (tracker[temp]) Std.rand2(i, array.cap() - 1) => temp;
array[i] => result[temp];
1 => tracker[temp];
}
//write out again
for(int i; i < array.cap() - 1; i++) result[i] => array[i];
} |
However, that version will react spectacularly bad to very large arrays, it's going to take that poor algorithem quite a while to find the last empty spot in a array that's a million locations long and worse; there is no guarantee that it will ever finish.
A compromise might be using the top version two or three times? Maybe some people with "cs" in their email adress can help us, this is hard stuff. _________________ Kassen Last edited by Kassen on Sat Jul 21, 2007 8:43 am; edited 1 time in total |
|
Back to top
|
|
|
Kassen
Janitor
Joined: Jul 06, 2004 Posts: 7678 Location: The Hague, NL
G2 patch files: 3
|
Posted: Sat Jul 21, 2007 8:38 am Post subject:
|
|
|
WHOOOPS! I take back what I said about the swapping method. I had overlooked that it allows for swapping a entry with itself so it shouldn't always return the same thing for arrays of length 2. Sorry about that. _________________ Kassen |
|
Back to top
|
|
|
kijjaz
Joined: Sep 20, 2004 Posts: 765 Location: bangkok, thailand
Audio files: 4
|
Posted: Sat Jul 21, 2007 12:33 pm Post subject:
|
|
|
oh oh no problem. That is one thing we can improve more on that model..
hmm... but it's pretty fast for today's cpu ^_^" |
|
Back to top
|
|
|
Kassen
Janitor
Joined: Jul 06, 2004 Posts: 7678 Location: The Hague, NL
G2 patch files: 3
|
Posted: Sat Jul 21, 2007 1:19 pm Post subject:
|
|
|
Actually, after thinking about it some more, I think your try is better then both of my own examples. In your example everything gets swapped once (possibly with itself but that's the same for everything) and on all other steps it has a equal chance of being swapped as well. Right now my gut says that should be utterly random so doing more passes shouldn't improve the randomness but it's a hard thing to think about.
However when you wrote; "for each member, swap randomly with any positions that's still not swapped.", that's not what avtually happens (you are swapping with any other member) which is a good thing, I don't think it's that "bruteforce" either. Of cource looping over a big array will take some time but we'll need to loop over it anyway, no way around that and four writes plus generating a random number seems entirely reasonable.
Definately a cool excersise! _________________ Kassen |
|
Back to top
|
|
|
kijjaz
Joined: Sep 20, 2004 Posts: 765 Location: bangkok, thailand
Audio files: 4
|
Posted: Sat Jul 21, 2007 9:19 pm Post subject:
|
|
|
Hmmm yeah I guess so.
That // comment doesn't go with the actual process -_-"
Hmm..
I still can't think of any more easy ways to jump around the array
with significantly less looping.
What I haven't done is some more complex / faster sorting.
I guess what I've been doing all the time is the bubble sort hahha
cute -_-" |
|
Back to top
|
|
|
Kassen
Janitor
Joined: Jul 06, 2004 Posts: 7678 Location: The Hague, NL
G2 patch files: 3
|
Posted: Sat Jul 21, 2007 10:33 pm Post subject:
|
|
|
Nah, I think it's good like this. It definately can't get a lot smaller and everything else I can come up with is less random.
About sorting; Wikipedia has some nice articles about different sorting algorithems with visualisations. I have been thinking about those; if we look at those like small buffers they all morph from cyclical noise to a saw wave but different algorithems do so in a different way.
I was thinking it might be cool to implement those algorithems in some timed way and playback the buffer in the meantime, then compare their different sound as they morph from noise to a (imperfect) saw.
BTW; for smaller arrays I don't think the ineficiency of Bubblesort matters that much, if you'd like to -say- sort the last 10 MIDI notes and turn that into a sorted scale Bubble sort should be fine,
It'd still be cool to have eficient sorting (for int and float) and randomising (for all arays) of arrays in a real build-in labrary. _________________ Kassen |
|
Back to top
|
|
|
dewdrop_world
Joined: Aug 28, 2006 Posts: 858 Location: Guangzhou, China
Audio files: 4
|
Posted: Mon Jul 23, 2007 4:35 am Post subject:
|
|
|
The supercollider scramble algorithm is to loop through all elements except the last one and swap it with a value that occurs after it in the array.
In sc code (sorry for not writing in chuck but the algorithm is self-explanatory anyway):
Code: | ~scrambler = { |array|
var out = array.copy; // non-destructive
if(array.size > 1) {
for(0, array.size - 2, { |i|
out.swap(i, i + rand(array.size - i))
})
};
out
}; |
a = [1, 2, 3, 4, 5];
~scrambler.(a);
outputs: [ 4, 2, 5, 1, 3 ]
hjh _________________ ddw online: http://www.dewdrop-world.net
sc3 online: http://supercollider.sourceforge.net |
|
Back to top
|
|
|
kijjaz
Joined: Sep 20, 2004 Posts: 765 Location: bangkok, thailand
Audio files: 4
|
Posted: Mon Jul 23, 2007 11:04 am Post subject:
|
|
|
eh seems like that's kinda the same as my proposed algorithm..
hmm interesting.
it looks easy to understand hmmm. |
|
Back to top
|
|
|
dewdrop_world
Joined: Aug 28, 2006 Posts: 858 Location: Guangzhou, China
Audio files: 4
|
Posted: Mon Jul 23, 2007 11:05 am Post subject:
|
|
|
kijjaz wrote: | eh seems like that's kinda the same as my proposed algorithm..
hmm interesting.
it looks easy to understand hmmm. |
Oh, yes, you're right, I didn't read yours carefully enough.
hjh _________________ ddw online: http://www.dewdrop-world.net
sc3 online: http://supercollider.sourceforge.net |
|
Back to top
|
|
|
kijjaz
Joined: Sep 20, 2004 Posts: 765 Location: bangkok, thailand
Audio files: 4
|
Posted: Mon Jul 23, 2007 8:07 pm Post subject:
|
|
|
dewdrop_world, thanks for the algorithm from SC.
I'm dreaming up some more ideas now -_-" |
|
Back to top
|
|
|
|