electro-music.com   Dedicated to experimental electro-acoustic
and electronic music
 
    Front Page  |  Radio
 |  Media  |  Forum  |  Wiki  |  Links
Forum with support of Syndicator RSS
 FAQFAQ   CalendarCalendar   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   LinksLinks
 RegisterRegister   ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in  Chat RoomChat Room 
go to the radio page Live at electro-music.com radio 1 Please visit the chat
poster
 Forum index » DIY Hardware and Software » ChucK programming language
Randomizing an array
Post new topic   Reply to topic Moderators: Kassen
Page 1 of 1 [13 Posts]
View unread posts
View new posts in the last week
Mark the topic unread :: View previous topic :: View next topic
Author Message
djdaphalgan



Joined: Jul 19, 2007
Posts: 20
Location: Belgium

PostPosted: Fri Jul 20, 2007 12:09 am    Post subject: Randomizing an array Reply with quote  Mark this post and the followings unread

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
View user's profile Send private message
Kassen
Janitor
Janitor


Joined: Jul 06, 2004
Posts: 7678
Location: The Hague, NL
G2 patch files: 3

PostPosted: Fri Jul 20, 2007 4:49 am    Post subject: Reply with quote  Mark this post and the followings unread

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
View user's profile Send private message Send e-mail Visit poster's website
kijjaz



Joined: Sep 20, 2004
Posts: 765
Location: bangkok, thailand
Audio files: 4

PostPosted: Sat Jul 21, 2007 3:15 am    Post subject: Reply with quote  Mark this post and the followings unread

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
View user's profile Send private message Send e-mail Visit poster's website Yahoo Messenger MSN Messenger
Kassen
Janitor
Janitor


Joined: Jul 06, 2004
Posts: 7678
Location: The Hague, NL
G2 patch files: 3

PostPosted: Sat Jul 21, 2007 8:28 am    Post subject: Reply with quote  Mark this post and the followings unread

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
View user's profile Send private message Send e-mail Visit poster's website
Kassen
Janitor
Janitor


Joined: Jul 06, 2004
Posts: 7678
Location: The Hague, NL
G2 patch files: 3

PostPosted: Sat Jul 21, 2007 8:38 am    Post subject: Reply with quote  Mark this post and the followings unread

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
View user's profile Send private message Send e-mail Visit poster's website
kijjaz



Joined: Sep 20, 2004
Posts: 765
Location: bangkok, thailand
Audio files: 4

PostPosted: Sat Jul 21, 2007 12:33 pm    Post subject: Reply with quote  Mark this post and the followings unread

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
View user's profile Send private message Send e-mail Visit poster's website Yahoo Messenger MSN Messenger
Kassen
Janitor
Janitor


Joined: Jul 06, 2004
Posts: 7678
Location: The Hague, NL
G2 patch files: 3

PostPosted: Sat Jul 21, 2007 1:19 pm    Post subject: Reply with quote  Mark this post and the followings unread

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
View user's profile Send private message Send e-mail Visit poster's website
kijjaz



Joined: Sep 20, 2004
Posts: 765
Location: bangkok, thailand
Audio files: 4

PostPosted: Sat Jul 21, 2007 9:19 pm    Post subject: Reply with quote  Mark this post and the followings unread

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
View user's profile Send private message Send e-mail Visit poster's website Yahoo Messenger MSN Messenger
Kassen
Janitor
Janitor


Joined: Jul 06, 2004
Posts: 7678
Location: The Hague, NL
G2 patch files: 3

PostPosted: Sat Jul 21, 2007 10:33 pm    Post subject: Reply with quote  Mark this post and the followings unread

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
View user's profile Send private message Send e-mail Visit poster's website
dewdrop_world



Joined: Aug 28, 2006
Posts: 858
Location: Guangzhou, China
Audio files: 4

PostPosted: Mon Jul 23, 2007 4:35 am    Post subject: Reply with quote  Mark this post and the followings unread

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
View user's profile Send private message Visit poster's website AIM Address
kijjaz



Joined: Sep 20, 2004
Posts: 765
Location: bangkok, thailand
Audio files: 4

PostPosted: Mon Jul 23, 2007 11:04 am    Post subject: Reply with quote  Mark this post and the followings unread

eh seems like that's kinda the same as my proposed algorithm..
hmm interesting.

it looks easy to understand hmmm.
Back to top
View user's profile Send private message Send e-mail Visit poster's website Yahoo Messenger MSN Messenger
dewdrop_world



Joined: Aug 28, 2006
Posts: 858
Location: Guangzhou, China
Audio files: 4

PostPosted: Mon Jul 23, 2007 11:05 am    Post subject: Reply with quote  Mark this post and the followings unread

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
View user's profile Send private message Visit poster's website AIM Address
kijjaz



Joined: Sep 20, 2004
Posts: 765
Location: bangkok, thailand
Audio files: 4

PostPosted: Mon Jul 23, 2007 8:07 pm    Post subject: Reply with quote  Mark this post and the followings unread

dewdrop_world, thanks for the algorithm from SC.
I'm dreaming up some more ideas now -_-"
Back to top
View user's profile Send private message Send e-mail Visit poster's website Yahoo Messenger MSN Messenger
Display posts from previous:   
Post new topic   Reply to topic Moderators: Kassen
Page 1 of 1 [13 Posts]
View unread posts
View new posts in the last week
Mark the topic unread :: View previous topic :: View next topic
 Forum index » DIY Hardware and Software » ChucK programming language
Jump to:  

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Forum with support of Syndicator RSS
Powered by phpBB © 2001, 2005 phpBB Group
Copyright © 2003 through 2009 by electro-music.com - Conditions Of Use