in All availableThis forumThis topic
Author Message
xandris
Tux's lil' helper

Joined: 24 Jan 2005
Posts: 108
Location: Chula Vista, CA

 Posted: Tue Jul 04, 2006 10:19 pm    Post subject: Pseudo-random O(1)-space permuting function? 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 xandris on Thu Jul 06, 2006 2:36 am; edited 1 time in total
valkyrite
Apprentice

Joined: 19 Sep 2002
Posts: 241

 Posted: Wed Jul 05, 2006 12:01 am    Post subject: I am not sure about Knuth-shuffling, can you explain it?
xandris
Tux's lil' helper

Joined: 24 Jan 2005
Posts: 108
Location: Chula Vista, CA

Posted: Wed Jul 05, 2006 3:57 am    Post subject:

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 void shuffle(T array[], size_t size) {   for(int i=0; i

There are several deficiencies in that example--e.g. it should use iterators instead of T[]--but it communicates the idea.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 All times are GMT Page 1 of 1

 Jump to: Select a forum Assistance----------------News & AnnouncementsFrequently Asked QuestionsInstalling GentooMultimediaDesktop EnvironmentsNetworking & SecurityKernel & HardwarePortage & ProgrammingGamers & PlayersOther Things GentooUnsupported Software Discussion & Documentation----------------Documentation, Tips & TricksGentoo ChatGentoo Forums FeedbackOff the WallDuplicate Threads International Gentoo Users----------------中文 (Chinese)DutchFinnishFrenchDeutsches Forum (German)  Diskussionsforum  Deutsche DokumentationGreekForum italiano (Italian)  Forum di discussione italiano  Risorse italiane (documentazione e tools)Polskie forum (Polish)  Instalacja i sprzęt  Polish OTWPortuguese  Documentação, Ferramentas e DicasRussianScandinavianSpanishOther Languages Architectures & Platforms----------------Gentoo on AMD64Gentoo on PPCGentoo on SparcGentoo on Alternative ArchitecturesGentoo for Mac OS X (Portage for Mac OS X)
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