如何生成一个伪随机对合？

Question

为了生成伪随机置换，可以使用Knuth shuffles。对合是自反排列，我想，我可以通过禁止多次触摸元素来适应洗牌。然而，我不确定我是否能够有效地做到这一点，以及它是否会生成每个复制等概率。

恐怕需要一个例子：在一组{0,1,2}上，有6个排列，其中4个是对合。我正在寻找一种以相同的概率随机生成其中一个的算法。

正确但非常低效的算法是：使用Knuth shuffle，如果没有对合，则重试。

Answer 1

我们在这里使用a(n)作为一组大小为n（as OEIS does）的对合数。对于给定的一组尺寸n和该集合中的给定元素，该集合上的对合总数为a(n)。该元素必须由对合不变或者与另一个元素交换。由于这些元素是其他元素的对角线，因此保留我们元素的对合数为a(n-1)。因此，在对合上的均匀分布必须有保持该元素固定的概率a(n-1)/a(n)。如果它是固定的，只需保留该元素。否则，选择另一个尚未被我们的算法检查过的元素与我们的元素交换。我们刚刚决定了集合中的一个或两个元素会发生什么：继续前进，并决定一次发生一个或两个元素的情况。

要做到这一点，我们需要对合每个i <= n的计数的名单，但很容易与递推公式

a(i) = a(i-1) + (i-1) * a(i-2)

（请注意，从OEIS这个公式也来自做了我算法：第一项用于计算保持第一个元素在哪里的对合，第二项用于与它交换的元素）。如果您正在使用对合，这可能足够重要，可以分解为另一个函数，预先计算一些较小的值，并缓存函数的结果以获得更高的速度，如下面的代码所示：

# Counts of involutions (self-inverse permutations) for each size 
_invo_cnts = [1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152] 

def invo_count(n): 
    """Return the number of involutions of size n and cache the result.""" 
    for i in range(len(_invo_cnts), n+1): 
     _invo_cnts.append(_invo_cnts[i-1] + (i-1) * _invo_cnts[i-2]) 
    return _invo_cnts[n] 

我们还需要一种方法来跟踪尚未确定的元素，因此我们可以有效地选择具有一致概率的元素之一和/或按照决定标记元素。我们可以将它们放在一个缩小的列表中，并在列表的当前末尾添加一个标记。当我们决定一个元素时，我们移动列表末尾的当前元素来替换已决定的元素，然后减少列表。以此效率，该算法的复杂性为O(n)，除了可能最后一个元素外，每个元素都有一个随机数计算。更好的订单复杂性是不可能的。

这里是Python 3.5.2中的代码。代码由于未定义元素列表中涉及的间接性而变得复杂一些。

from random import randrange 

def randinvolution(n): 
    """Return a random (uniform) involution of size n.""" 

    # Set up main variables: 
    # -- the result so far as a list 
    involution = list(range(n)) 
    # -- the list of indices of unseen (not yet decided) elements. 
    # unseen[0:cntunseen] are unseen/undecided elements, in any order. 
    unseen = list(range(n)) 
    cntunseen = n 

    # Make an involution, progressing one or two elements at a time 
    while cntunseen > 1: # if only one element remains, it must be fixed 
     # Decide whether current element (index cntunseen-1) is fixed 
     if randrange(invo_count(cntunseen)) < invo_count(cntunseen - 1): 
      # Leave the current element as fixed and mark it as seen 
      cntunseen -= 1 
     else: 
      # In involution, swap current element with another not yet seen 
      idxother = randrange(cntunseen - 1) 
      other = unseen[idxother] 
      current = unseen[cntunseen - 1] 
      involution[current], involution[other] = (
       involution[other], involution[current]) 
      # Mark both elements as seen by removing from start of unseen[] 
      unseen[idxother] = unseen[cntunseen - 2] 
      cntunseen -= 2 

    return involution 

我做了几个测试。下面是我用来检查的有效性，并均匀分布代码：

def isinvolution(p): 
    """Flag if a permutation is an involution.""" 
    return all(p[p[i]] == i for i in range(len(p))) 

# test the validity and uniformness of randinvolution() 
n = 4 
cnt = 10 ** 6 
distr = {} 
for j in range(cnt): 
    inv = tuple(randinvolution(n)) 
    assert isinvolution(inv) 
    distr[inv] = distr.get(inv, 0) + 1 
print('In {} attempts, there were {} random involutions produced,' 
    ' with the distribution...'.format(cnt, len(distr))) 
for x in sorted(distr): 
    print(x, str(distr[x]).rjust(2 + len(str(cnt)))) 

，结果

In 1000000 attempts, there were 10 random involutions produced, with the distribution... 
(0, 1, 2, 3)  99874 
(0, 1, 3, 2) 100239 
(0, 2, 1, 3) 100118 
(0, 3, 2, 1)  99192 
(1, 0, 2, 3)  99919 
(1, 0, 3, 2) 100304 
(2, 1, 0, 3) 100098 
(2, 3, 0, 1) 100211 
(3, 1, 2, 0) 100091 
(3, 2, 1, 0)  99954 

小艾制服给我，因为我做其他检查结果。

Answer 2

对合是一种一对一映射，它是自己的逆。任何密码都是一对一映射;它必须是为了使密文明确地解密。

对于一个对合，你需要一个密码，它是它自己的逆。这样的密码存在，ROT13就是一个例子。其他一些人参见Reciprocal Cipher。

对于你的问题，我会建议一个XOR密码。至少与您的初始数据集中最长的一段数据一样，选择一个随机密钥。如果您使用32位数字，则使用32位密钥。要进行排列，请依次将每个数据与XOR键进行XOR。反向置换（相当于解密）与XOR操作完全相同，并且将返回到原始数据。

这将解决数学问题，但它绝对不是密码安全的。反复使用相同的密钥将允许攻击者发现密钥。我假设除了需要均匀分布的随机看似对合之外，没有任何安全要求。

ETA：这是一个演示，在Java中，我正在谈论我的第二个评论。作为Java，我为你的13个元素集使用索引0..12。

public static void Demo() { 

    final int key = 0b1001; 

    System.out.println("key = " + key); 
    System.out.println(); 

    for (int i = 0; i < 13; ++i) { 

     System.out.print(i + " -> "); 
     int ctext = i^key; 

     while (ctext >= 13) { 
      System.out.print(ctext + " -> "); 
      ctext = ctext^key; 
     } 
     System.out.println(ctext); 
    } 

} // end Demo() 

从演示的输出是：

key = 9 

0 -> 9 
1 -> 8 
2 -> 11 
3 -> 10 
4 -> 13 -> 4 
5 -> 12 
6 -> 15 -> 6 
7 -> 14 -> 7 
8 -> 1 
9 -> 0 
10 -> 3 
11 -> 2 
12 -> 5 

凡变换密钥会脱落，再次变换，直到它落入该阵列中的阵列的端部。我不确定while构造是否属于函数的严格数学定义。