Я написал код для решения следующей проблемы, однако в последних двух тестах он не работает. Моя логика, используемая для решения проблемы, кажется разумной, и даже после того, как коллега рассмотрел ее, мы оба не можем понять, почему она будет работать для первых 8 тестовых случаев, но не для двух последних (которые были сгенерированы случайным образом).
Проблема:
Если задана строка, вернуть позицию введенной строки в
отсортированный по алфавиту список всех возможных перестановок
символы в этой строке. Например, перестановки ABAB являются
[AABB, ABAB, ABBA, BAAB, BABA, BBAA], где позиция ABAB в этом
список 2.
Логика, которую я использовал для решения проблемы:
Для больших входных данных невозможно (неэффективно) сформировать список перестановок, поэтому смысл состоит в том, чтобы найти позицию без генерации алфавитного списка. Это можно сделать, найдя частоту символов. В приведенном выше примере первый символ в ABAB - это A, поэтому до = 0 и после = .5, а между = 6, поэтому вы уменьшаете max на .5 * 6, что равно 3, для minn из 1 и maxx из 3 , чтобы оставить только [AABB, ABAB, ABBA], химическая завивка с A в качестве первого символа! Тогда оставленные символы - БАБ. minn = 1 и maxx = 3, а между = 3. Таким образом, для B значение before было бы .33, а после будет 0, поэтому увеличьте minn на 3 * .33 для minn из 2 и maxx из 3, что равно [ABAB , ABBA] перми, в которых первые два символа обозначены буквой AB! Продолжайте делать это для каждого символа, и он найдет ввод в списке.
Мой код:
## Imports
import operator
from collections import Counter
from math import factorial
from functools import reduce
## Main function, returns list position
def listPosition(word):
#turns string into list of numbers, A being 1, B being 2, and so on
val = [ord(char) - 96 for char in word.lower()]
#the result has to be between 1 and the number of permutations
minn = 1
maxx = npermutations(word)
#so we just increase the min and decrease the max based on the sum of freq
#of the characters less than and greater than each character
for indx in range(len(word)):
between = (maxx+1-minn)
before,after = sumfreq(val[indx:],val[indx])
minn = minn + int(round((between * before),0))
maxx = maxx - int(between * after)
return maxx #or minn, doesn't matter. they're equal at this point
## returns the number of permutations for the string (this works)
def npermutations(word):
num = factorial(len(word))
mults = Counter(word).values()
den = reduce(operator.mul, (factorial(v) for v in mults), 1)
return int(num / den)
## returns frequency as a percent for the character in the list of chars
def frequency(val,value):
f = [val.count(i)/len(val) for i in val]
indx = val.index(value)
return f[indx]
#returns sum of frequencies for all chars < (before) and > (after) the said char
def sumfreq(val,value):
before = [frequency(val,i) for i in [i for i in set(val) if i < value]]
after = [frequency(val,i) for i in [i for i in set(val) if i > value]]
return sum(before),sum(after)
tests= ['A','ABAB','AAAB','BAAA','QUESTION','BOOKKEEPER','ABCABC','IMMUNOELECTROPHORETICALLY','ERATXOVFEXRCVW','GIZVEMHQWRLTBGESTZAHMHFBL']
print(listPosition(tests[0]),"should equal 1")
print(listPosition(tests[1]),"should equal 2")
print(listPosition(tests[2]),"should equal 1")
print(listPosition(tests[3]),"should equal 4")
print(listPosition(tests[4]),"should equal 24572")
print(listPosition(tests[5]),"should equal 10743")
print(listPosition(tests[6]),"should equal 13")
print(listPosition(tests[7]),"should equal 718393983731145698173")
print(listPosition(tests[8]),"should equal 1083087583") #off by one digit?
print(listPosition(tests[9]),"should equal 5587060423395426613071") #off by a lot?