Gentoo Forums
Gentoo Forums
Gentoo Forums
Quick Search: in
Pseudo-random O(1)-space permuting function?
View unanswered posts
View posts from last 24 hours

 
Reply to topic    Gentoo Forums Forum Index Off the Wall
View previous topic :: View next topic  
Author Message
tamarind
Tux's lil' helper
Tux's lil' helper


Joined: 24 Jan 2005
Posts: 106

PostPosted: Tue Jul 04, 2006 10:19 pm    Post subject: Pseudo-random O(1)-space permuting function? Reply with quote

Such a function is unlikely to exist, but I've always wondered: is there such a thing as a stateless shuffling function? The idea is that you want to visit items in a list n items long in random order. You could build an array of integers and perform a Knuth shuffle on them, but is there a mathematical way to create a chaotic one-to-one mapping of the domain onto itself?

It doesn't even have to be very good randomness for some purposes, just enough to fool a human, but I can't think of any way to safely map the integers that isn't recognizably periodic.

EDIT: This problem is related to perfect hashing, so if I could understand that, then I could understand this. :?


Last edited by tamarind on Thu Jul 06, 2006 2:36 am; edited 1 time in total
Back to top
View user's profile Send private message
valkyrite
Apprentice
Apprentice


Joined: 19 Sep 2002
Posts: 241

PostPosted: Wed Jul 05, 2006 12:01 am    Post subject: Reply with quote

I am not sure about Knuth-shuffling, can you explain it?
Back to top
View user's profile Send private message
tamarind
Tux's lil' helper
Tux's lil' helper


Joined: 24 Jan 2005
Posts: 106

PostPosted: Wed Jul 05, 2006 3:57 am    Post subject: Reply with quote

The Knuth shuffle is an algorithm for shuffling an array in place. Iterating forward through the array, for each element you visit, swap it with either itself or one of the elements ahead of it. I've read that if you swap with the elements you've already visited, the shuffling won't be as effective (as those swaps could undo the shuffling as you move forward?).

Here's a simple implementation for C++:

Code:
template<class T>
void shuffle(T array[], size_t size) {
  for(int i=0; i<size; ++i)
    swap(T[i], T[rand()%(size-i)+i]);
}


There are several deficiencies in that example--e.g. it should use iterators instead of T[]--but it communicates the idea.
Back to top
View user's profile Send private message
Display posts from previous:   
Reply to topic    Gentoo Forums Forum Index Off the Wall All times are GMT
Page 1 of 1

 
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