Как назначить целочисленные значения для символов без добавления Asciis в Python - PullRequest
Новая
       11

Как назначить целочисленные значения для символов без добавления Asciis в Python

0 голосов
/ 21 марта 2012

Я не знаю, как эффективно задать этот вопрос, но мне нужно назначить целые значения символам таким образом, чтобы сложение символов не равнялось первому и второму, а вместо следующего числа в последовательность.

например:

если бы я использовал значения ascii для установки a-z на 1-26, то если бы у меня была строка ab, сумма была бы 3 Тем не менее, я хочу, чтобы ab было назначено 27, ac = 28, ad = 29 и т. Д.

так a = 1 но az = 51 (а не 27, если я просто сделал a + z)

Я не уверен, повлияет ли это на решение, но одно из условий состоит в том, что буквы в строке должны быть в алфавитном порядке, чтобы строка могла быть "abc", но не могла быть "cat"

Спасибо!

1 Ответ

1 голос
/ 21 марта 2012

Можно вычислить индекс запрошенным способом, не создавая список всех возможных строк, но это немного усложняет это. Вот реализация эффективного метода для этого: 

import itertools
import string

letters = string.ascii_lowercase

def _reference(max_len=4):
    """A reference implementation of the desired index operation."""
    a = []
    for k in range(max_len + 1):
        for comb in itertools.combinations(letters, k):
            a.append("".join(comb))
    return a.index

def choose(n, k):
    """The binomial coefficient "n choose k"."""
    if k < 0:
        return 0
    result = 1
    for i in range(k):
        result *= n - i
        result //= i + 1
    return result

def index(s):
    """An efficient implementation of the index operation."""
    n = len(s)
    choices = len(letters)
    result = 0
    for i, c in enumerate(s):
        new_choices = len(letters) - letters.index(c)
        result += choose(choices, n - i) - choose(new_choices, n - i)
        choices = new_choices - 1
    for i in range(n):
        result += choose(len(letters), i)
    return result

test_strings =[
    "a", "j", "ab", "az", "jw", "yz", "abc", "abhors", "almost",
    "begins", "bijoux", "biopsy", "chimps", "chinos", "chintz"]
ref_index = _reference(max(map(len, test_strings)))
for s in test_strings:
    print "{0:8}{1:8}{2:8}".format(s, index(s), ref_index(s))

Этот сценарий сравнивает выходные данные эффективной функции с реализацией грубой силы, и выходные данные равны 

a              1       1
j             10      10
ab            27      27
az            51      51
jw           228     228
yz           351     351
abc          352     352
abhors     91047   91047
almost    133902  133902
begins    154337  154337
bijoux    171130  171130
biopsy    172655  172655
chimps    201678  201678
chinos    201734  201734
chintz    201781  201781
...