排序列表的高效反转

Question

我有长度为3到25的数据列表，使用ascii（作为整数）。例如，x=[3,56,43,96,23]。假设我应用一个排序，使得y=sorted(x)。记住排序（比如存储一个字节）最有效的方法是什么

试着说得更清楚些。只有5个！=120个从x到自身的双射。因此，我只需要2**7位（小于一个字节）的信息来记住任何一种排序方法。然而，如何有效地将排序映射到二进制表示尚不清楚

假设x的长度为5，让我们试着使其更精确。写函数f(x)和g(y,b)的最佳方法是什么，其中f(x)的输出是字节b，这样如果g被赋予x的排序版本（即y）和字节b，那么g将再次输出x。像

x = [3,56,43,96,23]
y = sorted(x)
b = f(x)
print(x==g(y,b)) #Should print True. 

Answer 1

以下是与Nick相同的解决方案，但我试图通过避免生成列表和继续使用生成器来节省内存：

from itertools import permutations


def f(scrambled_list):
    ind, sorted_list = zip(*sorted(enumerate(scrambled_list), key=lambda x: x[1]))
    for index, perm in enumerate(permutations(range(len(scrambled_list)))):
        if perm == ind:
            return index


def g(sorted_list, pos):
    for index, perm in enumerate(permutations(range(len(sorted_list)))):
        if index == pos:
            break
    else:
        raise Exception('Could not find permutation')
    ret, _ = zip(*sorted(zip(sorted_list, perm), key=lambda x: x[1]))
    return list(ret)


x = [3, 56, 43, 96, 23]
print(x)
y = sorted(x)
print(y)
b = f(x)
print(b)
print(g(y, b))
print(x == g(y, b))  # Should print True.

输出：

[3, 56, 43, 96, 23]
[3, 23, 43, 56, 96]
20
[3, 56, 43, 96, 23]
True

Answer 2

更新

就内存和搜索时间而言，使用itertools.permutation显然效率低下。要解决这个问题，您可以直接使用this answer中描述的函数计算阶乘/逆阶乘表示：

def rank(n, p, q):
    if n == 1:
        return 0
    s = p[n-1]
    p[n-1], p[q[n-1]] = p[q[n-1]], p[n-1]
    q[s], q[n-1] = q[n-1], q[s]
    return s + n * rank(n-1, p, q)

def unrank(n, r, p):
    if n > 0:
        p[n-1], p[r % n] = p[r % n], p[n-1]
        p = unrank(n - 1, r // n, p)
    return p

def f(x):
    # sort x including indexes
    s = sorted(enumerate(x), key=lambda y:y[1])
    # extract the indexes to a list
    p = [t[0] for t in s]
    # find the factorial number of the tuple
    q = [0] * len(p)
    for i, v in enumerate(p):
        q[v] = i
    return rank(len(p), p, q)

def g(y, b):
    # find the matching permutation
    p = unrank(len(y), b, list(range(len(y))))
    # zip the permutation with the values
    z = list(zip(y, p))
    # sort by the order
    s = sorted(z, key=lambda y:y[1])
    # and return the values
    return [t[0] for t in s]
    
x = [3,56,43,96,23]
print(x)
b = f(x)
print(b)
y = sorted(x)
print(y)
o = g(y, b)
print(o)

输出：

[3, 56, 43, 96, 23]
108
[3, 23, 43, 56, 96]
[3, 56, 43, 96, 23]

原始答案

您可以使用itertools.permutations来解决这个问题，找出len(x)值的所有排列，并将索引返回到与元素排序顺序匹配的列表中。然后，您可以在g函数中反转该过程，找到与索引匹配的排列，并基于该值重新排序y：

import itertools

def f(x):
    # sort x including indexes
    s = sorted(enumerate(x), key=lambda y:y[1])
    # extract the indexes to a tuple
    i = tuple(t[0] for t in s)
    # find all the permutations of length len(x)
    p = list(itertools.permutations(range(len(x))))
    # find the sorted tuple in the list
    return p.index(i)

def g(y, b):
    # find all the permutations of length len(y)
    p = list(itertools.permutations(range(len(y))))
    # zip the permutation with the values
    z = list(zip(y, p[b]))
    # sort by the order
    s = sorted(z, key=lambda y:y[1])
    # and return the values
    return [t[0] for t in s]
    
x = [3,56,43,96,23]
print(x)
b = f(x)
print(b)
y = sorted(x)
print(y)
o = g(y, b)
print(o)

输出：

[3, 56, 43, 96, 23]
20
[3, 23, 43, 56, 96]
[3, 56, 43, 96, 23]

Answer 3

我不知道为什么其他人用排列来解决这个问题。这听起来像个问题。我还认为您指的是输出x[pos]，而不是输出x

#! /usr/bin/env python3
x = [ 3, 56, 43, 96, 23 ]

bits  = 0  ##  minimum number of bits to index list
while 2 **bits < len( x ):
    bits += 1

y  = []  ##  reverse nums
for ind, val in enumerate( x ):
    y .insert( 0, val )
y  = bytes( y )  ##  store as hex

def g( y, b ):  ##  count backwards, to find position in byte sequence
    return y[ len(y) -1 -b ]

binary_position = b'0'
print(  g( y, int( binary_position ) )  )

三,

---

编辑：

从返回值中减去1，这是一个基于0的列表。习惯于卢阿