c++ - 随机排列非重复序列

Question

一年前我问过a question在 R 论坛中关于如何将序列排列 1000 次但不允许重复元素。情况仍然如此，R 中的任何解决方案对于我的需求来说都太慢了。

问题是这样的:

对于每个字母都是一个单独元素的序列，例如

"...IDPGCGDCIDPGCGCDIDPGCGDCPGCIDPFJAIAHAHAHABAHAHABKPGCPGCGCECDGCPGCGCIDIPFCPGEPAJIAEPGCECJIPGCGPGCGCGADPDJDPGCPCPGCDIPEPGCJAJMAHZABAHAHAHABHAHBKRZALOBKAHABKLAHAHAHABKLKLAKLBKABABLAHAHABKBKLOKIABKLAHAHABKLABKALKABKLKAHBAKLABKBAHABLALKABABJLKAKLKHABKCRAHAKLKAKLABKLKLBKAHAKLKECECGDCGECGEDGCDGDGECECEGDCACACAHABABCDCHAHBKCQGCGCQCQGCQCGCACACBKCDCAHACQGCPGCDACAPCQAHAHBKACHAHAHBABCGCGCAHAHAMHMABAHAKLABKCPCFCABCQCQGCGCABHAHANBKQAHAHANANABKLABAKLPCGCGCPCAHABAHAHAHAHANBKALCQCGCECAHABANAHBKAKBKAHABAHBKALBHAHABKLKCPCECALCGCAKPHBAHAHAHAHAHAHABAHAHBKAMJABAHBAHAHBKALKABKPCQBANAHANHABKHBALAHALAHANBANBHABKAHANHAHABKAHAHAHAHAMANIAHABANHABABKBKLHLKLBKLKBKBKBALAHAKLBKLBHKBABHAMABKZAHAHABLKAHABAKABKOKHAKAHAHBKAHAHAHABKLHAHBKAHABKLAHAHABKAIAIAHABKLBAIAIKLKLAHAH..."

我需要置换(随机打乱)这个序列 10000 次。原始序列从来没有任何重复元素。随机采样的序列需要与原始序列具有相同比例的元素，并且没有重复元素。序列最长可达 50,000 个元素。每个元素的总数看起来像这样:

 A    B    C    D    E    F    G    H    I    J    K    L    M    N    O    P    Q    R    Z 
6537 3156 1736  198  445  138 1129 3849  818  287 2339 1190  275 1035  222  484  242  338   59 

我已经尝试使用 R 来解决这个问题。尝试的一切都太慢了，而且也不太擅长找到非重复元素。我不太了解 C++，但有兴趣尝试通过 Rcpp 来利用它来获得有效的解决方案。

我认为这将是一个有趣的问题，并会在允许的情况下为其增加赏金。

样本长序列是available here .

Answer 1

一种方法是通过在随机位置添加新元素而不是按顺序选择每个元素来一次构建一个元素的序列。

使用以下算法:

• 在没有非重复约束的情况下随机排列列表以获得插入元素的随机顺序。将此列表称为 a。
• 从一个空列表 b 开始。
• 对于 a 中的每个元素 e:
  • 将attempts设置为零
  • 虽然 attempts <max_attempts:
    • 从0到b.size()中随机选择一个位置p，0表示第一个元素之前，b .size() 表示在最后一个元素之后，并检查是否可以在此位置插入 e 而不会导致重复。如果可能，则将 e 插入 b 的 p 位置，否则增加 attempts 并重试
  • 如果在 max_attempts 次尝试中没有插入元素，则从头开始

我无法证明这会产生均匀分布，但我认为它不会有任何偏差将某些元素聚集到序列的开头或结尾，使用顺序方法可以更加确定可能性.它有可能失败(例如，如果为要插入的第一个和第二个元素选择了相同的元素)，但这是廉价的，而 b 很短，并且它变得越长就越不可能(假设频率分布类似于您向我们展示的那个)。 OTOH，您很容易想出一个会导致它失败的病态分布(例如 10000 As 和 10000 Bs，没有其他字母)。

这可以在 C++ 中使用列表 b 的 STL 列表以及引用列表中每个元素的迭代器数组在线性时间内实现。添加新元素时，将指向该元素的迭代器添加到数组的末尾。要在列表中选择一个随机位置，请从数组中随机选择一个迭代器。