Make 2N random selections from size N list whilst avoiding sequential duplicates

Question

Given a list of N objects, how do I make 2N selections in a random order such that no object is chosen twice in succession? (All N objects must be chosen twice.)

EDIT start: My goal is to present a list of words, once on the left and once on the right. No two consecutive trials are to have the same word.

Really I am asking if there is a known technique for doing this, or can someone think of a way to do it without the fiddle. EDIT end

My attempt is shown below, and may be useful as a template for testing.

The premise is to generate randomised indices and then check for repeats. When a repetition is found, swap the first repetition with the value before. Finally, if the lower two elements are the same, swap the 2^nd and 3^rd.

<script type="text/javascript">
    function init() {
        for (rep = 0; rep < 100000; rep++) {
            var indices = [0,0, 1,1, 2,2];
            shuffle(indices);

            for (var i = indices.length - 1; i > 1; i--)
                if (indices[i - 1] == indices[i]) {
                    var tmp = indices[i - 1];
                    indices[i - 1] = indices[i - 2];
                    indices[i - 2] = tmp;
                }

            if (indices[0] == indices[1]) {
                var tmp = indices[1];
                indices[1] = indices[2];
                indices[2] = tmp;
            }

            // test
            for (i = indices.length - 1; i > 1; i--)
                if (indices[i - 1] == indices[i])
                    rep = 1E8;  // fail
        }

        // **EDIT2:** BAD BAD BAD mistake in the check code!!!  Sorry!
        dbg.innerHTML = (rep >= 1E8) ? "Oh bother." : "OK";
    }

    function randomInt(max) { return Math.floor(Math.random() * max); }
    function shuffle(o) { for (var j, x, i = o.length; i; j = randomInt(i), x = o[--i], o[i] = o[j], o[j] = x); return o; }
</script>

<div>
    <span id="dbg" />
</div>

The failure of the method to deal with the lowest two elements is common to the alternative method of selecting from a reducing list. One potentially ends up with two identical elements remaining.

(Note, the method presented is not recommended for use since may not have a uniform random distribution.)

EDIT start: The experiment is supposed to present words in a "random" order. My method below has a 'fiddle' with the last two numbers just seems wrong - at the very least nasty.

(I agree that the overall sequence is not truly random. I am not a mathematician, just trying to code the experiment.) EDIT end

(Shuffle code taken from Jeff's answer.)

Answer 1

Make the list of 2n elements. Walk through it. If you find a repeat at positions i-1, i then swap the ith element with whatever is in a random position other than i, i-1, i-2.

(Sigh, examining the proof found a mistake. Some swaps can't be done without creating an early pairing. You can fix that by only swapping down the road. But now there is 1/n that you'll wind up with a final pair that can't be fixed. But it will still be close to random.)

If your random number generator is truly random, this will give a perfectly random distribution.

Here is a sketch of a proof by induction on i that after the ith step all distributions with no repeats up the position pair (i-1, i) are equally likely. This result with i = 2n-1 would show that the algorithm works.

Let p(i) be the probability of a possible distribution showing up after the ith step. This will be well-defined for i if the result holds for i.

Next it is trivially true for i = 0 because we start with a random shuffle. So p(0) is well-defined.

After the first step, each possible distribution could have been arrived at by having been the result of the shuffle with probability p(0), or by having arrived at a duplication in (0, 1) which was resolved with a swap to this distribution. The second possibility occurred with probability p(0)/(n-2). Therefore the result is true for 1 and p(1) = p(0) + p(0)/(n-2).

For i in 2, ..., 2n-1 you apply the same argument as for i=1 except that p(i) = p(i-1) + p(i-1)/(n-3).

Answer 2

After spending way too much time thinking about this problem [Note 1], I couldn't come up with an unbiased random generation algorithm other than the standard rejection algorithm. (Generate an unbiased sample of shuffle sequences of {0, 0, 1, 1,..., N-1, N-1} and reject the sequence if it contains two consecutive elements.)

Fortunately, the rejection algorithm in this case is not awful, because more than one-third of the total sequences qualify, and you can usually reject them before they are fully generated. So you would expect to generate on average fewer than two rejected sequences before finding one which works, and the possibility of early rejection means the expected time to generate each sequence of length 2N might be less than 4N, which means that it may well be faster than generating a sequence and doing another pass over it to "fix" the repetitions.

The sketch for the assertion that more than one-third of sequences qualify:

1. The number of 2N sequences (including repetitions) is (2N)!/2^N, based on the standard combinatoric counting formula. I'll call that A(n). We can easily see that A(n) is n(2n−1)A(n−1). (The first term is n rather than 2n because the denominator in A(n) has one more 2.)

2. The number of 2N sequences without repetitions (a(n), an equally arbitrary name) is given by the recursion a(n) = n(2n−1)a(n−1) + n(2n−1)a(n−2) [Note 2]. This recursion is very similar, but it has a relatively small second term.

3. It's clear than a(n) < A(n) because it is counting a subset of the same sequences. Also, A(n)/A(n−1) = n(2n−1) while a(n)/a(n−1) > n(2n−1). So a(n) grows slightly more rapidly than A(n) but it can never catch up. Since A(2) is 90 and a(2) is 30, we can assert that 1 < A(n)/a(n) ≤ 3 for all n ≥ 2. (The numbers get big very rapidly. According to OEIS, a(16) is 1453437879238150456164433920000, so A(16)/a(16) is 2.762455825573288. My guess is that the ratio will converge to some value not too far from that, but I did nothing to validate that guess. If I were to go way out on a limb, I might speculate that the limit of the ratio will turn out to be e, but the similarity might be entirely coincidental.)

Here's some not-very-tested javascript code which randomly shuffles a vector to produce a repetition-free result. (You need to initialize the vector once, but you'll get just as random a result starting with the previous shuffle as reinitializing, so I'd strongly suggest just initializing once.)

function reshuffle(indices) {
  for (var i = 0, len = indices.length; i < len;) {
    var j = i + Math.floor(Math.random() * (len - i));
    var tmp = indices[j]; indices[j] = indices[i]; indices[i] = tmp;
    if (i > 0 && indices[i - 1] == indices[i]) i = 0;
    else ++i;
  }
  return indices;
}

On a quick test, with the addition of a loop counter, the loop executed an average of 22.9 times to find a random 12-element vector, and 346 times to find a random 200-element vector.

---

Notes

1. Well, a few hours. But I do have other things to do.

2. I eventually managed to prove this, but I'm not going to write the proof here because of the lack of LaTeX; the sequence is A114938 in the OEIS and you'll find the same recursion there.

Answer 3

One way would be to do a Fischer-Yates shuffle of N items, and return them sequentially. Then shuffle the array again and return them sequentially. The only possibility of returning the same item twice in succession is if the last item from the first shuffle is the first item in the second shuffle. That's easily overcome:

array = shuffle(array);
for each item in array
    return item;

lastItem = array[last];
array = shuffle(array);
if (array[0] == lastItem)
    swap(array[0], array[1]);
for each item in array
    return item;

If you can't shuffle the array, you could easily build an index array and shuffle it, instead.

It's unclear to me if this will solve the problem in the way you want. From your description, it seems like it's okay to have a list that contains duplicates, as long as the duplicates aren't sequential. My solution doesn't produce a duplicate until all other items are produced.