Реверсирование (или упрощение) декартова произведения?

Question

Чтобы сделать вещи проще, но еще сложнее, я попытался реализовать концепцию «комбинированных/сжатых тегов», которые далее расширяются на несколько базовых форм тегов.

В этом случае метки состоят из (одного или более) "суб-тега (ов)", с разделителями точкой с запятой:

food:fruit:apple:sour/sweet 

drink:coffee/tea:hot/cold 

wall/bike:painted:red/blue 

Slashes указывают на "суб-тег" взаимозаменяемость. Поэтому переводчик переводит их на это:

food:fruit:apple:sour 
food:fruit:apple:sweet 

drink:coffee:hot 
drink:coffee:cold 
drink:tea:hot 
drink:tea:cold 

wall:painted:red 
wall:painted:blue 
bike:painted:red 
bike:painted:blue 

код используется (не идеально, но работает):

import itertools 

def slash_split_tag(tag): 
    if not '/' in tag: 
     return tag 
    subtags = tag.split(':') 
    pattern, v_pattern =(),() 
    for subtag in subtags: 
     if '/' in subtag: 
      pattern += (None,) 
      v_pattern += (tuple(subtag.split('/')),) 
     else: 
      pattern += (subtag,) 
    def merge_pattern_and_product(pattern, product): 
     ret = list(pattern) 
     for e in product: 
      ret[ret.index(None)] = e 
     return ret 
    CartesianProduct = tuple(itertools.product(*v_pattern)) # http://stackoverflow.com/a/170248 
    return [ ':'.join(merge_pattern_and_product(pattern, product)) for product in CartesianProduct ] 

#=============================================================================== 
# T E S T 
#=============================================================================== 

for tag in slash_split_tag('drink:coffee/tea:hot/cold'): 
    print tag 
print 
for tag in slash_split_tag('A1/A2:B1/B2/B3:C1/C2:D1/D2/D3/D4/EE'): 
    print tag 

Вопрос: Как я могу вернуть этот процесс? Мне нужно это для удобства чтения.

Answer 1

Вот простая, первый проход попытка такой функции:

def compress_list(alist): 
    """Compress a list of colon-separated strings into a more compact 
    representation. 
    """ 
    components = [ss.split(':') for ss in alist] 

    # Check that every string in the supplied list has the same number of tags 
    tag_counts = [len(cc) for cc in components] 
    if len(set(tag_counts)) != 1: 
     raise ValueError("Not all of the strings have the same number of tags") 

    # For each component, gather a list of all the applicable tags. The set 
    # at index k of tag_possibilities is all the possibilities for the 
    # kth tag 
    tag_possibilities = list() 
    for tag_idx in range(tag_counts[0]): 
     tag_possibilities.append(set(cc[tag_idx] for cc in components)) 

    # Now take the list of tags, and turn them into slash-separated strings 
    tag_possibilities_strs = ['/'.join(tt) for tt in tag_possibilities] 

    # Finally, stitch this together with colons 
    return ':'.join(tag_possibilities_strs) 

Надеется комментарии достаточно объяснить, как это работает. Несколько предостережений, однако:

• Он ничего толкового, такие, как избежать обратных косых черт, если он находит их в списке тегов не делать.

• Это не означает, что происходит более тонкое деление, или если он получает неполный список тегов. Рассмотрим следующий пример:

  fish:cheese:red 
  chips:cheese:red 
  fish:chalk:red 
  

  Он не осознает, что только cheese имеет как fish и chips, и вместо этого будет разрушаться это fish/chips:cheese/chalk:red.

• Порядок тегов в готовой строке случайный (или, по крайней мере, я не думаю, что это имеет какое-либо отношение к порядку строк в данном списке). Вы можете сортировать tt, прежде чем присоединяться к нему с помощью слэшей, если это важно.

Тестирование с помощью трех списков, приведенных в вопросе, кажется, работает, хотя, как я уже говорил, порядок может отличаться от начальных строк:

food:fruit:apple:sweet/sour 
drink:tea/coffee:hot/cold 
wall/bike:painted:blue/red