두 개의 목록을 조합하여 순서를 유지하는 중

Question

두 목록을 결합하여 원본 목록의 순서를 유지하는 병합 된 목록의 가능한 모든 조합을 출력하려고합니다. 예를 들면 :

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

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

경우 목록 "콤보"의 각 요소에, 1 및 9 항상 8 전에 오기 전에 2 항상 제공한다.

지금까지 itertools의 순열을 사용하여 가능한 모든 순열을 반복했지만 충분히 빠르지는 않습니다.

여기에 내가 가진 무엇 :

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 

감사합니다!

Answer 1

이 시도 보내기

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 

내가 문제를 생각하는 방법, 당신이 (이 경우 ab) 첫 순서로 시작을 한 다음 요소를 삽입 할 수있는 모든 가능한 장소를 찾아 (이 경우 1 다음에 2).

itertools.combinations 호출은 이러한 조합을 제공합니다. 위의 예에서 위치는 (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3) 인 위치를 반복합니다.

각 좌표 집합에 대해 두 번째 목록의 요소를 지정된 인덱스에 삽입하기 만하면됩니다.

UPDATE

여기에 그의 대답에 @ Đặng 법사 탄의 제안에 따라 목록의 수를 처리하는 재귀 솔루션은 다음과 같습니다

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))) 

기본적인 아이디어는, 그 ab에서 시작하여 12의 경우 가능한 모든 솔루션은 b 또는 2으로 끝납니다. b으로 끝나는 것은 모두 (a, 12)에 대한 해결책으로 시작됩니다. 2으로 끝나는 것은 모두 (ab, 1)에 대한 해결책으로 시작됩니다.

재귀의 기본 경우는 단순히 목록이 남아 있지 않은 경우입니다. (우리가가는 동안 비어있는 목록이 정리됩니다.)

Answer 2

저는 파이썬에 대해 더 많이 알지는 못하지만, 도움이 될만한 아이디어가 있습니다.
아이디어는 재귀 사용 :

• 두 목록을 가입 N-1 & m 항목, 다음에서 n 번째 항목을 넣어 :
  이 두 목록 N & m 항목에 가입하기를, 우리는 두 가지 사례를 가지고 종료.
• 두 개의 목록 n & m-1 항목을 결합한 다음 끝에 m 번째 항목을 넣으십시오.

이 재귀를 사용하면 가장 단순한 경우 만 처리하면됩니다. 둘 중 하나가 포함 된 두 목록을 비우면됩니다. 순열을 빨리 사용합니다. 도움이 되길 바랍니다.

Answer 3

A (yield from ... 파이썬 3 필요) 재귀 생성기를 사용하여 솔루션 : 각 단계에서

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]]) 

, 당신은 a의 첫 번째 문자 또는 b의 첫 번째 문자를 선택하고, 재귀의 나머지 부분을 구축 할 수 있습니다 목록. 두 개 중 하나가 비어 있으면 더 이상 선택 지점이 없습니다.

>>> 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]] 

업데이트 : 위의 솔루션에서 시작하여, 여기에 목록의 수를 처리하는 구현 :

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

롱 (틱) 한 줄

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))))}) 

에 내 대답을 참조하십시오 유사한 문제 All possible ways to interleave two strings 설명.

Answer 5

결과가 연결된 숫자 대신 목록으로 표시되었지만 문제가되지 않는다면 조금 더 깨끗합니다. 다음은 python3에서 간단한 재귀 적 해결책입니다 (하지만 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) ] 

이 목록의 목록을 반환합니다

>>> 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]] 

다음

원하는 출력으로 변환하는 방법은 다음과 같습니다

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)]