从大小为N的列表中进行2N个随机选择，同时避免顺序重复 [英] Make 2N random selections from size N list whilst avoiding sequential duplicates

问题描述

给出N个对象的列表，如何以随机顺序进行2N个选择，以使没有对象连续被选择两次？ （所有N个对象必须选择两次。）

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.

前提是生成随机索引，然后检查重复。找到重复项后，将第一个重复项替换为之前的值。最后，如果下面两个元素相同，则交换2 ^nd 和3 ^rd 。

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

（随机播放代码取自 Jeff的答案。）

(Shuffle code taken from Jeff's answer.)

推荐答案

花费了方式考虑到这个问题[注1]的时间过多，除了标准拒绝算法之外，我无法提出一种无偏的随机生成算法。 （生成 {0，0，1 ,, ...，N-1，N-1} 的随机排序样本，并拒绝该序列，如果包含

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

幸运的是，在这种情况下，拒绝算法并不是很糟糕，因为超过了全部序列的三分之一，因此您通常可以拒绝它们在它们完全生成之前。因此，在找到一个有效的序列之前，您会期望平均生成少于两个的拒绝序列，而且早期拒绝的可能性意味着生成长度为2N的每个序列的预期时间可能少于4N，这意味着它可能会更快

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. 2 N 个序列（包括重复）的数量为（2 N ）！/ 2 ^N ，基于标准组合计数公式。我将其称为 A （ n ）。我们可以很容易地看到 A （ n ）是 n （2 n − 1） A （ n − 1）。 （第一项是 n 而不是2 n ，因为 A （ n ）中的分母还有2 。）

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个 N 个无重复序列的数量（ a （ n ），一个同等任意的名称）由递归 a （ n ）= n （2 n − 1） a （ n − 1）+ n （2 n − 1） a （ n − 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.

比 a （ n ）< A （ n ），因为它正在计算相同序列的子集。此外， A （ n ）/ A （ n − 1）= n （2 n − 1）而 a （ n ）/ a （ n &min ;; 1）> n （2 n − 1）。因此， a （ n ）的增长速度要快于 A （ n ），但它永远无法追赶。由于 A （2）为90而 a （2）为30，我们可以断言1 < A （ n ）/ a （ n ）≤对于所有 n ≥ 3 2.（数字迅速变得非常大。根据 OEIS ， a （16）是1453437879238150456164433920000，所以 A （16）/ a （16）是2.762455825573288。我的猜测是该比率将收敛到某个值距离不是很远，但我没有做任何验证该猜测的方法。如果我要大步走出去，我可能会推测该比率的极限将变成 e ，但是

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

这是一些未经测试的JavaScript代码，它随机地将向量随机产生无重复的结果。 （您需要对向量进行一次初始化，但是从上一次随机播放开始，您将获得与重新初始化一样的随机性，因此我强烈建议您进行一次初始化。）

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;
}

在快速测试中，添加循环计数器后，将执行循环平均22.9次找到一个随机的12个元素向量，346次找到一个随机的200个元素向量。

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.

1. 好吧，几个小时。但是我确实还有其他事情要做。

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

我最终设法证明了这一点，但是由于缺乏相关性，我不打算在这里写证明。胶乳;序列为OEIS中的 A114938 ，您将在此处找到相同的递归。

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.

这篇关于从大小为N的列表中进行2N个随机选择，同时避免顺序重复的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！