PYTHON - заданное начальное слово, последовательность букв которого позволит вам максимизировать количество допустимых слов, которые могут быть написаны - PullRequest
Новая
       6

PYTHON - заданное начальное слово, последовательность букв которого позволит вам максимизировать количество допустимых слов, которые могут быть написаны

3 голосов
/ 12 августа 2011

Редактировать: Новый вопрос. Учитывая, что я подозреваю, что этот вопрос сложнее, чем я первоначально думал - потенциально NP-сложный, у меня другой вопрос: какой полезный алгоритм может приблизиться к максимизации количества используемых букв?

Меня вдохновило написать программу на основе карточной игры Scrabble Slam! Однако я новичок в алгоритмах и не могу придумать эффективный способ решения этой проблемы:

Вы начинаете со строки, содержащей действительное английское слово из 4 букв. Вы можете поместить одну букву в это слово за раз, так что, поместив эту букву, вы формируете новое словарное слово. Буквы, которые у вас есть, равны буквам в алфавите.

Например, если начальное слово «корзина», это может быть допустимая последовательность ходов:

песок -> нормальный -> синус -> линия -> линии -> контакты -> плавники и т. Д.

Цель состоит в том, чтобы максимально увеличить количество слов в последовательности, используя как можно больше букв алфавита (без использования буквы более одного раза).

Мой алгоритм не может найти самую длинную последовательность, только предположение о том, какой может быть самая длинная последовательность.

Во-первых, он получает список всех слов, которые можно сформировать, изменив одну букву начального слова. Этот список называется «соседний список». Затем он просматривает все слова в соседнем списке и находит, какие из этих слов имеют наиболее смежные слова. Независимо от того, какое слово имеет наибольшее количество смежных слов, оно решает превратить начальное слово в * 1015

Например, слово "здравый смысл" может быть превращено в 28 других слов, слово "синус" может быть превращено в 27 других слов, строка слова может быть превращена в 30 других слов - каждый из этих вариантов был сделан для максимизации вероятность того, что все больше и больше слов могут быть написаны.

Как лучше всего решить эту проблему? Какая структура данных будет оптимальной? Как я могу улучшить свой код, чтобы сделать его более эффективным и менее многословным? 

##Returns a list of all adjacent words.  Lists contain tuples of the adjacent word and the letter that
##makes the difference between those two words.

def adjacentWords(userWord):
    adjacentList, exactMatches, wrongMatches = list(), list(), str()
    for dictWords in allWords:
        for a,b in zip(userWord, dictWords):
            if a==b: exactMatches.append(a)
            else: wrongMatches = b
        if len(exactMatches) == 3:
            adjacentList.append((dictWords, wrongMatches))
        exactMatches, wrongMatches = list(), list()
    return adjacentList
    #return [dictWords for dictWords in allWords if len([0 for a,b in zip(userWord, dictWords) if a==b]) == 3]


def adjacentLength(content):
    return (len(adjacentWords(content[0])), content[0], content[1])

#Find a word that can be turned into the most other words by changing one letter
def maxLength(adjacentList, startingLetters):
    return max(adjacentLength(content) for content in adjacentList if content[1] in startingLetters)

def main():
    startingWord = "sand"
    startingLetters = "a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z".replace(" ", "").split(',')

    existingWords = list()
    while True:
        adjacentList = adjacentWords(startingWord)
        letterChoice = maxLength(adjacentList, startingLetters)
        if letterChoice[1] not in existingWords:
            print "Going to use letter: "+ str(letterChoice[2]) + " to spell the word "+ str(letterChoice[1]) + " with "+ str(letterChoice[0]) + " possibilities."
            existingWords.append(letterChoice[1])
            startingLetters.remove(str(letterChoice[2]))
            startingWord = letterChoice[1]


main()

Ответы [ 2 ]

3 голосов
/ 12 августа 2011

@ Parseltongue Возможно, вы обнаружите, что, хотя есть оптимальное решение для данной задачи, но не существует известного способа ее решения оптимальным способом.Эта задача является одной из проблем NP-класса .

Примите во внимание следующее: 

sand --> [?]and

. На этом этапе вам нужно пройти через ВСЕ возможные комбинации [?]and, чтобы найти слова, которые соответствуют критериям.В худшем случае, без эвристики, это 26 итераций.

sand --> band, hand, land, wand

Теперь, возьмите каждое найденное слово и итерируйте вторую букву и т. Д.
Вы можете видеть, что количество итераций, которое вам нужно сделать, растет в геометрической прогрессии.

Это в некотором роде очень похоже на проблему шахмат.Независимо от того, насколько мощный ваш компьютер, он не может предсказать все возможные шаги, потому что есть слишком много комбинаций.

0 голосов
/ 12 августа 2011

Я и мой друг фактически разработали аналогичную программу (хотя и на Java) в лаборатории для курса по структурам данных и алгоритмам.Задача состояла в том, чтобы создать самую короткую цепочку слов из одного слова в другое.

Мы создали дерево всех доступных слов, где один узел был связан с другим, если они отличались только одной буквой.Использование некоторой хеш-таблицы, такой как словарь, требуется для скорости.Мы фактически удалили одну букву из слов, которые мы использовали в качестве ключей, тем самым воспользовавшись тем фактом, что соединенные слова имели одинаковый хеш, но это трудно объяснить без кода.мы просто использовали поиск в ширину.Однако найти кратчайший путь в графе легче, чем самый длинный.См. проблема самого длинного пути для получения более подробной информации.

Чтобы решить основную проблему, вы можете просто перебрать все слова.Однако, если важна скорость, часто бывает проще найти хороший специальный эвристический алгоритм.

...