Połączenie dwóch list przy zachowaniu zamówienia

Question

Próbuję połączyć dwie listy i wypisać wszystkie możliwe kombinacje połączonej listy, która zachowuje kolejność oryginalnych dwóch list. Na przykład:

list_1 = [9,8] 
list_2 = [2,1] 

#output 
combo= [9821,9281,2981,2918,2198,9218] 

gdzie każdy element na liście "combo", zawsze przychodzi przed i zawsze przychodzi przed .

Do tej pory użyłem permutacji z itertools do zapętlenia wszystkich możliwych permutacji, ale nie jest wystarczająco szybki.

Oto co mam:

from itertools import permutations 
seq = [5, 9, 8, 2, 1] 
plist = [] 
root = seq[0] 
left = filter(lambda x: x > root, seq) 
right = filter(lambda x: x < root, seq) 

for pseq in permutations(seq[1:]): 
    pseq = (root,) + pseq 
    if list(filter(lambda x: x > root, pseq)) == left and list(filter(lambda x: x < root, pseq)) == right: 
     plist.append(pseq) 
print plist 

Dzięki!

Answer 1

spróbuj tego:

import itertools 

lst1 = ['a', 'b'] 
lst2 = [1, 2] 

for locations in itertools.combinations(range(len(lst1) + len(lst2)), len(lst2)): 
    result = lst1[:] 
    for location, element in zip(locations, lst2): 
     result.insert(location, element) 
    print(''.join(map(str, result))) 

# Output: 
# 12ab 
# 1a2b 
# 1ab2 
# a12b 
# a1b2 
# ab12 

sposób myślenia o problemie, zacząć od pierwszej sekwencji (ab w tym przypadku), a następnie szukać wszystkich możliwych miejscach można wstawić elementy drugiej sekwencji (w tym przypadku 1, a następnie 2).

Wywołanie itertools.combinations daje te kombinacje. W powyższym przykładzie, że iteracje przez pozycji (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3).

Dla każdego z tych zestawów współrzędnych, po prostu wstawiamy elementy z drugiej listy w określonych indeksach.

UPDATE

Oto rekurencyjny rozwiązanie, które obsługuje dowolną liczbę list na podstawie @ sugestią Đặng Xuan Thanh w swojej odpowiedzi:

import itertools 

def in_order_combinations(*lists): 
    lists = list(filter(len, lists)) 

    if len(lists) == 0: 
     yield [] 

    for lst in lists: 
     element = lst.pop() 
     for combination in in_order_combinations(*lists): 
      yield combination + [element] 
     lst.append(element) 

for combo in in_order_combinations(['a', 'b'], [1, 2]): 
    print(''.join(map(str, combo))) 

Podstawowym założeniem jest to, że wychodząc z ab i 12, wiesz, że wszystkie możliwe rozwiązania zakończą się z b lub 2. Te, które kończą się na b, zaczną od rozwiązania dla (a, 12). Te, które kończą się 2, zaczną od rozwiązania dla (ab, ,).

Podstawowym przykładem rekursji jest po prostu brak list. (Puste listy są przycinane, kiedy idziemy.)

Answer 2

Nie wiem więcej o Pythonie, ale mam pomysł może pomóc.
Pomysł jest za pomocą rekurencyjnych:
do przyłączenia dwóch list n & m elementów, mamy dwa przypadki:

• łączenia dwóch list n-1 & m elementów, a następnie umieścić elementy n-th Pod koniec.
• Dołącz do dwóch list n & elementów m-1, a następnie umieść m-te elementy na końcu.

Użyj tego rekursywnego, wystarczy poradzić sobie w najprostszym przypadku: dołącz dwie listy z jedną z nich jest pusta. Szybko to będzie używać permutacji. Mam nadzieję, że to pomaga.

Answer 3

Roztwór stosując rekurencyjny generator (wymaga Python 3 dla yield from ...):

def f(a,b,p=[]): 
    if len(a)==0 or len(b)==0: 
     yield p+a+b 
    else: 
     yield from f(a[1:],b,p+[a[0]]) 
     yield from f(a,b[1:],p+[b[0]]) 

na każdym kroku, można wybrać pierwszy znak a lub pierwszego znaku b i rekurencyjnie zbudować resztę lista (-y). jeśli jedno z nich stanie się puste, nie ma już punktów wyboru.

>>> list(f([9,8],[2,1])) 
[[9, 8, 2, 1], [9, 2, 8, 1], [9, 2, 1, 8], [2, 9, 8, 1], [2, 9, 1, 8], [2, 1, 9, 8]] 

Aktualizacja: począwszy od powyższego rozwiązania, oto implementacja który obsługuje dowolną liczbę list:

def f(*args,p=[]): 
    if any(len(arg)==0 for arg in args): 
     yield p+[el for arg in args for el in arg] 
    else: 
     for i,arg in enumerate(args): 
      args1=list(args) 
      args1[i]=arg[1:] 
      yield from f(*args1,p=p+[arg[0]]) 

Answer 4

Long (owski) jedno-liner

from itertools import * 
from copy import deepcopy 

list({''.join(str(l.pop(0)) for l in deepcopy(p)) for p in permutations(chain(repeat(list_1, len(list_1)), repeat(list_2, len(list_2))))}) 

Zobacz moją odpowiedź na podobny problem All possible ways to interleave two strings dla wyjaśnienia.

Answer 5

Byłoby nieco bardziej czysto, gdyby twoje wyjście było listą zamiast połączonych cyfr, ale to nie ma znaczenia. Oto proste rozwiązanie rekursywne w python3 (ale możesz go trywialnie przekonwertować na python2).

def combine(xs, ys): 
    if xs == []: return [ys] 
    if ys == []: return [xs] 
    x, *xs_tail = xs 
    y, *ys_tail = ys 
    return [ [x] + l for l in combine(xs_tail, ys) ] + \ 
      [ [y] + l for l in combine(ys_tail, xs) ] 

Będzie to zwróci listę list:

>>> combine([9, 8], [2, 1]) 
[[9, 8, 2, 1], [9, 2, 1, 8], [9, 2, 8, 1], [2, 1, 9, 8], [2, 9, 8, 1], [2, 9, 1, 8]] 

Oto sposób, aby przekształcić go do żądanego wyjścia:

def list_to_int(digits): 
    return int(''.join(map(str, digits))) 

def combine_flat(xs, ys): 
    return [list_to_int(l) for l in combine(xs, ys)]