☰

如何根据洗牌强度指标获得随机洗牌序列？

tag-icon • tag-icon shell-script
如何根据洗牌强度指标获得随机洗牌序列？

我需要获得一个范围内的一系列打乱元素的序列，但是我想确定多少这个序列应该被打乱。例如，假设我们的范围是1-100，我想要一个由 10 个数字组成的序列。所有这些序列都是有效的：

{1,5,17,43,44,67,77,77,83,90}

{1,90,17,43,44,77,77,67,83,5}

{67,5,90,77,43,77,17,1,83,44}

正如你所看到的，三个序列的所有元素都是相同的，但它们的洗牌强度不同。第一个序列已排序（即未打乱），第二个序列稍微打乱了一点，最后一个序列打乱了更多（也许只有这个序列真正打乱了:)）。现在我想要一种方法，以便我可以根据称为洗牌强度指示器或 的指示器来获取此类序列si2。

我的方法

我希望这部分不会让我的问题成为XY问题。我只想分享我的方法，这不是问题的重点。不过，如果我在本节中的问题得到解答，我会很高兴。

我使用了以下一系列命令来获取范围内 2,000,000 个数字的序列1-2000000：

for i in `seq 10000`; do 
    shuf -i 1-2000000 -r -n 100 | sort ; shuf -i 1-2000000 -r -n 100; 
    done > input

正如您所看到的，该序列有 10,000 个由 100 个数字组成的块，这些数字是交叉排序和打乱的序列。例如，我可以使用150代替第一100和50代替第二，所以洗牌强度变为四倍。但这种方法有一些问题（至少对我来说）。

  • 这种方法是太慢了（ 和我想知道为什么。我发现块越大，操作速度就越快。）。
  • 它还需要手动测定表示洗牌强度的两个数字的其中之一。
  • 而且，也许最重要的是，并不是真正随机洗牌。正如您所看到的，块大小是相同的。

理想的解决方案

理想情况下，我想要一个带有如下选项的脚本：

myshuf SI2 MIN MAX NUM [OUTPUT]

whileMIN确定MAX范围，NUM确定序列的大小，SI2是洗牌强度指标。越高SI2，洗牌越激烈。SI2将在 0 到 10 之间。

所以

myshuf 0 0 2000000 2000000

给出 0 到 2,000,000 之间的 2,000,000 个数字的排序序列，并且

myshuf 10 0 2000000 2000000

给出了一个非常好的洗牌序列。

如果您想知道为什么我需要这样的序列，我应该说我有一些排序算法，我想尝试每一种算法，看看它们在不同类型的输入上的时间复杂度。

答案1

以不同强度进行洗牌的一种方法可能是采用排序列表并进行不同数量的随机排列（确保元素不会移动多次）。

shuffle() {
  awk -v n="$1" '
    {line[NR]=$0; i[NR] = NR}
    END{
      if (n > NR/2) {
        print "two many permutations"
        exit(1)
      }
      srand()
      for (x = 1; x <= NR; x++) {
        # shuffle the list of indicies
        y = int(rand() * NR) + 1
        tmp = i[x]; i[x] = i[y]; i[y] = tmp
      }
      for (x = 1; x <= n; x++) {
        # get the lines to permute from the head of the shuffled
        # list of indices
        y = i[x*2-1]; z = i[x*2]
        tmp = line[y]; line[y] = line[z]; line[z] = tmp
      }
      for (x = 1; x <= NR; x++) print line[x]
    }'
}

$ seq 10 | shuffle 0 | paste -sd , -
1,2,3,4,5,6,7,8,9,10
$ seq 10 | shuffle 1 | paste -sd , -
1,2,6,4,5,3,7,8,9,10
$ seq 10 | shuffle 5 | paste -sd , -
9,6,5,10,3,2,8,7,1,4

shuffle 5将保证没有任何元素保留其原始位置（shufflen保证 2*n 元素获得不同的位置）。有些洗牌是它永远无法实现的。例如，对于 1,2,3 列表，唯一可能的结果是2,1,3,3,2,1和1,3,2。不是3,1,2

有了，你也可能会得到一个你可能不太混乱的shuffle 5结果。6,7,8,9,10,1,2,3,4,5

相关内容