Поиск разделителей/разделителей в списках строк

Question

Я пытаюсь найти разделители в файле, который может иметь или не иметь разделителей, а какие эти разделители - если они есть - также неизвестны.

До сих пор я написал следующий код в попытке «решить» это:

strings = [ 
    'cabhb2k4ack_sfdfd~ffrref_lk', 
    'iodja_24ed~092oi3jelk_fcjcad', 
    'lkn04432m_90osidjlknxc~o_pf' 
] 

# Process first line 
line1 = strings[0] 
separators = set() 
for sep in set(line1): 
    separators.add((sep, line1.count(sep))) 

# Process all the others 
for line in strings: 
    for sep,sepcount in separators.copy(): 
     if line.count(sep) != sepcount: separators.remove((sep,sepcount)) 

print separators 

Она возвращает набор: set([('_', 2), ('~', 1)]), который хорошо - но, к сожалению, не содержит порядок сепараторов в файл. Фактически, его даже не известно, был ли последовательный порядок для этих разделителей.

Правила для сепараторов просты:

1. Они должны происходить то же самое количество раз в каждой строке,
2. Они должны происходить в том же порядке, в каждой строке, не
3. Ни один из не- символы разделителей могут быть разделительными символами.

Обратите внимание, что в приведенном выше примере, «4» был исключен в качестве разделителя, как это происходит дважды в третьей строке по причине 1 и 3.

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

Answer 1

Я бы использовать Counter вместо .count, принять предложение skrrgwasme, чтобы использовать список, и использовать itertools.combinations, чтобы помочь перебрать все подмножества возможных разделителей:

from collections import Counter 
from itertools import combinations 

def subsets(elems): 
    for width in range(1, len(elems)+1): 
     for comb in combinations(elems, width): 
      yield comb 

def sep_order(string, chars): 
    chars = set(chars) 
    order = tuple(c for c in string if c in chars) 
    return order 

def find_viable_separators(strings): 
    counts = [Counter(s) for s in strings] 
    chars = {c for c in counts[0] 
      if all(count[c]==counts[0][c] for count in counts)} 
    for seps in subsets(chars): 
     orders = {sep_order(s, seps) for s in strings} 
     if len(orders) == 1: 
      yield seps, next(iter(orders)) 

, который дает мне

>>> 
... strings = [ 
...  'cabhb2k4ack_sfdfd~ffrref_lk', 
...  'iodja_24ed~092oi3jelk_fcjcad', 
...  'lkn04432m_90osidjlknxc~o_pf' 
... ] 
... 
... for seps, order in find_viable_separators(strings): 
...  print("possible separators:", seps, "with order:", order) 
...    
possible separators: ('~',) with order: ('~',) 
possible separators: ('_',) with order: ('_', '_') 
possible separators: ('~', '_') with order: ('_', '~', '_') 

Answer 2

Учитывая правило 1, каждый разделитель имеет ряд вхождений/строк, которые устойчивы от первой строки до последней из списка.

Я не считаю правило 3 очень хорошо выраженным. Я думаю, что это нужно понимать как «каждый символ, используемый как разделитель, не может быть найден среди других символов, которые считаются несепараторами в строке».

Таким образом, с учетом правил 1 и 3 каждый символ, число вхождений/линии которого изменяется даже в течение одного времени между двумя последовательными строками, не может быть разделителем.

Таким образом, принцип ниже код
· во-первых, чтобы создать список sep_n всех символов, присутствующих в первой линии, связанной с их числом вхождений в первой строке,
· а затем итерацию по список строк S и устранить каждый символ в списке sep_n, число входов которого не остается прежним.

S = [ 
    'cabhb2k4ack_sfdfd~ffrref_lk', 
    'iodja_24ed~092oi3jelk_fcjcad', 
    'lkn04432m_90osidjlknxc~o_pf', 
    'hgtr5v_8mgojnb5+87rt~lhiuhfj_n547' 
    ] 
# 1.They must occur the same number of times per line, 
line0 = S.pop(0) 
sep_n = [ (c,line0.count(c)) for c in line0] 
print(line0); print(sep_n,'\n') 

for line in S: 
    sep_n = [x for x in sep_n if line.count(x[0]) == x[1]] 
    print(line); print(sep_n,'\n') 

S.insert(0, line0) 

# 2.They must occur in the same order on each line, 
separators_in_order = [x[0] for x in sep_n] 
print('separators_in_order : ',separators_in_order) 
separators   = ''.join(set(separators_in_order)) 

for i,line in enumerate(S): 
    if [c for c in line if c in separators] != separators_in_order: 
     print(i,line) 

Если символы в строках имеют достаточно изменения их появления (кроме сепараторов), длина sep_n в моем коде быстро уменьшается список итеративно.

.

Инструкция sep_n = [ (c,line0.count(c)) for c in line0] несет ответственность за то, что окончательный заказ, полученный в separators_in_order, представляет собой порядок в первой строке списка S.

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

Вот почему вторичное управление должно быть выполнено после получения значения sep_n. Он должен повторить итерацию через список S.
Проблема заключается в том, что если «» каждый символ, число вхождений/строки которого меняется даже в течение одного времени между двумя последовательными строками, не может быть разделителем », однако может случиться, что символ без разделителя будет выглядеть строго такое же количество раз во всех строках, таким образом, без возможности обнаружить его как несепаратор на этой основе количества вхождений.
Но так как остается шанс, что такой символ не разделителя всегда будет находиться в одном и том же месте в списке символов с устойчивыми вхождениями, возможна вторичная проверка.

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

Результат

cabhb2k4ack_sfdfd~ffrref_lk 
[('c', 2), ('a', 2), ('b', 2), ('h', 1), ('b', 2), ('2', 1), ('k', 3), ('4', 1), ('a', 2), ('c', 2), ('k', 3), ('_', 2), ('s', 1), ('f', 5), ('d', 2), ('f', 5), ('d', 2), ('~', 1), ('f', 5), ('f', 5), ('r', 2), ('r', 2), ('e', 1), ('f', 5), ('_', 2), ('l', 1), ('k', 3)] 

iodja_24ed~092oi3jelk_fcjcad 
[('c', 2), ('a', 2), ('4', 1), ('a', 2), ('c', 2), ('_', 2), ('~', 1), ('_', 2), ('l', 1)] 

lkn04432m_90osidjlknxc~o_pf 
[('_', 2), ('~', 1), ('_', 2)] 

hgtr5v_8mgojnb5+87rt~lhiuhfj_n547 
[('_', 2), ('~', 1), ('_', 2)] 

separators_in_order : ['_', '~', '_'] 

И

S = [ 
    'cabhb2k4ack_sfd#fd~ffrref_lk', 
    'iodja_24ed~092oi#3jelk_fcjcad', 
    'lkn04432m_90osi#djlknxc~o_pf', 
    'h#gtr5v_8mgojnb5+87rt~lhiuhfj_n547' 
    ] 

результат

cabhb2k4ack_sfd#fd~ffrref_lk 
[('c', 2), ('a', 2), ('b', 2), ('h', 1), ('b', 2), ('2', 1), ('k', 3), ('4', 1), ('a', 2), ('c', 2), ('k', 3), ('_', 2), ('s', 1), ('f', 5), ('d', 2), ('#', 1), ('f', 5), ('d', 2), ('~', 1), ('f', 5), ('f', 5), ('r', 2), ('r', 2), ('e', 1), ('f', 5), ('_', 2), ('l', 1), ('k', 3)] 

iodja_24ed~092oi#3jelk_fcjcad 
[('c', 2), ('a', 2), ('4', 1), ('a', 2), ('c', 2), ('_', 2), ('#', 1), ('~', 1), ('_', 2), ('l', 1)] 

lkn04432m_90osi#djlknxc~o_pf 
[('_', 2), ('#', 1), ('~', 1), ('_', 2)] 

h#gtr5v_8mgojnb5+87rt~lhiuhfj_n547 
[('_', 2), ('#', 1), ('~', 1), ('_', 2)] 

separators_in_order : ['_', '#', '~', '_'] 
1 iodja_24ed~092oi#3jelk_fcjcad 
3 h#gtr5v_8mgojnb5+87rt~lhiuhfj_n547 

.
.

NB 1
Инструкция line0 = S.pop(0) делается
, чтобы предотвратить Распоряжения for line in S[1:]: прочь,
, потому что S[1:] создает новый список, который может быть тяжелым.

.

NB 2
Для того, чтобы избежать создания нового sep_n списка на каждом витке итерации в S,
лучше писать итерации следующим образом:

for line in S: 
    for x in sep_n: 
     if line.count(x[0]) == x[1]: 
      sep_n = [x for x in sep_n if line.count(x[0]) == x[1]] 
      break 
    print(line); print(sep_n,'\n')