Algorithm for iterating over random permutation

Question

I have a bag that has the following:

• 6 red marbles
• 5 green marbles
• 2 blue marbles

I want to remove a random marble from the bag, record its color, and repeat until no more marbles are left in the bag:

1. sort the counts
   • bag = {2:blue, 5:green, 6:red}
2. compute the cumulative counts
   • cumulative = {2:blue, 7:green, 13:red}
3. pick a random number in [0, max cumulative count]
   • rand(0, 13) = 3
4. find insertion point index of this integer using binary search
   • i = 1
5. record the color corresponding to this index
   • green
6. reduce that count by 1
   • bag = {2:blue, 4:green, 6:red}
7. repeat until no more marbles in bag

Is this a good way to do this or are there more efficient ways in terms of time complexity?

Answer 1

Instead of relying on extraction, you can shuffle the array in-place.

1. like in maraca's answer, you store the items individually in the array (citing it here: "Create a list with all the items (0=red, 1=green, 2=blue): [0,0,0,0,0,0,1,1,1,1,1,2,2].")

2. iterate through the array and, for each element i, pick a random index j of an element to swap place with

3. at the end, just iterate over the array to get a shuffled order.

Something like

for(i=0..len-1) {
  j=random(0..len-1);
  // swap them
  aux=a[i]; a[i]=a[j]; a[j]=aux;
}
// now consume the array - it is as random as it can be
// without extracting from it on the way

Note: many programming languages will have libraries providing already implemented array/list shuffling functions

• C++ - std::random_shuffle

• Java - Collections.shuffle

• Python - random.shuffle

Answer 2

Your algorithm is pretty good, but it could be optimized further:

1. You don't need to sort the colors! You can skip the first step.

2. Instead of calculating the cumulative counts each time you can do it iteratively by decreasing all values right of the selected one (including the selected color itself).

3. You also don't need the binary search, you can just start decreasing the cumulative counts from the end until you reach the correct number.

There is also another algorithm based on lists:

1. Create a list with all the items (0=red, 1=green, 2=blue): [0,0,0,0,0,0,1,1,1,1,1,2,2].

2. Get a random integer i between 0 and the size of the list - 1.

3. Remove the ith item from the list and add it to the result.

4. Repeat 2. and 3. until the list is empty.