Shuffle an array of strings randomly

Solution 1:

As far as I know, there is no better solution than repeatedly running the Fisher-Yates shuffle until you find an arrangement without adjacent duplicates. (That's usually called a rejection strategy.)

The amount of time this will take depends on the probability that a random shuffle has adjacent duplicates, which will be low if there are few duplicates and could be as much as 1.0 if more than half of the set is the same majority element. Since the rejection strategy never terminates if there is no possible qualifying arrangement, it could be worth the trouble to verify that a solution is possible, which means that there is no majority element. There's an O(n) algorithm for that, if necessary, but given the precise details you provided, it shouldn't be necessary (yet).

You can reject immediately rather than continuing to the end of the shuffle, which significantly cuts down on the cost of running the algorithm. So just use your shuffle algorithm, but restart the counter if you place an element beside one of its twins.

By the way, using strcpy to move elements around is really inefficient. Just shuffle the pointers.

Here's some code adapted from this answer. I've assumed that the duplicates are exact, for simplicity; perhaps you have some other way of telling (like looking only at the first word):

void shuffle(const char* names[], size_t n) {
  for (size_t i = 0; i < n;) {
    size_t j = i + rand() % (n - i);
    /* Reject this shuffle if the element we're about to place
     * is the same as the previous one
     */
    if (i > 0 && strcmp(names[j], names[i-1]) == 0)
      i = 0;
    else {
      /* Otherwise, place element i and move to the next one*/
      const char* t = names[i];
      names[i] = s[j];
      names[j] = t;
      ++i;
    }
  }
}

For your use case, where you have 10 objects with frequencies 3, 3, 2, and 2, there are 605,376 valid arrangements, out 3,628,800 (10!) total arrangements, so about five of every six shuffles will be rejected before you find a valid arrangement, on average. However, the early termination means that you will do less than six times as much work as a single shuffle; empirical results indicate that it takes about 33 swaps to produce a valid shuffle of 10 objects with the above frequencies.

Note: rand()%k is not a very good way to generate a uniform distribution of integers from 0 to k-1. You'll find lots of advice about that on this site.