Siparişi tutarken iki listenin birleşimi

Question

İki listeye katılmaya çalışıyorum ve birleştirilen listenin tüm olası kombinasyonlarını orijinal iki listenin sırasını koruyor. Örneğin:

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

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

nerede listesi "tuşlarıyla" her eleman, ve hep önce gelir önce daima gelir de.

Şimdiye kadar, tüm olası permütasyonları yapmak için itertoollerden permütasyonları kullandım, ancak yeterince hızlı değil.

İşte ne var:

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 

teşekkürler!

Answer 1

bu Deneyin:

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 

Sorunun düşünüyorum şekilde, (bu durumda ab) ilk dizisi ile başlar ve sonra unsurları ekleyebilirsiniz tüm olası yerlerde aramaya ikinci diziden (bu durumda, bir 1 ve daha sonra bir 2).

itertools.combinations numaralı çağrı size bu kombinasyonları sunar. Yukarıdaki örnekte, (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3) numaralı pozisyonlarda yineleme yapar.

Bu koordinat kümelerinin her biri için, öğeleri yalnızca belirtilen dizinlerde ikinci listeden ekleriz.

GÜNCELLEME

İşte onun cevabını @ Đặng Xuân Thanh önerisine dayalı listeleri herhangi bir sayı işleyen bir özyinelemeli çözümü var:

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

temel fikir, yani ab ile başlayan ve 12, tüm olası çözümlerin b veya 2 ile biteceğini biliyorsunuz. b ile bitenler, (a, 12) için bir çözümle başlayacak. 2 ile bitenler, (ab, 1) için bir çözümle başlayacaktır.

Özyineleme için temel durum, hiçbir liste kalmadıysa ortaya çıkar. (Boş listeler, biz giderken budanırız.)

Answer 2

Python hakkında daha fazla bilgim yok ama size yardımcı olabilecek bir fikrim var.
Fikir özyinelemeli kullanıyor:

• iki listeyi Üyelik n-1 & m ürün, o zaman en n'inci öğeleri koyun:
  iki n listeler & m öğeleri katılmak için, iki türlü durum son.
• İki listeye katıl n & m-1 adet, ardından m-th öğelerini sonuna yerleştirin.

Bu özyinelemeyi kullanın, en basit durumu ele almanız yeterlidir: bunlardan biriyle iki liste birleştirin boş. Bu, daha sonra permütasyon kullanarak hızlı olacaktır. Umut eder.

Answer 3

bir (yield from ... Python 3 gerektirir) yinelemeli jeneratörü kullanılarak çözelti: her adımda

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

, sen a ilk karakter ya da b ilk karakteri almak ve yinelemeli geri kalanını oluşturabilir liste (ler). İkisinden biri boş olursa, başka seçim noktası yoktur.

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

Güncelleme: Yukarıdaki çözüm başlayarak burada listeleri herhangi bir sayı işleyen bir uygulama:

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

Uzun (imsi) tek satırlık

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

cevabım bakın Açıklama için benzer sorun All possible ways to interleave two strings.

Answer 5

Çıktınız, birleştirilen basamak yerine bir liste listesiyse biraz daha temiz olurdu, ancak önemli değil. İşte python3'te basit bir özyinelemeli çözümdür (ancak bunu python2'ye kolayca dönüştürebilirsiniz).

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

Bu listelerin bir listesini döndürür:

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

İşte

istediğiniz çıkışa dönüştürmek için:

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