Partial completion of word ranking

Question

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

Abbreviated wording of the problem:

• A "word" is like any sequence of capital letters AZ (not limited only to dictionary words).
• Consider a list of permutations of all characters in a word, sorted lexicographically
• Find the position of the original word in such a list
• Do not generate all possible permutations of the word, since it will not correspond to the limitations of temporary memory.
• Limitations: word length <= 25 characters; 1Gb memory limit, any response must match a 64-bit integer

Original wording of the problem:

Consider a “word” like any sequence of capital letters AZ (not limited to “dictionary words”). For any word with at least two different letters, there are other words consisting of the same letters, but in a different order (for example, STATIONARILY / ANTIROYALIST, which, like words, are dictionary words, for our purposes "AAIILNORSTTY" also is a "word" consisting of the same letters as these two). Then we can assign a number to each word, based on where it falls into an alphabetically sorted list of all words made up of the same set of letters. One way to do this is to generate an entire list of words and find the right one, but it will be slow if the word is long. Write a programwhich takes a word as a command line argument and prints its number to standard output. Do not use the method above to create an entire list. Your program should be able to accept any word 25 or less in length (possibly with the repetition of several letters) and use no more than 1 GB of memory and 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 rank. 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.
• .

, 1, 2. ,

Haskell... Haskell =/ Python

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

Answer 1

. :

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

. 8!/2!= 20160 JACBZPUC, 60480. , . :

permutations that start with A:   7! / 2! ==   2520
permutations that start with B:   7! / 2! ==   2520
permutations that start with C:   7! / 1! ==   5040
                                              -----
                                              10080

2! , C, ; C.

Python:

def fact(n):
    """factorial of n, n!"""

    f = 1

    while n > 1:
         f *= n
         n -= 1

    return f



def rrank(s):
    """Back-end to rank for 0-based rank of a list permutation"""

    # trivial case
    if len(s) < 2: return 0

    order = s[:]
    order.sort()

    denom = 1

    # account for multiple occurrences of letters
    for i, c in enumerate(order):
        n = 1
        while i + n < len(order) and order[i + n] == c:
            n += 1

        denom *= n

    # starting letters alphabetically before current letter
    pos = order.index(s[0])

    #recurse to list without its head
    return fact(len(s) - 1) * pos / denom + rrank(s[1:])



def rank(s):
    """Determine 1-based rank of string permutation"""

    return rrank(list(s)) + 1



strings = [
    "ABC", "CBA", 
    "ABCD", "BADC", "DCBA", "DCAB", "FRED", 
    "QUESTION", "BOOKKEEPER", "JACBZPUC",
    "AAAB", "AABA", "ABAA", "BAAA"
]

for s in strings:
    print s, rank(s)

Answer 2

- - , :

, "Location A", "Location B", ACBZPUC . , , , .

Answer 3

JABCCPUZ, , JACBZPUC, , J. JACBZPUC JABCCPUZ, J , , , .

Repeat this process for enough time, and you will have a word containing one character, C. The position of a word with one character is always 1, so you can then sum it up and all the previous relative positions for an absolute position.