个人中心
gpt4 book ai didi

python - 单词排名部分完成

转载 作者：太空狗 更新时间：2023-10-30 03:01:52 24 4
gpt4 key购买 nike

<分区>

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

简化的问题表述:

  1. “单词”为大写字母 A-Z 的任意序列(不仅限于“字典单词”)。
  2. 考虑一个单词中所有字符的排列列表，按字典顺序排序
  3. 在这样的列表中找到原始单词的位置
  4. 不要生成单词的所有可能排列，因为它不符合时间内存限制。
  5. 约束:字长<= 25个字符；内存限制 1Gb，任何答案都应该适合 64 位整数

原始问题表述:

Consider a "word" as any sequence of capital letters A-Z (not limited to just "dictionary words"). For any word with at least two different letters, there are other words composed of the same letters but in a different order (for instance, STATIONARILY/ANTIROYALIST, which happen to both be dictionary words; for our purposes "AAIILNORSTTY" is also a "word" composed of the same letters as these two). We can then assign a number to every word, based on where it falls in an alphabetically sorted list of all words made up of the same set of letters. One way to do this would be to generate the entire list of words and find the desired one, but this would be slow if the word is long. Write a program which takes a word as a command line argument and prints to standard output its number. Do not use the method above of generating the entire list. Your program should be able to accept any word 25 letters or less in length (possibly with some letters repeated), and should use no more than 1 GB of memory and take no more than 500 milliseconds to run. Any answer we check will fit in a 64-bit integer.

示例词及其排名:

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 这应该是单词排名中的第 1 位。从 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

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

Consider the n-letter word { x1, x2, ... , xn }. My solution is based on the idea that the word number will be the sum of two quantities:

  1. The number of combinations starting with letters lower in the alphabet than x1, and
  2. how far we are into the the arrangements that start with x1.

The trick is that the second quantity happens to be the word number of the word { x2, ... , xn }. This suggests a recursive implementation.

Getting the first quantity is a little complicated:

  1. Let uniqLowers = { u1, u2, ... , um } = all the unique letters lower than x1
  2. For each uj, count the number of permutations starting with uj.
  3. Add all those up.

我想我完成了第 1 步但没有完成第 2 步。我不确定如何完成这部分

这是 Haskell 的解决方案...我不知道 Haskell =/我正在尝试用 Python 编写这个程序

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

24 4 0
文章推荐： python - 如何在 Python PIL 中为绘制文本设置适当的线宽？
文章推荐： python - 如何在不迭代的情况下读取行
文章推荐： python - 使用条件 python 查找最小值
文章推荐： python - Python 3 Miniconda 环境上的 wxPython
太空狗
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com