枚举卡片排列的最佳方法是什么？

Question

我正在寻找一个能够为特定洗牌分配值的函数.

该功能必须是双射的.甲板上有52张牌,所以有52张牌!不同的shuffle,因此域是52张卡的所有排列的集合,并且codomain是从1到52的整数!

快速有效地执行此操作的最佳算法是什么？

Answer 1

要将置换编码为伪代码中的值:

A = list of cards
value = 0
for i in range(52):
   cards_left = 52-i
   let pos = index of card i in A 
   delete A[pos]
   value = value * cards_left + pos

最后,A将是一个空列表,值具有表示排列的数字.

要解码:

A = []
value is an input
for i in reversed(range(52)):
   cards_left = 52-i
   pos = value % cards_left
   value = value / cards_left
   Insert card i at index pos in A

最后,A应该包含原始排列.

示例Python代码:

B=[3,2,0,1,4]

def encode(A):
    value = 0
    n = len(A)
    A = A[:] # Take a copy to avoid modifying original input array 
    for i in range(n):
       cards_left = n-i
       pos = A.index(i)
       del A[pos]
       value = value * cards_left + pos
    return value

def decode(value,n):
    A=[]
    for i in range(n-1,-1,-1):
       cards_left = n-i
       value,pos = divmod(value, cards_left)
       A.insert(pos,i)
    return A

v=encode(B)
print v
print decode(v,len(B))