How to randomize order of approximately 20 elements with lowest complexity? (generating random permutations)
-
What do you mean by cca?Stefan Kendall– Stefan Kendall2009-11-07 01:48:33 +00:00Commented Nov 7, 2009 at 1:48
-
Canonical correlation analysis?Murali VP– Murali VP2009-11-07 01:49:04 +00:00Commented Nov 7, 2009 at 1:49
-
more about this freebase.com/view/en/circaAnte– Ante2009-11-07 01:58:41 +00:00Commented Nov 7, 2009 at 1:58
-
ca. and cca. are both abbreviations for circa, although circa is only used to refer to dates: en.wikipedia.org/wiki/CircaThisSuitIsBlackNot– ThisSuitIsBlackNot2009-11-07 02:00:44 +00:00Commented Nov 7, 2009 at 2:00
-
1Isn't this a duplicate of a list shuffle question? stackoverflow.com/questions/375351/…Mathias– Mathias2009-11-07 02:28:52 +00:00Commented Nov 7, 2009 at 2:28
Add a comment
|
4 Answers
Knuth's shuffle algorithm is a good choice.
1 Comment
SourceOverflow
Well I am disappointed that that is the answer. Since you have to first iterate through the list to fill it and then shuffle it (with an admittedly good algorithm), I would have thought that there was a better solution.
Some months ago I blogged about obtaining a random permutation of a list of integers. You could use that as a permutation of indexes of the set containing your elements, and then you have what you want.
In the first post I explore some possibilities, and finally I obtain "a function to randomly permutate a generic list with O(n) complexity", properly encapsulated to work on immutable data (ie, it is side-effect free).
In the second post, I make it uniformely distributed.
The code is in F#, I hope you don't mind!
Good luck.
EDIT: I don't have a formal proof, but intuition tells me that the complexity of such an algorithm cannot be lower than O(n). I'd really appreciate seeing it done faster!
2 Comments
Steve Jessop
All permutations must be possible, and re-arranging an array into a derangement (that is, a permutation
p for which p(k) != k for all k) requires that every element be visited. Hence O(n) worst case. Or is that still not formal enough?Steve Jessop
Also O(n) average case by the same proof, come to think of it, since IIRC the proportion of permutations of (1...n) which are derangements approaches 1/e as n approaches infinity.
A simple way to randomise the order is to make a new list of the correct size (20 in your case), iterate over the first list, and add each element in a random position to the second list. If the random position is already filled, put it in the next free position.
I think this pseudocode is correct:
list newList
foreach (element in firstList)
int position = Random.Int(0, firstList.Length - 1)
while (newList[position] != null)
position = (position + 1) % firstList.Length
newList[position] = element
EDIT: so it turns out that this answer isn't actually that good. It is neither particularly fast, nor particularly random. Thankyou for your comments. For a good answer, please scroll back to the top of the page :-)
3 Comments
Bruno Reis
In the worst case this algorithm is O(n^2) (ie, if your random number generator says "1, 1, 1, 1, 1, 1, 1, ...", I let you calculate the rest), not very optimized.
Guffa
Putting items in the next free position makes it less random. The items will keep their original order more than in a truly random shuffle. To fix that you would have to pick a new random position when a position is taken, which of course makes it a lot slower.
David Johnstone
That's a good point Guffa. I'd never realised that. Thanks. At least I've learnt something here :-)
Probably someone already implemented the shuffling for you. For example, in Python you can use random.shuffle, in C++ random_shuffle, and in PHP shuffle.
1 Comment
Roberto Bonvallet
Surprisingly, in PHP it is called
shuffle :) I'll update my answer.