单词排名效率 [英] Word ranking efficiency

问题描述

我不确定如何在限制范围内解决此问题.

I am not sure how to solve this problem within the constraints.

将单词"视为大写字母A-Z的任意序列(不仅限于词典单词").对于具有至少两个不同字母的任何单词，还有其他单词由相同字母组成，但顺序不同(例如，STATIONARILY/ANTIROYALIST，它们恰好都是字典单词；就我们的目的而言，"AAIILNORSTTY"也是字"由与这两个字母相同的字母组成).然后，我们可以根据每个单词的编号顺序，为每个单词分配一个数字，该列表按字母顺序排列，列出由同一组字母组成的所有单词.一种方法是生成整个单词列表并找到所需的单词列表，但是如果单词很长，这将很慢.编写一个程序，该程序将单词作为命令行参数，并将其编号打印到标准输出中.不要使用上面的方法来生成整个列表.您的程序应能够接受长度不超过25个字母的任何单词(可能重复一些字母)，并且使用的内存不得超过1 GB，并且运行的时间不得超过500毫秒.我们检查的所有答案都将适合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

我考虑过使用二进制搜索来搜索单词和所有可能的单词，这些单词都由字符组成(1-permutation(word))，但是我认为这会花费很长时间. O(logN)可能太慢.

I thought about using a binary search for a word and all the possible words built from the characters (1 - permutation(word)) but I think that would take too long. O(logN) might be too slow.

我找到了这个解决方案，但是我有点困惑，需要一些帮助来理解它:

I found this solution but I am a bit confused and need a bit of help understanding it:

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:

The number of combinations starting with letters lower in the alphabet than x1, and
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:

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

推荐答案

解决方案说答案由两个数字组成.请看下面的图片，其中描述了可以由单词QUESTION制成的单词:

The solutions says that the answer consists of two numbers. Look at the following picture describing the words that can be made from the word QUESTION:

EIONQSTU (first word lexographically, rank 1)
...
...
... (first word before Q, rank A)
QEIONSTU 
....
....
QUESTION (our given word, rank x)
...

这个短语我们进入以x1开头的安排有多远"，是数量(xA)，称为B.事情是B恰好等于"UESTION"的单词等级，这是我们的第一个字母的原始单词被截断.这是在问相同的问题，但有一部分输入内容，建议使用递归解决方案.

This phrase "how far we are into the the arrangements that start with x1", is the quantity (x-A), call it B. The thing is B is exactly equal to the word rank of "UESTION", which is our original word with the first letter cut off. This is asking the same question but with a subset of our input, suggesting a recursive solution.

然后剩下的便是找到A，这意味着要找到以Q之前的单词开头的单词的排列数量.因此，A =以{E，I，O，N}开头的单词的数量

It then remains to find A, this says to find the number of permutations of words beginning with words that come before Q. So A = number of words beginning with {E, I, O, N}

这篇关于单词排名效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！