8

How to randomize order of approximately 20 elements with lowest complexity? (generating random permutations)

Jacob
  • 34,255
  • 14
  • 110
  • 165
Ante
  • 8,567
  • 17
  • 58
  • 70

4 Answers4

22

Knuth's shuffle algorithm is a good choice.

David R Tribble
  • 11,918
  • 5
  • 42
  • 52
  • 1
    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. – SourceOverflow Oct 30 '17 at 11:37
2

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!

Bruno Reis
  • 37,201
  • 11
  • 119
  • 156
  • 1
    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 Nov 07 '09 at 03:25
  • 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. – Steve Jessop Nov 07 '09 at 03:27
1

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 :-)

David Johnstone
  • 24,300
  • 14
  • 68
  • 71
  • 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. – Bruno Reis Nov 07 '09 at 02:23
  • 2
    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. – Guffa Nov 07 '09 at 03:00
  • That's a good point Guffa. I'd never realised that. Thanks. At least I've learnt something here :-) – David Johnstone Nov 07 '09 at 03:19
1

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.

Roberto Bonvallet
  • 31,943
  • 5
  • 40
  • 57