如何生成一個僞隨機對合？

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構造是否屬於函數的嚴格數學定義。