Shuffle an array while making each index have the same probability to be in any index

Question

I want to shuffle an array, and that each index will have the same probability to be in any other index (excluding itself).

I have this solution, only i find that always the last 2 indexes will always ne swapped with each other:

void Shuffle(int arr[]. size_t n)
{
  int newIndx = 0;
  int i = 0;

  for(; i > n - 2; ++i)
  {
    newIndx = rand() % (n - 1);
    if (newIndx >= i)
    {
      ++newIndx;
    }

    swap(i, newIndx, arr);
  }
}

but in the end it might be that some indexes will go back to their first place once again.

Any thoughts?

C lang.

Answer 1

A permutation (shuffle) where no element is in its original place is called a derangement.

Generating random derangements is harder than generating random permutations, can be done in linear time and space. (Generating a random permutation can be done in linear time and constant space.) Here are two possible algorithms.

---

The simplest solution to understand is a rejection strategy: do a Fisher-Yates shuffle, but if the shuffle attempts to put an element at its original spot, restart the shuffle. [Note 1]

Since the probability that a random shuffle is a derangement is approximately 1/e, the expected number of shuffles performed is about e (that is, 2.71828…). But since unsuccessful shuffles are restarted as soon as the first fixed point is encountered, the total number of shuffle steps is less than e times the array size for a detailed analysis, see this paper, which proves the expected number of random numbers needed by the algorithm to be around (e−1) times the number of elements.

In order to be able to do the check and restart, you need to keep an array of indices. The following little function produces a derangement of the indices from 0 to n-1; it is necessary to then apply the permutation to the original array.

/* n must be at least 2 for this to produce meaningful results */
void derange(size_t n, size_t ind[]) {
  for (size_t i = 0; i < n; ++i) ind[i] = i;
  swap(ind, 0, randint(1, n));
  for (size_t i = 1; i < n; ++i) {
    int r = randint(i, n);
    swap(ind, i, r);
    if (ind[i] == i) i = 0;
  }
}

Here are the two functions used by that code:

void swap(int arr[], size_t i, size_t j) {
  int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
}

/* This is not the best possible implementation */
int randint(int low, int lim) {
  return low + rand() % (lim - low);
}

---

The following function is based on the 2008 paper "Generating Random Derangements" by Conrado Martínez, Alois Panholzer and Helmut Prodinger, although I use a different mechanism to track cycles. Their algorithm uses a bit vector of size N but uses a rejection strategy in order to find an element which has not been marked. My algorithm uses an explicit vector of indices not yet operated on. The vector is also of size N, which is still O(N) space [Note 2]; since in practical applications, N will not be large, the difference is not IMHO significant. The benefit is that selecting the next element to use can be done with a single call to the random number generator. Again, this is not particularly significant since the expected number of rejections in the MP&P algorithm is very small. But it seems tidier to me.

The basis of the algorithms (both MP&P and mine) is the recursive procedure to produce a derangement. It is important to note that a derangement is necessarily the composition of some number of cycles where each cycle is of size greater than 1. (A cycle of size 1 is a fixed point.) Thus, a derangement of size N can be constructed from a smaller derangement using one of two mechanisms:

• Produce a derangement of the N-1 elements other than element N, and add N to some cycle at any point in that cycle. To do so, randomly select any element j in the N-1 cycle and place N immediately after j in the j's cycle. This alternative covers all possibilities where N is in a cycle of size > 3.

• Produce a derangement of N-2 of the N-1 elements other than N, and add a cycle of size 2 consisting of N and the element not selected from the smaller derangement. This alternative covers all possibilities where N is in a cycle of size 2.

If Dn is the number of derangements of size n, it is easy to see from the above recursion that:

Dn = (n−1)(Dn−1 + Dn−2)

The multiplier is n−1 in both cases: in the first alternative, it refers to the number of possible places N can be added, and in the second alternative to the number of possible ways to select n−2 elements of the recursive derangement.

Therefore, if we were to recursively produce a random derangement of size N, we would randomly select one of the N-1 previous elements, and then make a random boolean decision on whether to produce alternative 1 or alternative 2, weighted by the number of possible derangements in each case.

One advantage to this algorithm is that it can derange an arbitrary vector; there is no need to apply the permuted indices to the original vector as with the rejection algorithm.

As MP&P note, the recursive algorithm can just as easily be performed iteratively. This is quite clear in the case of alternative 2, since the new 2-cycle can be generated either before or after the recursion, so it might as well be done first and then the recursion is just a loop. But that is also true for alternative 1: we can make element N the successor in a cycle to a randomly-selected element j even before we know which cycle j will eventually be in. Looked at this way, the difference between the two alternatives reduces to whether or not element j is removed from future consideration or not.

As shown by the recursion, alternative 2 should be chosen with probability (n−1)Dn−2/Dn, which is how MP&P write their algorithm. I used the equivalent formula Dn−2 / (Dn−1 + Dn−2), mostly because my prototype used Python (for its built-in bignum support).

Without bignums, the number of derangements and hence the probabilities need to be approximated as double, which will create a slight bias and limit the size of the array to be deranged to about 170 elements. (long double would allow slightly more.) If that is too much of a limitation, you could implement the algorithm using some bignum library. For ease of implementation, I used the Posix drand48 function to produce random doubles in the range [0.0, 1.0). That's not a great random number function, but it's probably adequate to the purpose and is available in most standard C libraries.

Since no attempt is made to verify the uniqueness of the elements in the vector to be deranged, a vector with repeated elements may produce a derangement where one or more of these elements appear to be in the original place. (It's actually a different element with the same value.)

The code:

/* Deranges the vector `arr` (of length `n`) in place, to produce
 * a permutation of the original vector where every element has
 * been moved to a new position. Returns `true` unless the derangement
 * failed because `n` was 1.
 */
bool derange(int arr[], size_t n) {
  if (n < 2) return n != 1;
  /* Compute derangement counts ("subfactorials") */
  double subfact[n];
  subfact[0] = 1;
  subfact[1] = 0;
  for (size_t i = 2; i < n; ++i)
    subfact[i] = (i - 1) * (subfact[i - 2] + subfact[i - 1]);

  /* The vector 'todo' is the stack of elements which have not yet
   * been (fully) deranged; `u` is the count of elements in the stack
   */
  size_t todo[n];
  for (size_t i = 0; i < n; ++i) todo[i] = i;
  size_t u = n;

  /* While the stack is not empty, derange the element at the
   * top of the stack with some element lower down in the stack
   */
  while (u) {
    size_t i = todo[--u];      /* Pop the stack */
    size_t j = u * drand48();  /* Get a random stack index */
    swap(arr, i, todo[j]);     /* i will follow j in its cycle */
    /* If we're generating a 2-cycle, remove the element at j */
    if (drand48() * (subfact[u - 1] + subfact[u]) < subfact[u - 1])
      todo[j] = todo[--u];
  }
  return true;
}

---

Notes

1. Many people get this wrong, particularly in social occasions such as "secret friend" selection (I believe this is sometimes called "the Santa game" in other parts of the world.) The incorrect algorithm is to just choose a different swap if the random shuffle produces a fixed point, unless the fixed point is at the very end in which case the shuffle is restarted. This will produce a random derangement but the selection is biased, particularly for small vectors. See this answer for an analysis of the bias.

2. Even if you don't use the RAM model where all integers are considered fixed size, the space used is still linear in the size of the input in bits, since N distinct input values must have at least N log N bits. Neither this algorithm nor MP&P makes any attempt to derange lists with repeated elements, which is a much harder problem.

Answer 2

Your algorithm is only almost correct (which in algorithmics means unexpected results). Because of some little errors scattered along, it will not produce expected results.

First, rand() % N is not guaranteed to produce an uniformal distribution, unless N is a divisor of the number of possible values. In any other case, you will get a slight bias. Anyway my man page for rand describes it as a bad random number generator, so you should try to use random or if available arc4random_uniform.

But avoiding that an index come back at its original place is both incommon, and rather hard to achieve. The only way I can imagine is to keep an array of the numbers [0; n[ and swap it the same as the real array to be able to know the original index of a number.

The code could become:

void Shuffle(int arr[]. size_t n)
{
  int i, newIndx;
  int *indexes = malloc(n * sizeof(int));
  for (i=0; i<n; i++) indexes[i] = i;
  for(i=0; i < n - 1; ++i)           // beware to the inequality!
  {
    int i1;
    // search if index i is in the [i; n[ current array:
    for (i1=i; i1 < n; ++i) {
      if (indexes[i1] == i) {          // move it to i position
        if (i1 != i) {                 // nothing to do if already at i
          swap(i, i1, arr);
          swap(i, i1, indexes);
        }
        break;
      }
    }
    i1 = (i1 == n) ? i : i+1;          // we will start the search at i1
                                       // to guarantee that no element keep its place
    newIndx = i1 + arc4random_uniform(n - i1);
    /* if arc4random is not available:
    newIndx = i1 + (random() % (n - i1));
    */
    swap(i, newIndx, arr);
    swap(i, newIndx, indexes);
  }
  /* special case: a permutation of [0: n-1[ have left last element in place
   * we will exchange the last element with a random one
   */
  if (indexes[n-1] == n-1) {
    newIndx = arc4random_uniform(n-1)
    swap(n-1, newIndx, arr);
    swap(n-1, newIndx, indexes);
  }
  free(indexes);    // don't forget to free what we have malloc'ed...
}

Beware: the algorithm should be correct, but the code has not been tested and can contain typos...