Fusionner 2 Listes De Plusieurs Façons-Python
j'ai expérimenté un certain nombre de techniques, mais je suis sûr qu'il y a un moyen facile de le faire.
supposons que j'ai deux listes avec le même nombre d'articles (4 chacun):
a = ['a', 'b', 'c', 'd']
b = [1, 2, 3, 4]
j'aimerais fusionner ces listes de toutes les façons possibles, tout en conservant l'ordre. Exemple de sortie:
a, b, c, d, 1, 2, 3, 4
1, 2, 3, 4, a, b, c, d
a, b, 1, 2, c, 3, 4, d
le point est que chacune des listes doit conserver son ordre de sorte qu'un élément ne peut pas précéder un autre élément dans la sortie compte tenu de sa position dans la liste. si par exemple, la sortie ne peut pas être:
a, b, **d**, c, 1... > d precedes c whereas c is before d in the original list
1, **4**, a, b, 3.... > 4 precedes 3 whereas 3 is before 4 in the original list
je suppose que l'idée est de fusionner la deuxième liste dans la première liste de toutes les façons possibles. Un exemple développé est ceci:
a = [a, b]
b = [1, 2]
sortie désirée:
ab12
a1b2
a12b
1ab2
1a2b
12ab
Comment dois-je faire? Fait itertools avoir une capacité de faire cela d'une certaine façon? Ou est-il un autre moyen de faire ceci? S'il vous plaît aider!
5 réponses
dans le cas 2x4, vous voulez prendre tous les 8 éléments sans perturber l'ordre dans chaque quad. Ces exemples:
a, b, c, d, 1, 2, 3, 4
1, 2, 3, 4, a, b, c, d
a, b, 1, 2, c, 3, 4, d
peut être transformé en séquences d '"instructions" qui sont la liste à prendre, 0 ou 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
une fois que vous avez réalisé ceci, vous pouvez remarquer que les séquences que nous devons générer sont toutes les permutations de quatre zéros et quatre uns. Ayant fait ce saut, nous pouvons utiliser itertools:
itertools.permutations([0,0,0,0,1,1,1,1])
pour le 2x4 cas, cela donne 40320 résultats, mais seulement 70 (car itertools.permutations pense que 1,1,1 est différent de 1,1,1 si les nombres sont réorganisés). Vous pouvez obtenir de l'unique permutations de réponse ici: https://stackoverflow.com/a/6285330/4323 ou tout simplement utiliser set().
en regroupant tout cela, Voici une solution complète:
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
vous pouvez le tester de cette façon (donne 70 résultats):
a = ['a', 'b', 'c', 'd']
b = [1, 2, 3, 4]
for res in combos(a, b):
print res
Une approche récursive avec 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:] )
une option est d'utiliser un compteur où les bits définis correspondent à un élément sur a et annuler le point sur b. Pour chaque valeur dans le compteur, Vérifiez s'il y a len(a) bits et de générer une permutation:
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]
Utilisation:
for p in ordered_permutations(['a','b'], [1,2]):
print p
Sortie:
['a', 'b', 1, 2]
['a', 1, 'b', 2]
['a', 1, 2, 'b']
[1, 'a', 'b', 2]
[1, 'a', 2, 'b']
[1, 2, 'a', 'b']
la mise en oeuvre pourrait être améliorée en utilisant HAKMEM 175 pour générer la séquence suivante au lieu d'utiliser un compteur et vérifier la bonne quantité de bits sont définis.
L'option Alternative est d'utiliser la récursion.
Pseudo:
result[] SortedMergePermutations(listA,listB)
{
result.append([FirstElementOfListA,
SortedMergePermutations(listAWithoutFirstElement,listB))]
result.append([FirstElementOfListB,
SortedMergePermutations(listA,listBWithoutFirstElement))]
])
return result
}
j'ai trouvé une solution qui fonctionne uniquement pour les deux séquences, mais utilise itertools.combinations() pour trouver les séquences possibles de postes dans lequel placer (dans l'ordre... les éléments de la première séquence
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])
je comprends vaguement qu'il est possible de traiter un plus grand nombre de listes fusionnant la 3ème liste avec chacune des listes générées à partir de la première et de la seconde, etc, une idée qui pointe dans le sens d'une implémentation récursive mais je suis heureux de laisser une telle réalisation à quelqu'un d'autre...
Edit 1
j'ai enlevé les machines de comptoir, comme itertools.cycle() objets sont exactement ce qui est nécessaire.
sortie du Test
[[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]