Поменять местами (или упростить) декартово произведение?

Question

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

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

food:fruit:apple:sour/sweet

drink:coffee/tea:hot/cold

wall/bike:painted:red/blue

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

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://stackru.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