稍微改变种子时，随机列表的输出会稍微洗牌

问题：

我想随机洗牌一个列表，但使用种子值s这样，当只稍微改变s时，洗牌的输出也只会略有变化。

详：

我有一个排序的元素列表，例如：

[0,1,3,5,7]

此列表应多次随机播放，每次使用种子值s。当两个种子值s1并且s2 = s1 + d彼此靠近时，随机列表也应该是"相似的"。

通过"相似"，我的意思是新洗牌列表中的元素要么与使用原始种子值s1时相同，要么仅由原始列表中接近它们的值替换(例如它们在原始列表中的直接邻居)。

编辑：输出仍然应该是确定性的，即使用相同的种子s1，当洗牌相同的输入列表时，应该产生相同的随机列表。

上面列表的示例(请注意，添加小值d只会稍微扰乱列表，即许多值保持不变，如果它们发生变化，它们通常会被原始列表中的邻居替换。随着偏移量的增加，列表之间的"差异"可能会进一步增加，并且还可以选择邻居以外的值)：

输出：>[5,0,3,7,1]

Seed：
`s`	： left;">`[5,0,1,7,3]`
`s + d`
`s + 2d`	： left;">`[7,0,3,5,1]`
`s + 3d`	： left;">`[7,0,1,3,5]`

生成并留出列表的随机洗牌R。然后，每次使用种子s调用生成器时：

让我们s = s % factorial(N)其中N是列表的长度(或者只要求s应该介于 0 和 N！-1 之间)。
查找s的阶乘表示
将阶乘表示转换为排列p
将p应用于R并返回结果。

构造使得排列p(s)和p(s+1)在字典顺序上相邻。这些步骤可以有效地实施。

您可以将相同的想法用于排列集的其他排序，从而进一步减少更改，例如堆排序或 Steinhaus-Johnson-Trotter 排序，但我不知道步骤 3. 是否可以在这些情况下有效实施。

如果你能忍受改变你对"相似性">的定义，定义为排列元素之间的交换次数，那么我们可以使用特罗特-约翰逊排列排序，其中连续排列仅相差两次换取

。有一些算法可以将连续的整数秩与排序的连续烫发相关联，还有进一步的算法可以从秩生成烫发，反之亦然。如果将种子作为排名值，则相差 n 的两个种子将需要 n 个项目交换才能在各自的 perms 之间移动。

很多搜索都提到了这本书：

D.L. Kreher和D.R. Stinson，组合算法：生成，《枚举和搜索》，CRC出版社，1999年。

我把它变成了下面的Python：

# -*- coding: utf-8 -*-
"""
Created on Thu Jun  3 08:44:56 2021
@author: Paddy3118
"""
from typing import List
Perm = List[int]
_fact = [1]     # factorials cache

def print_perm(T: Perm) -> None:
print(T)
def tj_unrank(n: int, r: int) -> Perm:
"Returns the r-ranked Trotter-Johnson permutation of integers 0..n-1"
global _fact
for i in range(len(_fact), n+2):    # Extend factorial cache if necessary.
_fact.append(_fact[i - 1] * i)
pi: Perm = [0] * (n+2)
pi[1] = 1
r2 = 0
for j in range(2, n+1):
r1 = (r * _fact[j]) // _fact[n]
k = r1 - j*r2
if ((r2 % 2) == 0):
for i in range(j-1, j - k - 1, -1):
pi[i+1] = pi[i]
pi[j-k] = j
else:
for i in range(j - 1, k, -1):
pi[i+1] = pi[i]
pi[k + 1] = j
r2 = r1
return [i - 1 for i in pi[1:-1]]
def tj_rank(n: int, p: Perm) -> int:
"Returns the ranking of the Trotter-Johnson permutation p, of integers 0..n-1"
assert set(p) == set(range(n)), f"Perm {p} not a perm of 0..{n-1}."
pi = [0] + [i+1 for i in p] + [0]
r = 0
for j in range(2, n + 1):
i = k = 1
while pi[i] != j:
if (pi[i] < j):
k += 1
i += 1
if ((r % 2) == 0 ):
r = j*r+j-k
else:
r = j*r+k-1
return r
def tj_parity(p: Perm) -> int:
"Returns the 0/1 parity of the Trotter-Johnson permutation p, of integers 0..n-1"
n = len(p)
assert set(p) == set(range(n)), f"Perm {p} not a perm of 0..{n-1}."
pi = [0] + [i+1 for i in p] + [0]
a, c = [0] * (n + 1), 0
for j in range(1, n+1):
if a[j] == 0:
c += 1
a[j] = 1
i = j
while ( pi[i] != j ):
i = pi[i]
a[i] = 1
return (n-c) % 2

if __name__ == '__main__':
from sys import argv
import re
if not (len(argv) == 2 and re.match(r'd+', argv[1])):
raise SystemExit('ERROR. Call needs an integer >0 argument')
n = int(argv[1])
if n <=0:
raise SystemExit('ERROR. Call needs one integer >0 argument')
print(f"Testing rank/unrank n={n}.n");
for i in range(len(_fact), n+2):    # Extend factorial cache if necessary.
_fact.append(_fact[i - 1] * i)
for r in range(_fact[n]):
p = tj_unrank(n, r)
rank = tj_rank(n, p)
parity = tj_parity(p)
print(f"  Rank: {r:4} to perm: {p}, parity: {parity} to rank: {rank}")

n == 4 的示例输出

Testing rank/unrank n=4.
Rank:    0 to perm: [0, 1, 2, 3], parity: 0 to rank: 0
Rank:    1 to perm: [0, 1, 3, 2], parity: 1 to rank: 1
Rank:    2 to perm: [0, 3, 1, 2], parity: 0 to rank: 2
Rank:    3 to perm: [3, 0, 1, 2], parity: 1 to rank: 3
Rank:    4 to perm: [3, 0, 2, 1], parity: 0 to rank: 4
Rank:    5 to perm: [0, 3, 2, 1], parity: 1 to rank: 5
Rank:    6 to perm: [0, 2, 3, 1], parity: 0 to rank: 6
Rank:    7 to perm: [0, 2, 1, 3], parity: 1 to rank: 7
Rank:    8 to perm: [2, 0, 1, 3], parity: 0 to rank: 8
Rank:    9 to perm: [2, 0, 3, 1], parity: 1 to rank: 9
Rank:   10 to perm: [2, 3, 0, 1], parity: 0 to rank: 10
Rank:   11 to perm: [3, 2, 0, 1], parity: 1 to rank: 11
Rank:   12 to perm: [3, 2, 1, 0], parity: 0 to rank: 12
Rank:   13 to perm: [2, 3, 1, 0], parity: 1 to rank: 13
Rank:   14 to perm: [2, 1, 3, 0], parity: 0 to rank: 14
Rank:   15 to perm: [2, 1, 0, 3], parity: 1 to rank: 15
Rank:   16 to perm: [1, 2, 0, 3], parity: 0 to rank: 16
Rank:   17 to perm: [1, 2, 3, 0], parity: 1 to rank: 17
Rank:   18 to perm: [1, 3, 2, 0], parity: 0 to rank: 18
Rank:   19 to perm: [3, 1, 2, 0], parity: 1 to rank: 19
Rank:   20 to perm: [3, 1, 0, 2], parity: 0 to rank: 20
Rank:   21 to perm: [1, 3, 0, 2], parity: 1 to rank: 21
Rank:   22 to perm: [1, 0, 3, 2], parity: 0 to rank: 22
Rank:   23 to perm: [1, 0, 2, 3], parity: 1 to rank: 23

(请注意，在上面的烫发中，连续的烫发是如何通过两个项目的交换而有所不同的)。

在这种情况下，很难为"相似"提供指标。[例如：苹果在他们的第一次随机播放实现中遇到了问题 - 人们觉得歌曲的混合不够随机]。

我会以不同的方式重新表述问题"我们如何修改一些简单的洗牌算法，以便我们达到预期的结果？

这是我的想法：

我们将需要一个基线种子s- (很大的东西，与您的案例/数据中通常使用的列表大小相当，此值可以硬编码或作为参数传递，但如果我们改变s1
，则应保持固定
d = abs(s1 - s)- (s1离s有多远)
使用s作为种子进行默认洗牌 - (您选择的语言的随机库中的任何函数都足够了。
现在遍历列表，并将任何概率为 (0,1) 的元素与距离您的位置 d 的任何其他元素交换p。
例如：d = 2
1 2 3 4 5 6 7
元素 5 可以换成 3、4、6 或 7。
posi处的基本元素将与该范围内的任何元素(也可以随机选择)交换，[i-d,i+d]概率为 p。
操纵p和s，直到你的"相似性"分数/感觉得到满足。

问题：

详：

n == 4 的示例输出

相关内容

最新更新

热门标签：