Как объединить вложенные кортежи

Question

У меня есть набор вложенных кортежей:

('id', ('name', ('name_float_fml',)), ('user', ('email',)), ('user', ('last_login',)))

Я хотел бы объединить списки с одинаковыми префиксами, в результате чего:

('id', ('name', ('name_float_fml',)), ('user', ('email','last_login')))

Вот еще один пример:

(('baz', ('bing', ('fizz', 'frozz', ('frazz', ('fry', 'bleep', 'blop'))))), ('baz', ('zap', ('zang',))), 'foo', 'bar')

будет объединено с:

(('baz', (('bing', ('fizz', 'frozz', ('frazz', ('fry', 'bleep', 'blop')))), ('zap', ('zang')))), 'foo', 'bar')

Они предназначены для хранения путей от корня до листьев дерева:

• 'baz' -> 'bing' -> 'fizz', он же. ('baz' ('bing' ('fizz,)))
• 'baz' -> 'zap' -> 'zang', он же ('baz' ('zap', ('zang',)))
• 'baz' -> 'bing' -> 'frazz' -> 'blop', он же ('baz', ('bing', ('frazz', ('blop,))))

Я хочу объединить элементы, где листья достигаются одним и тем же путем. Я надеюсь, что это дает некоторое пояснение.

Я написал некоторый код для этого, но он уродлив, многословен и, возможно, хрупок. Есть ли какой-то общий, краткий и / или эффективный способ сделать это? Я предполагаю, что может быть какая-то магия itertools, о которой я не знаю, которая дала бы какое-то элегантное решение.

Примечание: Я использую Python 2.4

Answer 1

Вот версия, которая работает для опубликованных вами примеров:

a = ('id', ('name', ('name_float_fml',)), ('user', ('email',)), ('user', ('last_login',)))
b = (('baz', ('bing', ('fizz', 'frozz',('frazz', ('fry', 'bleep', 'blop'))))), ('baz', ('zap', ('zang',))), 'foo', 'bar')

def preserve_path(value):
    if len(value) == 2 and isinstance(value[1], (list, tuple)):
        return [value]
    else:
        return value

def flatten_group(my_list):
    d = {}
    for item in my_list:
        # Only items with one string, followed by one tuple represent a path
        # segment. In all other situations, strings are leaves.
        if isinstance(item, (list, tuple)) and len(item) == 2:
            key, value = item
            if key in d:
                d[key].extend(flatten_group(preserve_path(value)))
            else:
                d[key] = preserve_path(list(flatten_group(value)))
        else:
            yield item

    for item in d.iteritems():
        yield item

print list(flatten_group(a))
# ['id', ('name', ['name_float_fml']), ('user', ['email', 'last_login'])]
print list(flatten_group(b))
# ['foo', 'bar', ('baz', [['bing', ('fizz', 'frozz', ('frazz', ('fry', 'bleep', 'blop')))], ('zap', ['zang'])])]

Редактировать 3: Обновлено с помощью соавторской версии, которая работает для обоих примеров и включает в себя ваше ограничение, касающееся только объединения элементов, которые являются кортежами / списками и содержат два элемента. Это также предотвращает дополнительное выравнивание слитых элементов.

Answer 2

Вот решение, которое использует itertools.groupby:

from itertools import groupby
def combine(tuples):
    rlist = [tuples[0]]
    for k, g in groupby(tuples[1:], key=lambda t: t[0]):
        rlist.append(tuple((k, tuple(gg[1:][0][0] for gg in g))))
    return tuple(rlist)

sample = ('id', ('name', ('name_float_fml',)), ('user', ('email',)), ('user', ('last_login',)))
print combine(sample)
# ('id', ('name', ('name_float_fml',)), ('user', ('email', 'last_login')))

Возможно рекурсивное применение этого процесса для образцов более сложных, чем приведенный в вашем вопросе.

Answer 3

Вот рекурсивная функция для этого:

def merge(x, bases = (tuple, list)):
    for e in x:
        if type(e) in bases:
            for e in merge(e, bases):
                yield e
        else:
            yield e

tup = (0, (1, 3, 2), [5, (7, 2)])

print list(merge(tup))
# [0, 1, 3, 2, 5, 7, 2]