Python a harder itertools.product problem with defined grouping

Question

So here is the issue.

First, here is normal itertools.product operation:

x = [[0, 1], [0, 1], [0, 1]]
itertools.product(*x)

The output is:

>>> [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]

Now x is an array of length 3. Let's say I define a "group plan":

# Note 0th and 1st group indices are both 0, indicating they are of the same group.
group plan = [0, 0, 1]

My goal is to implement a

def my_itertools_product_with_group(*args, group_plan=[0, 0, 1]) The correct solutions will be:

>>> [[0, 0, 0], [0, 0, 1], [1, 1, 0], [1, 1, 1]]

Because we can see for the 0th and 1st element of each list, they are the same, either [0, 0] or [1, 1]

Another example: arr = [['a0', 'A0'], ['a1', 'A1'], ['a2', 'A2'], ['a3', 'A3'], ['a4', 'A4'], ['a5', 'A5']]

The grouping scheme defined as [0, 0, 0, 1, 0, 2] In that sense, still want to find all possible combinations

result = my_itertools_product_with_group(*arr, group_plan=[0, 0, 0, 1, 0, 2])

The legal outputs are:

result = [\
['a0', 'a1', 'a2', 'a3', 'a4', 'a5']
['a0', 'a1', 'a2', 'a3', 'a4', 'A5']
['a0', 'a1', 'a2', 'A3', 'a4', 'a5']
['a0', 'a1', 'a2', 'A3', 'a4', 'A5']

['A0', 'A1', 'A2', 'a3', 'A4', 'a5']
['A0', 'A1', 'A2', 'a3', 'A4', 'A5']
['A0', 'A1', 'A2', 'A3', 'A4', 'a5']
['A0', 'A1', 'A2', 'A3', 'A4', 'A5']]

My attempts: I can do post filtering after calling normal itertool.product(), but am also wondering if it is possible to do it in one-shot as defined by the def my_itertools_product_with_group(*args, group_plan)

Here is my post-filtering code where you can see, I first get cartesian product of [ [0, 1] * 5 ].

group_plan = [0, 0, 1, 2, 0] # meaning all elements marked as 0 should be treated as the same group

result = [x for x in itertools.product([0, 1], repeat=5) if grouped_as_planned(x, group_plan)]

...
    def grouped_as_planned(arr, group_plan):
        for x_ind, x in enumerate(arr):
            for y_ind in range(x_ind + 1, len(arr)):
                if group_plan[x_ind] == group_plan[y_ind]:
                    if x != arr[y_ind]:
                        return False
        return True

Please share what you have attempted to implement the said behavior, and ask specific questions about the problems you're having with your implementation. — blhsing, Aug 12 '21 at 02:07
Please repeat [on topic](https://stackoverflow.com/help/on-topic) and [how to ask](https://stackoverflow.com/help/how-to-ask) from the [intro tour](https://stackoverflow.com/tour). “Show me how to solve this coding problem” is not a Stack Overflow issue. We expect you to make an honest attempt, and *then* ask a *specific* question about your algorithm or technique. — Prune, Aug 12 '21 at 15:28
Your problem specification is hard to understand, in part because your first example is a *negative* one that doesn't clearly explain the rationale. — Prune, Aug 12 '21 at 15:28
[I’m stuck](https://softwareengineering.meta.stackexchange.com/questions/6366/where-to-start/), without specifics of *how* you're stuck, is an issue for a tutor in problem analysis or specification. It’s not focused enough for Stack Overflow. — Prune, Aug 12 '21 at 15:29
very interesting question :) . I have added a solution, do check it out. — Akshay Sehgal, Aug 13 '21 at 23:06

Akshay Sehgal · Answer 1 · 2021-08-13T23:06:07.670

Very interesting question. Here is a solution.

I use defaultdict for grouping, numpy.argsort for storing original order of arrays and itertools.product for taking products.

Explanation inline as comments:

import numpy as np
from collections import defaultdict
import itertools

def my_itertools_product_with_group(arr, group_plan):
    order = np.argsort(group_plan) #Stores the original order for the columns
    
    #Grouper dictionary for group plan
    d = defaultdict(list)
    for i,j in zip(group_plan, arr):
        d[i].append(j)
    
    stack = [zip(*v) for k,v in d.items()] #Inter-group stacker for each group
    prod = itertools.product(*stack)       #itertools product
    flat = [[k for j in i for k in j ] for i in prod] #Flatten ragged tensor from 3D to 2D
    reorder = np.array(flat)[:,order].tolist() #Reorder based on original order and return
    return reorder

Testing it out on your complex case:

arr = [['a0', 'A0'], ['a1', 'A1'], ['a2', 'A2'], ['a3', 'A3'], ['a4', 'A4'], ['a5', 'A5']]
group_plan = [0,0,0,1,0,2]

my_itertools_product_with_group(arr, group_plan)

[['a0', 'a1', 'a2', 'a3', 'a4', 'a5'],
 ['a0', 'a1', 'a2', 'a3', 'a4', 'A5'],
 ['a0', 'a1', 'a2', 'A3', 'a4', 'a5'],
 ['a0', 'a1', 'a2', 'A3', 'a4', 'A5'],
 ['A0', 'A1', 'A2', 'a3', 'A4', 'a5'],
 ['A0', 'A1', 'A2', 'a3', 'A4', 'A5'],
 ['A0', 'A1', 'A2', 'A3', 'A4', 'a5'],
 ['A0', 'A1', 'A2', 'A3', 'A4', 'A5']]

Another example:

arr = [[0, 1], [0, 1], [0, 1]]
group_plan = [0,0,1]

my_itertools_product_with_group(arr, group_plan)

[[0, 0, 0], [0, 0, 1], [1, 1, 0], [1, 1, 1]]

Explanation:

Let's break it down step by step.

Store original order for reordering in the last step:

order = np.argsort(group_plan)
order

# array([0, 1, 2, 4, 3, 5])

Use defaultdict to group items belonging to same group:

d = defaultdict(list)
for i,j in zip(group_plan, arr):
    d[i].append(j)
    
dict(d)

#{0: [['a0', 'A0'], ['a1', 'A1'], ['a2', 'A2'], ['a4', 'A4']],
# 1: [['a3', 'A3']],
# 2: [['a5', 'A5']]}

Stack the list of lists for each of the groups (transpose)

stack = [list(zip(*v)) for k,v in d.items()]
stack

#[[('a0', 'a1', 'a2', 'a4'), ('A0', 'A1', 'A2', 'A4')],
# [('a3',), ('A3',)],
# [('a5',), ('A5',)]]

Take itertools.product between the stacked/grouped items

prod = list(itertools.product(*stack))
prod

#[(('a0', 'a1', 'a2', 'a4'), ('a3',), ('a5',)),
# (('a0', 'a1', 'a2', 'a4'), ('a3',), ('A5',)),
# (('a0', 'a1', 'a2', 'a4'), ('A3',), ('a5',)),
# (('a0', 'a1', 'a2', 'a4'), ('A3',), ('A5',)),
# (('A0', 'A1', 'A2', 'A4'), ('a3',), ('a5',)),
# (('A0', 'A1', 'A2', 'A4'), ('a3',), ('A5',)),
# (('A0', 'A1', 'A2', 'A4'), ('A3',), ('a5',)),
# (('A0', 'A1', 'A2', 'A4'), ('A3',), ('A5',))]

Flatten the innermost tuple to get a list of lists in the ragged matrix.

flat = [[k for j in i for k in j ] for i in prod]
flat

#[['a0', 'a1', 'a2', 'a4', 'a3', 'a5'],
# ['a0', 'a1', 'a2', 'a4', 'a3', 'A5'],
# ['a0', 'a1', 'a2', 'a4', 'A3', 'a5'],
# ['a0', 'a1', 'a2', 'a4', 'A3', 'A5'],
# ['A0', 'A1', 'A2', 'A4', 'a3', 'a5'],
# ['A0', 'A1', 'A2', 'A4', 'a3', 'A5'],
# ['A0', 'A1', 'A2', 'A4', 'A3', 'a5'],
# ['A0', 'A1', 'A2', 'A4', 'A3', 'A5']]

Reorder numpy array using the original order stored and convert back to list

reorder = np.array(flat)[:,order].tolist()
reorder

#[['a0', 'a1', 'a2', 'a3', 'a4', 'a5'],
# ['a0', 'a1', 'a2', 'a3', 'a4', 'A5'],
# ['a0', 'a1', 'a2', 'A3', 'a4', 'a5'],
# ['a0', 'a1', 'a2', 'A3', 'a4', 'A5'],
# ['A0', 'A1', 'A2', 'a3', 'A4', 'a5'],
# ['A0', 'A1', 'A2', 'a3', 'A4', 'A5'],
# ['A0', 'A1', 'A2', 'A3', 'A4', 'a5'],
# ['A0', 'A1', 'A2', 'A3', 'A4', 'A5']]

score 1 · Answer 2 · answered Aug 13 '21 at 21:21

You can do this directly, but it's not quite as easy: you have to drive the logic from the viewpoint of your grouping scheme, as that defines what you have for independent elements.

I suggest that you set up a table, keyed by the grouping index. The values will be the list choices and their placement in the solution. Let's take a shorter version of your second example, with only four elements (instead of six).

arr = [['a0', 'A0'], ['a1', 'A1'], ['a2', 'A2'], ['a3', 'A3']]
grouping_plan = [0, 1, 0, 2]

This shows that you have to link groups 0 & 2. Your table will look like this:

group   pos      values
  0    [0, 2]    [['a0', a2'], ['A0, A2]]
  1     [1]      [['a1'], ['A1']]
  3     [3]      [['a3'], ['A3']]

Now, you call product on you list of values. You will get items such as

[['a0', a2'], ['A1'], ['a3']]

Now, you refer to your in-order grouping indices:

[[0, 2], [1], [3]]

Flatten both lists, zip them, sort on the index, and you have the desired order.

Coding details are left as an exercise for the reader. :-)

Python a harder itertools.product problem with defined grouping

2 Answers2

Explanation: