在每个索引处具有唯一值的生成多个数字序列

Question

我有一行数字1:n。我想添加第二行，也是使用数字1:n，但这些数字应该是随机的，同时满足以下条件:

1. 两行中没有相同的数字
2. 没有重复出现的数字组合

例如，在下面的示例中：

Row 1:  1  2  3  4  5  6  7 ...
Row 2:  3  6  15 8  13 12 7 ...  

数字7在第1行和第2行的同一位置出现（即在第7个位置；因此不符合规则1）

而在以下情况中

Row 1:  1  2  3  4  5  6  7 ...
Row 2:  3  7  15 8  13 12 2 ...

数字2和7的组合出现了两次（分别在位置2和7，因此不符合规则2）。

可能手工完成这个任务是可行的，但耗时过长（至少在一个合理的范围内），然而在MATLAB中必定会有相当优雅的解决方案。

- rvrvrv

---

假设有10个人，如果其中三个人形成一个独立的循环，与其他人分开，你会感到满意吗？例如：1->2 2->3, 3->1。如果你希望禁止这样的分组方式，那么我在我的答案中描述了一个简单的解决方案。 - Aaron McDaid

Answer 1

这个问题被称为排列的错位。
使用函数randperm来找到数据的随机排列。

x = [1  2  3  4  5  6  7];
y = randperm(x);

然后，您可以检查序列是否合法。如果不是，请一遍又一遍地重试..每次成功的概率约为0.3，这意味着您需要尝试大约10/3次才能找到它。因此，您将很快找到答案。

或者，您可以使用此算法创建随机置换。

编辑

如果您只想拥有大小> 2的周期，则这是问题的概括。在其中写道，这种情况下的概率较小，但足够大，可以在固定步骤内找到它。因此，相同的方法仍然有效。

- Andrey Rubshtein

---

我认为这是部分错位。为了扩展您提供的 PDF 文档中所述的类比：虽然任何绅士都不应该取回自己的帽子（错位），但也不应该有两个绅士拿着对方的帽子（规则 2，请参见我的编辑）。也许可以在 Matlab 中创建一个脚本，针对这两个规则比较随机生成的 '1:n' 序列，直到找到同时满足两个规则的序列为止？ - rvrvrv

@user1092247，我已经更新了我的答案。欢迎来到SO。如果您喜欢我的答案，请不要忘记点赞和采纳。 - Andrey Rubshtein

Answer 2

这很简单。创建节点的随机排列，但按以下方式解释列表：将其解释为围绕节点的随机行走，并且如果节点'b'出现在节点'a'之后，则表示节点'b'在列表中出现在节点'a'下面：

因此，如果您的初始随机排列是：

3 2 5 1 4

那么在这种情况下，遍历路径为3 -> 2 -> 5 -> 1 -> 4，您可以按以下方式创建行：

Row 1:  1 2 3 4 5
Row 2:  4 5 2 3 1

这个随机游走将满足两个条件。

但是你是否希望在你的网络中允许多个循环？我知道你不想让两个人互相拥有对方的帽子。但是如果有7个人，其中3个人互相拥有对方的帽子，另外4个人也互相拥有对方的帽子，这样做是否可接受和/或可取？

- Aaron McDaid

---

回想起来：我花了一点时间才理解你的意思，但从理论上讲，这似乎是最优雅的解决方案，因为它不需要任何循环（“试错”）！ - rvrvrv

@user1092247，没问题，我不得不稍微编辑我的答案，使其更易读。如有任何措辞建议，请随意提出。 - Aaron McDaid

Answer 3

Andrey已经向您指出了randperm和拒绝抽样的方法。在生成排列p之后，检查它是否有固定点的简单方法是any(p==1:n)。检查它是否包含长度为2的循环的简单方法是any(p(p)==1:n)。

因此，这可以得到满足您要求的1:n的排列p：

p=[];
while (isempty(p))
    p=randperm(n);
    if any(p==1:n), p=[]; 
    elseif any(p(p)==1:n), p=[]; 
    end
end

将其包围在一个for循环中，并对每个while循环的迭代计数，似乎每个“有效”的排列平均需要生成4.5个（如果不允许长度为三的循环，则为6.2）。非常有趣。

- arne.b

---

这是一段很棒的代码！满足第二个条件（使用“p(p)”）的解决方案运行良好（尽管确实需要“试错”循环）。谢谢！ - rvrvrv