要素の部分文字列に基づいてリストを減らす

Question

リストに既に含まれている部分文字列に基づいて特定のリストを減らす最も効率的な方法を探しています。 'ABCD' および 'QRS' の両方が、そのリスト内の他の要素の最小のサブストリングであるため

mylist = ['abcd','qrs'] 

：

mylist = ['abcd','abcde','abcdef','qrs','qrst','qrstu'] 

例えば

にまで低減されるであろう。私は約30行のコードでこれを行うことができましたが、そこには狡猾な1ライナーがあると思われます。

Answer 1

これは（私は仮定それほど効率的ではなく）動作しているようだ

def reduce_prefixes(strings): 
    sorted_strings = sorted(strings) 
    return [element 
      for index, element in enumerate(sorted_strings) 
      if all(not previous.startswith(element) and 
        not element.startswith(previous) 
        for previous in sorted_strings[:index])] 

テスト：

>>>reduce_prefixes(['abcd', 'abcde', 'abcdef', 
        'qrs', 'qrst', 'qrstu']) 
['abcd', 'qrs'] 
>>>reduce_prefixes(['abcd', 'abcde', 'abcdef', 
        'qrs', 'qrst', 'qrstu', 
        'gabcd', 'gab', 'ab']) 
['ab', 'gab', 'qrs'] 

Answer 2

1つの解決方法は、すべての文字列を繰り返し、その関数を再帰的に適用します。

def reduce_substrings(strings): 
    return list(_reduce_substrings(map(iter, strings))) 

def _reduce_substrings(strings): 
    # A dictionary of characters to a list of strings that begin with that character 
    nexts = {} 
    for string in strings: 
     try: 
      nexts.setdefault(next(string), []).append(string) 
     except StopIteration: 
      # Reached the end of this string. It is the only shortest substring. 
      yield '' 
      return 
    for next_char, next_strings in nexts.items(): 
     for next_substrings in _reduce_substrings(next_strings): 
      yield next_char + next_substrings 

これは文字に基づいて辞書に分割し、それが辞書に別のリストに分割するもののうち最も短い部分文字列を検索しようとします。

もちろん、この関数の再帰的性質のため、効率的に1ライナーを実行することはできません。

Answer 3

この方法を試してください。

import re 
mylist = ['abcd','abcde','abcdef','qrs','qrst','qrstu'] 
new_list=[] 
for i in mylist: 
    if re.match("^abcd$",i): 
     new_list.append(i) 
    elif re.match("^qrs$",i): 
     new_list.append(i) 
print(new_list) 
#['abcd', 'qrs'] 

Answer 4

おそらくない最も効率的、少なくとも短く：

mylist = ['abcd','abcde','abcdef','qrs','qrst','qrstu'] 

outlist = [] 
for l in mylist: 
    if any(o.startswith(l) for o in outlist): 
     # l is a prefix of some elements in outlist, so it replaces them 
     outlist = [ o for o in outlist if not o.startswith(l) ] + [ l ] 
    if not any(l.startswith(o) for o in outlist): 
     # l has no prefix in outlist yet, so it becomes a prefix candidate 
     outlist.append(l) 

print(outlist)