词排名部分完成

Question

我不太确定如何在这些限制条件下解决这个问题。

简化的问题描述：

把“单词”看作是任何由大写字母A-Z组成的序列（不仅限于“字典单词”）。
考虑一个单词中所有字符的排列组合，并按字母顺序排序。
找出原始单词在这个列表中的位置。
不要生成所有可能的单词排列，因为这样会超出时间和内存的限制。
限制条件：单词长度小于等于25个字符；内存限制为1GB，任何答案都应该适合64位整数。

原始问题描述：

把“单词”看作是任何由大写字母A-Z组成的序列（不仅限于“字典单词”）。对于任何至少有两个不同字母的单词，都会有其他由相同字母但顺序不同的单词（例如，STATIONARILY和ANTIROYALIST，它们都是字典中的单词；在这里，“AAIILNORSTTY”也是由这两个单词的字母组成的“单词”）。我们可以根据单词在按字母顺序排列的所有由相同字母组成的单词列表中的位置，为每个单词分配一个编号。一个方法是生成整个单词列表，然后找到所需的单词，但如果单词很长，这样会很慢。编写一个程序，接受一个单词作为命令行参数，并将其编号打印到标准输出。不要使用上述生成整个列表的方法。你的程序应该能够接受任何长度不超过25个字母的单词（可能有些字母重复），并且使用的内存不超过1GB，运行时间不超过500毫秒。我们检查的任何答案都应该适合64位整数。

示例单词及其排名：

ABAB = 2 
AAAB = 1 
BAAA = 4 
QUESTION = 24572 
BOOKKEEPER = 10743

示例：

AAAB - 1
AABA - 2
ABAA - 3
BAAA - 4

AABB - 1
ABAB - 2
ABBA - 3
BAAB - 4
BABA - 5
BBAA - 6

我想出的解决方案似乎只是部分解决。

假设我有一个单词 JACBZPUC。我对这个单词进行排序，得到 ABCCJPUZ。这个单词在排名中应该是第一名。从 ABCCJPUZ 到以 J 开头的第一个字母的单词之间，我想找出这两个单词之间的排列数量。

例如：

for `JACBZPUC`

sorted --> `ABCCJPUZ`

permutations that start with A -> 8!/2!
permutations that start with B -> 8!/2!
permutations that start with C -> 8!/2!
              Add the 3 values -> 60480

另一个C被忽略，因为它的排列与之前的C是重复的（重复项）

此时我已经得到了从 ABCCJPUZ 到以J开头的单词之前的单词的排名。

ABCCJPUZ   rank 1       
...
...         60480 values
...
*HERE*     
JABCCJPUZ  rank 60481      LOCATION A
...
...         
...
JACBZPUC   rank ???        LOCATION B

我不确定如何获取位置A和B之间的值：

这是我用来找到60480个值的代码。

def perm(word):
    return len(set(itertools.permutations(word)))

def swap(word, i, j):
    word = list(word)
    word[i], word[j] = word[j], word[i]
    print word
    return ''.join(word)

def compute(word):
    if ''.join(sorted(word)) == word:
        return 1
    total = 0
    sortedWord = ''.join(sorted(word))
    beforeFirstCharacterSet = set(sortedWord[:sortedWord.index(word[0])])
    print beforeFirstCharacterSet
    for i in beforeFirstCharacterSet:
        total += perm(swap(sortedWord,0,sortedWord.index(i)))
    return total

这是我在网上找到的解决这个问题的方法。

考虑一个n字母的单词 { x1, x2, ... , xn }。我的解决方案基于这样一个想法：单词的编号将是两个数量的总和：

以字母表中比x1更小的字母开头的组合数量，以及

我们在以x1开头的排列中走了多远。

关键在于第二个数量恰好是单词 { x2, ... , xn } 的编号。这提示我们可以使用递归实现。

获取第一个数量有点复杂：

让 uniqLowers = { u1, u2, ... , um } = 所有比x1小的唯一字母

对于每个uj，计算以uj开头的排列数量。

把所有这些加起来。

我觉得我完成了第一步，但第二步不太确定如何完成。

这是Haskell的解决方案……我不懂Haskell =/，我正在尝试用Python编写这个程序。

https://github.com/david-crespo/WordNum/blob/master/comb.hs

字符串处理递归排序算法组合数学内存限制 64位整数字母排列词排名

词排名部分完成

3 个回答

撰写回答