代码之家 › 专栏 › 技术社区 › Siddharth Chabra

排列列表的有序排序

lexicographic permutation python

-2

Siddharth Chabra · 技术社区 · 6 年前

我正在尝试开发一种方法来查找下面列表中特定序列的有序秩。

a = list(sorted(itertools.combinations(range(0,5),3)))
b = list(sorted(itertools.permutations(range(0,5),3)))

a 表示的元素列表 combinatorial number system 所以等级的公式是非常直接的。

def magic_rank_1(perm_item,permutation_list_object): 
## permutation_list_object is actually b
    return list_object.index(perm_item)

def magic_rank_2(perm_item,permutation_list_object,combination_list_object):
## permutation_list_object is actually b and combination_list_object is actually a
    return combination_list_object.index(tuple(sorted(perm_item)))

所以基本上 magic_rank_2((0,1,2),b,a) = magic_rank_2((2,0,1),b,a)

听起来很简单。。但我有一些限制。

我需要魔术排名1和魔术排名2是纯数学没有使用任何排序函数,比较函数或搜索函数。我将得到的所有信息是需要确定其等级的元组和字母表的最后一个字母(在本例中为5)
- 当k=len(a)时,幻数秩2不必是介于0和k-1之间的数字,只要它是介于0和2^(上限((max_字母/2)+1))之间的唯一数字

我知道魔法排名可以用类似于 this 在我的每一个字母表中,都有一个字母的差异

最后是的,这应该是一个哈希函数的替代品,目前正在使用一个哈希函数,但我没有利用这个事实 幻数秩2((0,1,2),b,a)=幻数秩2((2,0,1),b,a) . 如果可以的话,它将大大减少我的存储空间需求,因为我的序列的长度实际上是5,所以如果我可以计算一个magic_rank_2的方法,我将我的存储需求减少到当前需求的1%

更新 -对于magic_rank_2,元组的元素之间不应该有比较操作,即没有排序、最小值、最大值等

这只会使算法的效率低于常规哈希

1 回复 | 直到 6 年前

1

0

jedwards 6 年前

下面两个函数将对组合和排列进行排序,给定一个单词和一个字母表(或者在您的例子中,是一个元组和一个列表)。

import itertools
import math

def rank_comb(word, alph, depth=0):
    if not word: return 0

    if depth == 0:
        word = list(word)
        alph = sorted(alph)

    pos = 0
    for (i,c) in enumerate(alph):
        if c == word[0]:
            # Recurse
            new_word = [x for x in word if x != c]
            new_alph = [x for x in alph if x > c]
            return pos + rank_comb(new_word, new_alph, depth+1)
        else:
            num = math.factorial(len(alph)-i-1)
            den = math.factorial(len(alph)-i-len(word)) * math.factorial(len(word)-1)
            pos += num // den


def rank_perm(word, alph, depth=0):
    if not word: return 0

    if depth == 0:
        word = list(word)
        alph = sorted(alph)

    pos = 0
    for c in alph:
        if c == word[0]:
            # Recurse
            new_word = [x for x in word if x != c]
            new_alph = [x for x in alph if x != c]
            return pos + rank_perm(new_word, new_alph, depth+1)
        else:
            num = math.factorial(len(alph)-1)
            den = math.factorial(len(alph)-len(word))
            pos += num // den


#== Validation =====================================================================
# Params
def get_alph(): return range(8)
r = 6

a = list(sorted(itertools.combinations(get_alph(), r)))
b = list(sorted(itertools.permutations(get_alph(), r)))

# Tests
PASS_COMB = True
PASS_PERM = True
for (i,x) in enumerate(a):
    j = rank_comb(x, get_alph())
    if i != j:
        PASS_COMB = False
        print("rank_comb() FAIL:", i, j)

for (i,x) in enumerate(b):
    j = rank_perm(x, get_alph())
    if i != j:
        PASS_PERM = False
        print("rank_perm() FAIL:", i, j)

print("rank_comb():", "PASS" if PASS_COMB else "FAIL")
print("rank_perm():", "PASS" if PASS_PERM else "FAIL")

new_alph 过滤方式不同。
num 和 den 是不同的。

更新:

rank_comb2 不需要对输入字(三元组)进行排序:

import itertools
import math

def rank_comb2(word, alph, depth=0):
    if not word: return 0

    if depth == 0:
        word = list(word)
        alph = sorted(alph)

    pos = 0
    for (i,c) in enumerate(alph):
        if c == min(word):
            # Recurse
            new_word = [x for x in word if x != c]
            new_alph = [x for x in alph if x > c]
            return pos + rank_comb2(new_word, new_alph, depth+1)
        else:
            num = math.factorial(len(alph)-i-1)
            den = math.factorial(len(alph)-i-len(word)) * math.factorial(len(word)-1)
            pos += num // den

r1 = rank_comb2([2,4,1], range(5))
r2 = rank_comb2([1,4,2], range(5))
r3 = rank_comb2([4,1,2], range(5))

print(r1, r2, r3)     # 7 7 7