MatLAB 帮助：在不连续重复数字的情况下改组预定义向量（所有值的出现次数相等）

Question

我在不重复数字的情况下随机打乱一个向量时遇到了麻烦（例如 1 1 不可接受，但 1 2 是可以接受的），因为每个值都是平等重复的。

更具体地说，我想将矩阵 [1:4] 重复十次（总共 40 个元素），以便 1、2、3 和 4 都重复 10 次而不是连续的。

如果需要任何说明，请告诉我，我希望这个问题很清楚。

这是我目前拥有的：

cond_order = repmat([1:4],10,1); %make matrix
cond_order = cond_order(:); %make sequence

我知道 randperm 非常相关，但我不确定如何在非重复数字的条件下使用它。

编辑：感谢您的所有回复。

我发现我之前说的不太清楚。这些是我想拒绝的例子 [1 1 2 2 4 4 4...]。因此，只要不重复单个值，[1 2 3 4] 是否按该顺序出现并不重要。（所以 [1 2 3 4 1 2 3 4...] 和 [4 3 1 2...] 都可以接受）
最好我正在寻找满足
标准的混洗向量
1. 随机
2. 没有连续重复的值（例如 1 1 4 4）
3. 所有四个值出现的次数相同

Answer 1

根据此处的一些讨论，我认为性能与应用程序的理论要求之间存在 trade-off。

如果需要从所有有效排列的集合中完全统一抽取，则可能需要纯拒绝抽样方法。这样做的问题当然是随着问题规模的增大，拒绝率会变得非常高。为了证明这一点，如果我们考虑问题中的基本示例是 [1 2 3 4] 的 n 倍数，那么我们可以看到每次有效抽奖被拒绝的样本数量如下（注意对数 y 轴）：

我的替代方法是对数组进行随机排序，然后如果检测到重复项，则将再次对剩余元素进行随机排序：

cond_order = repmat(1:4,10,1); %make matrix
cond_order = reshape(cond_order, numel(cond_order), 1);

cond_order = cond_order(randperm(numel(cond_order)));

i = 2;

while i < numel(cond_order)
    if cond_order(i) ~= cond_order(i - 1)
        i = i + 1;
    else
        tmp = cond_order(i:end);
        cond_order(i:end) = tmp(randperm(numel(tmp)));
    end
end

cond_order

请注意，不能保证这会收敛，但在很明显它不会收敛的情况下，我们可以重新开始，re-computing 整个序列仍然会更好.

这绝对满足问题的后两个要求：

B) 没有连续的值

C) 所有 4 个值出现的次数相等

问题是是否满足第一个'Random'要求。

如果我们采用问题的最简单版本，输入 [1 2 3 4 1 2 3 4] 则有 864 个有效排列（根据经验确定！）。如果我们运行两种方法都超过 100,000 运行s，那么我们预计每个排列大约有 115.7 次绘制的高斯分布。

正如预期的那样，纯拒绝抽样方法给出了这个：

然而，我的算法没有：

明显偏向某些样本。

最后还是要看需求。这两种方法都对整个分布进行采样，因此都满足了问题的核心要求。我没有包括性能比较，但除了最简单的情况之外，我相信我的算法会快得多。然而，平局的分布并不完全均匀。它是否足够好取决于应用程序和实际问题的大小。

Answer 2

有点像使用拒绝抽样的想法，只是用 randperm 重复，直到找到没有重复值的序列排列。

cond_order = repmat(1:4,10,1); %//make matrix
N = numel(cond_order); %//number of elements
sequence_found = false;
while ~sequence_found
    candidate = cond_order(randperm(N));
    if all(diff(candidate) ~= 0) %// check if no repeated values
        sequence_found = true;
    end
end
result = candidate;

Answer 3

一个微妙但重要的区别：作者是否需要等概率地选择任何可行序列？

许多人提到了表单的答案，"Let's use randperm and then rearrange the sequence so that it's feasible."这可能行不通。使这个问题变得相当困难的是，如果作者需要平等的机会选择任何可行的序列。让我举个例子来说明问题。

想象一下数字集 [1 2 2 3 4]。首先让我们枚举可行序列的集合：

6 个以 1 开头的序列：[1 2 3 2 4], [1 2 3 4 2], [1 2 4 2 3], [1 2 4 3 2], [1 3 2 4 2], [1 4 2 3 2]。
那么有[2 1]开头的6个序列：[2 1 2 3 4], [2 1 2 4 3], [2 1 3 2 4], [2 1 3 4 2], [2 1 4 2 3], [2 1 4 3 2]。通过对称性，有 18 个序列以 2 开头（即 [2 1] 中的 6 个，[2 3] 中的 6 个，[2 4] 中的 6 个）。
根据对称性，有 6 个以 3 开头的序列和另外 6 个以 4 开头的序列。
因此有 6 * 3 + 18 = 36 个可能的序列。

从可行序列中均匀抽样，第一个数字是2的概率是18/36 = 50%！但是如果你只是随机排列，第一个数字是 2 的概率是 40%！（即集合中 2/5 的数字是 2）

如果需要任何可行序列的等概率，您希望 2 的 50% 作为第一个数字，但天真地使用 randperm 然后在 2:end 处重新调整数字以使序列可行会给你第一个数字是两位的概率为 40%。

请注意，拒绝抽样会得到正确的概率，因为每个可行序列都有相同的被接受概率。（当然拒绝采样变得非常慢，因为被接受的概率趋于 0。）

Answer 4

的解决方案在条理上是正确的，但我认为还有更有效的方法：

他选择等量抽样，检查差异。我选择反过来做，最终得到了一个需要更少迭代的解决方案。

n=4;
k=10;
d=42; %// random number to fail first check
while(~all(sum(bsxfun(@eq,d,(1:n).'),2)==k)) %' //Check all numbers to appear k times.
    d=mod(cumsum([randi(n,1,1),randi(n-1,1,(n*k)-1)]),n)+1; %generate new random sample, enforcing a difference of at least 1.
end

MatLAB 帮助：在不连续重复数字的情况下改组预定义向量（所有值的出现次数相等）

MatLAB help: shuffling a predefined vector without consecutively repeating numbers (with equal occurrences of all values)

matlab

random

octave

shuffle

一个微妙但重要的区别：作者是否需要等概率地选择任何可行序列？