反转函数以获得给定排列的字典索引

Question

我正在开展一项 Python3 代码挑战，其中消息根据 52 张标准扑克牌的洗牌顺序进行编码或解码。我已经找到了如何对消息进行编码，但我很难反转该函数以从给定的洗牌顺序中获取消息。我有一个函数可以根据索引查找卡片列表的字典排列。我现在需要一个从卡片列表中进行排列并输出其索引的卡片。我有一些想法，但我在数论方面还没有达到应有的水平。我已经发表了一些我的想法的评论。

deck = ["AC", "2C", "3C", "4C", "5C", "6C", "7C", "8C", "9C", "TC", "JC", "QC", "KC",
        "AD", "2D", "3D", "4D", "5D", "6D", "7D", "8D", "9D", "TD", "JD", "QD", "KD",
        "AH", "2H", "3H", "4H", "5H", "6H", "7H", "8H", "9H", "TH", "JH", "QH", "KH",
        "AS", "2S", "3S", "4S", "5S", "6S", "7S", "8S", "9S", "TS", "JS", "QS", "KS",]

def get_nth_permutation( p_index, in_list, out_list=[] ):

    if p_index >= factorial( len(in_list) ): return []
    if not in_list: return out_list

    f = factorial( len(in_list)-1 )
    index = p_index / f # p_index * f
    remainder = p_index % f # pow(p_index, -1, f) - reverse modulo?
    # reverse divmod by adding index + remainder in each step to increase p_index?
    out_list.append( in_list[int(index)] )
    del in_list[int(index)]

    if not remainder: # function should end when out_list + in_list matches deck
        return out_list + in_list # return p_index
        
    else: #keep recursion if possible
        return get_nth_permutation( remainder, in_list, out_list ) 

如有任何帮助，我们将不胜感激。它甚至不必是代码，即使是伪代码解释或一些后续步骤也比我现在的情况更好。

Answer 1

您将获取第一个条目的索引，并将其乘以列表其余部分（没有第一个条目）可能的排列数。对列表的下一个条目重复此逻辑。

这是一个实现：

def get_permutation_index(ordered, perm):
    ordered = ordered[:]  # Get a copy so we don't mutate the original list
    result = 0
    for card in perm:
        i = ordered.index(card)
        ordered.pop(i)
        result += i * factorial(len(ordered))
    return result

备注

• 上面的函数返回一个从 0 开始的索引，就像当您为

  p_index

  传递 0 时，函数将返回第一个排列，而当您传递 1 时，函数将返回第二个排列。如果目的是从 1 开始计数 (正如函数名称中的

  _nth_

  所示），您需要调整这两个函数。

• 您的函数清空给定的

  in_list

  。这意味着，如果您使用

  deck

  作为参数（或上述函数）再次调用它，您将传递一个 empty 列表。如果您的函数不会改变原始列表，那就更好了。

• 将

  []

  作为默认值会对省略此参数的后续调用产生副作用。请参阅Python 中的可变默认参数。我建议不要有这个参数，而是创建一个递归生成器，从中构建要返回的列表。

• 请勿使用

  /

  除法运算符，然后使用

  int()

  。而是使用整数除法运算符：

  //

这是您进行这些调整后的函数：

def get_nth_permutation( p_index, in_list):  # Don't use mutable default
    
    def recur(p_index):
        if p_index >= factorial( len(in_list) ) or not in_list: 
            return
        if not p_index: 
            yield from in_list
            return
        
        f = factorial( len(in_list)-1 )
        index = p_index // f  # Don't use floating point division
        remainder = p_index % f
        yield in_list[index]
        del in_list[index]
        yield from recur(remainder)

    return list(recur(p_index))