Объединение двух списков в нескольких путях - Python

Ответ 1

В случае 2x4 вы хотите взять все 8 элементов, не нарушая порядок в каждом квадранте. Эти примеры:

a, b, c, d, 1, 2, 3, 4    
1, 2, 3, 4, a, b, c, d    
a, b, 1, 2, c, 3, 4, d

Может быть преобразован в последовательности "инструкций", которые являются списком, который следует взять, 0 или 1:

0 0 0 0 1 1 1 1
1 1 1 1 0 0 0 0
0 0 1 1 0 1 1 0

Как только вы это осознали, вы можете заметить, что последовательности, которые нам нужно создать, - это все перестановки из четырех нулей и четырех. Сделав этот скачок, мы можем использовать itertools:

itertools.permutations([0,0,0,0,1,1,1,1])

Для случая 2x4 это дает 40320 результатов, но только 70 уникальных (потому что itertools.permutations считает, что 1,1,1 отличается от 1,1,1, если числа переупорядочены). Вы можете получить уникальные перестановки из ответа здесь: fooobar.com/questions/111860/... или просто использовать set().

Объединяя это, вот полное решение:

import itertools

def combos(*seqs):
    counts = map(len, seqs)
    base = []
    for ii, count in enumerate(counts):
        base.extend([ii]*count)
    for take in set(itertools.permutations(base)):
        result = []
        where = [0] * len(seqs)
        for elem in take:
            result.append(seqs[elem][where[elem]])
            where[elem] += 1
        yield result

Вы можете протестировать его таким образом (дает 70 результатов):

a = ['a', 'b', 'c', 'd']
b = [1, 2, 3, 4]

for res in combos(a, b):
    print res

Ответ 2

Рекурсивный подход с python:

def f( s , l1 , l2 ):
        if( l1 == [] and l2 == [] ):
                print s
                return
        if( l1 != [] ):
                f( s + l1[0] , l1[1:] , l2 )
        if( l2 != [] ):
                f( s + str(l2[0]) , l1 , l2[1:] )

Ответ 3

Один из вариантов - использовать счетчик, в котором заданные биты соответствуют элементу на a и не заданы в элементе b. Для каждого значения в счетчике проверьте, установлены ли биты len(a) и генерируются перестановки:

def ordered_permutations(l1, l2):
    length = len(l1) + len(l2)
    fmt = '{{0:0{0}b}}'.format(length)

    for i in xrange(2 ** length):
        seq = fmt.format(i)

        if seq.count('1') == len(l1):
            iters = [iter(l1), iter(l2)]
            yield [iters[int(c)].next() for c in seq]

Использование:

for p in ordered_permutations(['a','b'], [1,2]):
    print p

Вывод:

['a', 'b', 1, 2]
['a', 1, 'b', 2]
['a', 1, 2, 'b']
[1, 'a', 'b', 2]
[1, 'a', 2, 'b']
[1, 2, 'a', 'b']

Реализация может быть улучшена с помощью HAKMEM 175 для генерации следующей последовательности вместо использования счетчика и проверки правильности количества бит.

Ответ 4

Альтернативный вариант - использовать рекурсию.

псевдокод:

result[] SortedMergePermutations(listA,listB)
{
  result.append([FirstElementOfListA, 
    SortedMergePermutations(listAWithoutFirstElement,listB))]
  result.append([FirstElementOfListB,
    SortedMergePermutations(listA,listBWithoutFirstElement))]
  ])
  return result
}

Ответ 5

Я нашел решение, которое работает только для двух последовательностей, но использует itertools.combinations(), чтобы найти только возможные последовательности позиций, в которые нужно поместить (в порядке...) элементы первой последовательности

from __future__ import print_function

def print_merged(a, b):
    from itertools import combinations, cycle

    l = len(a) + len(b)
    ab = [cycle(a), cycle(b)]
    rng = range(l)
    print([a, b])

    for index in combinations(rng, len(a)):
        li = []
        for i in rng:
            n = 0 if i in index else 1
            li.append(next(ab[n]))
        print(li)

# testing

print_merged([1,2,3], [4,5,6])
print('-'*72)
print_merged([1,2], [4,5,6])
print('-'*72)
print_merged([1,2,3], [5,6])

Я смутно понимаю, что возможно иметь дело с большим количеством списков, объединяющих 3-й список с каждым из списков, сгенерированных из первого и второго, и т.д., идея, указывающая на направление рекурсивной реализации, но я "Я рад оставить такое достижение кому-то еще...

Изменить 1

Я удалил счетчик машин, поскольку объекты itertools.cycle() - это именно то, что необходимо.

Тестируемый выход

[[1, 2, 3], [4, 5, 6]]
[1, 2, 3, 4, 5, 6]
[1, 2, 4, 3, 5, 6]
[1, 2, 4, 5, 3, 6]
[1, 2, 4, 5, 6, 3]
[1, 4, 2, 3, 5, 6]
[1, 4, 2, 5, 3, 6]
[1, 4, 2, 5, 6, 3]
[1, 4, 5, 2, 3, 6]
[1, 4, 5, 2, 6, 3]
[1, 4, 5, 6, 2, 3]
[4, 1, 2, 3, 5, 6]
[4, 1, 2, 5, 3, 6]
[4, 1, 2, 5, 6, 3]
[4, 1, 5, 2, 3, 6]
[4, 1, 5, 2, 6, 3]
[4, 1, 5, 6, 2, 3]
[4, 5, 1, 2, 3, 6]
[4, 5, 1, 2, 6, 3]
[4, 5, 1, 6, 2, 3]
[4, 5, 6, 1, 2, 3]
------------------------------------------------------------------------
[[1, 2], [4, 5, 6]]
[1, 2, 4, 5, 6]
[1, 4, 2, 5, 6]
[1, 4, 5, 2, 6]
[1, 4, 5, 6, 2]
[4, 1, 2, 5, 6]
[4, 1, 5, 2, 6]
[4, 1, 5, 6, 2]
[4, 5, 1, 2, 6]
[4, 5, 1, 6, 2]
[4, 5, 6, 1, 2]
------------------------------------------------------------------------
[[1, 2, 3], [5, 6]]
[1, 2, 3, 5, 6]
[1, 2, 5, 3, 6]
[1, 2, 5, 6, 3]
[1, 5, 2, 3, 6]
[1, 5, 2, 6, 3]
[1, 5, 6, 2, 3]
[5, 1, 2, 3, 6]
[5, 1, 2, 6, 3]
[5, 1, 6, 2, 3]
[5, 6, 1, 2, 3]