Python: сравнение списка со строкой

Question

Я хочу знать, как сравнить строку со списком. Например, У меня есть строка 'abcdab' и список ['ab','bcd','da']. Есть ли способ сравнить все возможные комбинации списков с строкой и избежать совпадающих элементов. так что на выходе будет список кортежей как [('ab','da'),('bcd'),('bcd','ab'),('ab','ab'),('ab'),('da')].

Выход следует избегать таких сочетаний, как ('bcd', 'da') как символ «d» повторяется в кортеже в то время как он появляется только один раз в строке.

Как указано в ответе. Символы в строках и элементах списка не должны быть перегруппированы.

Один из способов, которым я пытался, состоял в том, чтобы разделить элементы строки на все возможные комбинации и сравнить. Который был 2^(n-1) n - количество символов. Это заняло много времени.

Я новичок в программировании на питоне. Спасибо заранее.

Answer 1

Эта маленькая рекурсивная функция должна сделать работу:

def matches(string, words, start=-1): 
    result= [] 
    for word in words: # for each word 
     pos= start 
     while True: 
      pos= string.find(word, pos+1) # find the next occurence of the word 
      if pos==-1: # if there are no more occurences, continue with the next word 
       break 

      if [word] not in result: # add the word to the result 
       result.append([word]) 

      # recursively scan the rest of the string 
      for match in matches(string, words, pos+len(word)-1): 
       match= [word]+match 
       if match not in result: 
        result.append(match) 
    return result 

выход:

>>> print matches('abcdab', ['ab','bcd','da']) 
[['ab'], ['ab', 'ab'], ['ab', 'da'], ['bcd'], ['bcd', 'ab'], ['da']] 

Answer 2

всех возможные комбинации списка в строку, и избежать перекрывающихся элементов

Являются комбинацией один или более полные детали в его точном, текущем порядке в списке, которые соответствуют шаблону или подшаблон строки ? Я считаю, что одно из требований состоит в том, чтобы не переупорядочить элементы в списке (ab не заменяет ba). Я считаю, что одним из требований является не перегруппировка символов в строке. Если подшаблон появляется дважды, то вы хотите, чтобы комбинации отображали две отдельные копии подшаблона сами по себе, а также список с обоими элементами подшаблона с другими подшаблонами, которые тоже совпадают. Вы хотите несколько перестановок совпадений.

Answer 3

Oops! Я как-то пропустил ответ Равинга. Ну что ж. :)

Вот еще одно рекурсивное решение.

#! /usr/bin/env python 

def find_matches(template, target, output, matches=None): 
    if matches is None: 
     matches = [] 

    for s in template: 
     newmatches = matches[:] 
     if s in target: 
      newmatches.append(s) 
      #Replace matched string with a null byte so it can't get re-matched 
      # and recurse to find more matches. 
      find_matches(template, target.replace(s, '\0', 1), output, newmatches) 
     else: 
      #No (more) matches found; save current matches 
      if newmatches: 
       output.append(tuple(newmatches)) 
      return 


def main(): 
    target = 'abcdab' 
    template = ['ab','bcd','da'] 

    print template 
    print target 

    output = [] 
    find_matches(template, target, output) 
    print output 


if __name__ == '__main__': 
    main() 

выход

['ab', 'bcd', 'da'] 
abcdab 
[('ab', 'ab'), ('ab',), ('bcd', 'ab'), ('bcd',), ('da', 'ab'), ('da',)]