4

I have two lists, both of the same length:

a = [1,2,3]
b = [4,5,6]

How can I get all possible results, from iterating over a and either choosing to replace it with the corresponding element from b, or not doing so?

output[0] = [1,2,3] # no replacements
output[1] = [4,2,3] # first item was replaced
output[2] = [1,5,3] # second item was replaced
output[3] = [1,2,6] # third item was replaced
output[4] = [4,5,3] # first and second items were replaced
output[5] = [4,2,6] # first and third items were replaced
output[6] = [1,5,6] # second and third items were replaced
output[7] = [4,5,6] # all items were replaced
Karl Knechtel
  • 62,466
  • 11
  • 102
  • 153
P. Shark
  • 198
  • 1
  • 7
  • This is equivalent to constructing the pairs of elements from `a` and `b` and then getting the results of choosing an element from each pair (i.e., a Cartesian product of the pairs). – Karl Knechtel Mar 02 '23 at 02:44

3 Answers3

4

Creating 3 lists of two elements would not over-complicate the code at all. zip can "flip the axes" of multiple lists trivially (making X sequences of Y elements into Y sequences of X elements), making it easy to use itertools.product:

import itertools

a = [1,2,3]
b = [4,5,6]

# Unpacking result of zip(a, b) means you automatically pass
# (1, 4), (2, 5), (3, 6)
# as the arguments to itertools.product
output = list(itertools.product(*zip(a, b)))

print(*output, sep="\n")

Which outputs:

(1, 2, 3)
(1, 2, 6)
(1, 5, 3)
(1, 5, 6)
(4, 2, 3)
(4, 2, 6)
(4, 5, 3)
(4, 5, 6)

Different ordering than your example output, but it's the same set of possible replacements.

ShadowRanger
  • 143,180
  • 12
  • 188
  • 271
  • Note: If you really want `list`s, not `tuple`s for some reason, `output = list(map(list, itertools.product(*zip(a, b))))` will convert the `tuple`s back to `list`s, but it's usually not necessary. – ShadowRanger Jun 16 '17 at 18:10
3

Each item may independently be replaced or left alone. This can be modeled by a bit being 1 or 0. If you consider each item to be a separate bit, then iterating over all of the possibilities can be mapped to iterating over all of the combinations of n bits.

In other words, iterate from 0 to 2n-1 and look at the bit patterns.

n = len(a)
for i in range(2**n):
    yield [a[j] if i & (1 << j) != 0 else b[j] for j in range(n)]

Breaking this down, i & (1 << j) != 0 checks if the jth bit of i is set. If it is, use a[j], otherwise b[j].

Result:

[1, 2, 3]
[4, 2, 3]
[1, 5, 3]
[4, 5, 3]
[1, 2, 6]
[4, 2, 6]
[1, 5, 6]
[4, 5, 6]
John Kugelman
  • 349,597
  • 67
  • 533
  • 578
0

Okay this is similar to the other answers, but taking a bit from both. You can model your problem as finding all possible bits of a sequence of given length, and replacing only when there is 1, and otherwise not.

from itertools import product

a = [1,2,3]
b = [4,5,6]

## All binary combinations of length of a (or b)
combinations = product([0,1], repeat=len(a))

for combination in combinations:
    y = []
    for l, i in zip(zip(a,b),combination):
         y.append(l[i])
    print y

All combinations of bits are:

(0, 0, 0)
(0, 0, 1)
(0, 1, 0)
(0, 1, 1)
(1, 0, 0)
(1, 0, 1)
(1, 1, 0)
(1, 1, 1)

Which results in:

[1, 2, 3]
[1, 2, 6]
[1, 5, 3]
[1, 5, 6]
[4, 2, 3]
[4, 2, 6]
[4, 5, 3]
[4, 5, 6]
Sahil M
  • 1,790
  • 1
  • 16
  • 31
  • While this works, I see no reason at all to prefer it over getting the product of the elements directly. Computing indices then indexing is like doing `for i in range(len(someseq)): x = someseq[i]` (and never using `i` again), which is one of the most straightforward anti-patterns in Python committed by recidivist C programmers, being slower, less flexible (doesn't work with iterators), more verbose and less self documenting than `for usefulname in someseq:` – ShadowRanger Jun 16 '17 at 18:08
  • @ShadowRanger I agree, and I would also get the product directly. However I put this in, because it is easy to understand. – Sahil M Jun 16 '17 at 18:17