Решать смешанные головоломки слова с питоном?

Question

У меня есть интересная головоломка для вас:

Вам будут даны две вещи:

1. Слово, содержащее список английских слов, составленных вместе, например:

   word = "iamtiredareyou"
   

2. Возможные поднаборы:

   subsets = [
      'i', 'a', 'am', 'amt', 'm', 't', 'ti', 'tire', 'tired', 'i', 
      'ire', 'r', 're', 'red', 'redare', 'e', 'd', 'da', 'dar', 'dare', 
      'a', 'ar', 'are', 'r', 're', 'e', 'ey', 'y', 'yo', 'you', 'o', 'u'
   ]
   

Вызовы:

Уровень-1: Мне нужно прагматично найти членов в subsets, которые вместе в заказе составят "iamtiredareyou", т.е. ['i', 'am', 'tired', 'are', 'you']

Level-2: Исходная строка может состоять из некоторой дополнительнойсимволы в последовательности, которых нет в подмножестве.например, "iamtired12aareyou".Значение subset такое же, как указано выше, решение должно автоматически включить это подмножество в нужное место в массиве результатов.то есть ['i', 'am', 'tired', '12a', 'are', 'you']

Как я могу это сделать?

Answer 1

Обычно рекурсивный алгоритм подходит. Начните с проверки всех подмножеств по отношению к началу данного слова, если найдено - добавьте (добавьте) к найденным значениям и выполните повторение с оставшейся частью слова и текущими найденными значениями. Или, если это конец строки, выведите найденные значения.

что-то в этом роде:

all=[]
def frec(word, values=[]):
    gobal all
    if word == "":  # got result.
        all+=[values]
    for s in subsets:
        if word.startswith(s):
            frec(word[len(s):], values+[s])

frec(word)

обратите внимание, что существует множество возможных решений, поскольку подмножества содержат много односимвольных строк. Возможно, вы захотите найти кратчайшие результаты. (13146 решений ... используйте «all.sort (cmp = lambda x, y: cmp (len (x), len (y)))» для получения кратчайшего)

Для уровня 2 - вам нужен еще один цикл, если не найдено подмножества, которое добавляет все больше и больше символов к следующему значению (и возвращается в него) до тех пор, пока не будет найдено совпадение.

all=[]
def frec(word, values=[]):
    global all
    if word == "":  # got result.
        all+=[values]
        return true
    match = False
    for s in subsets:
        if word.startswith(s):
            match = True
            frec(word[len(s):], values+[s])       
    if not match:                        
        return frec(word[1:], values+[word[0]])
frec(word)

Однако это не пытается объединить не подмножественные значения в одну строку.

Answer 2

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

Answer 3

Извините за отсутствие фрагмента кода, но я хотел бы предложить динамическое программирование. Атакуйте уровень 1 и уровень 2 одновременно, назначив цену за каждое слово и добавив все отдельные символы, которые не представлены в качестве односимвольных дорогостоящих слов. Задача состоит в том, чтобы найти способ разбить последовательность на слова, что дает наименьшую общую стоимость.

Работайте слева направо по последовательности, в каждой точке вырабатывая и сохраняя решение с наименьшими затратами, включая текущую точку и длину слова, которое завершает это решение. Чтобы найти ответ для следующего пункта последовательности, рассмотрите все известные слова, которые являются суффиксами последовательности. Для каждого такого слова рассчитайте наилучшую общую стоимость, добавив стоимость этого слова к (уже выработанной) стоимости наилучшего решения, заканчивающегося непосредственно перед началом этого слова. Обратите внимание на наименьшую общую стоимость и длину слова, которое его производит.

Как только у вас будет лучшая стоимость для всей последовательности, используйте длину последнего слова в этой последовательности, чтобы выяснить, каково последнее слово, а затем отступите на это количество символов, чтобы проверить ответ, выработанный в этой точке. и получить слово, предшествующее последнему слову, и т. д.

Answer 4

Для задания уровня 1 вы можете сделать это рекурсивно .Возможно, не самое эффективное решение, но самое простое:

word = "iamtiredareyou"
subsets = ['i', 'a', 'am', 'amt', 'm', 't', 'ti', 'tire', 'tired', 'i', 'ire', 'r', 're', 'red', 'redare', 'e', 'd', 'da', 'dar', 'dare', 'a', 'ar', 'are', 'r', 're', 'e', 'ey', 'y', 'yo', 'you', 'o', 'u']

def findsubset():
    global word

    for subset in subsets:
        if word.startswith(subset):
            setlist.append(subset)
            word = word[len(subset):]

            if word == "":
                print setlist
            else:
                findsubset()

            word = subset + word
            setlist.pop()

# Remove duplicate entries by making a set
subsets = set(subsets)
setlist = []
findsubset()

Ваш список подмножеств содержит дубликаты - например, 'a' появляется дважды - поэтому мой код делает его set чтобы удалить дубликаты перед поиском результатов.

Answer 5

Вот рекурсивное, неэффективное Java-решение:

private static void findSolutions(Set<String> fragments, String target, HashSet<String> solution, Collection<Set<String>> solutions) {
    if (target.isEmpty()) {
        solutions.add(solution);
        return;
    }

    for (String frag : fragments) {
        if (target.startsWith(frag)) {
            HashSet<String> solution2 = new HashSet<String>(solution);
            solution2.add(frag);
            findSolutions(fragments, target.substring(frag.length()), solution2, solutions);
        }
    }       
}

public static Collection<Set<String>> findSolutions(Set<String> fragments, String target) {
    HashSet<String> solution = new HashSet<String>();
    Collection<Set<String>> solutions = new ArrayList<Set<String>>();
    findSolutions(fragments, target, solution, solutions);
    return solutions;
}

Answer 6

Разве это не то же самое, что найти перестановки, но с некоторыми условиями? Подобно тому, как вы запускаете алгоритм перестановки (рекурсивный), вы проверяете, соответствует ли уже имеющаяся у вас строка первым X вашим символам, чтобы найти слово, если да, вы продолжаете рекурсию, пока не найдете слово целиком, в противном случае вы вернетесь назад.

Уровень 2 немного глуп, если вы спросите меня, потому что тогда вы могли бы написать что-нибудь как «слово, которое нужно найти», но в основном это было бы как уровень 1, за исключением того, что если вы не можете найти подстроку в свой список вы просто добавляете его (буква за буквой, т.е. у вас есть «love» и список ['l', 'e'], вы соответствуете 'l', но вам не хватает 'o', поэтому вы добавляете его и проверяете, есть ли Ваши слова в списке начинаются с буквы «v» и соответствуют вашему слову, которое нужно найти, они не совпадают, поэтому вы добавляете «v» в «o» и т. д.).

И если вам скучно, вы можете реализовать генетический алгоритм, это действительно весело, но не очень эффективно.