How to find combination of n elements from list of lists while choosing single element for each list

Question

Looking for combinations for n elements from list of lists but choosing only one element from each list. E.g.

list =  [[a, b], [c,d], [e,f,g,h,i], [j,k,l,m, n], [o,p]..]

While choosing no more than one element from each list, I am trying to come up with different combinations

e.g: for combination of n = 2 elements:

[a,c] [b,c], [c,j]...so on

for combination of n = 3 elements:

[a,c,e], [a,d,f]..so on

for combination of n = 4 elements:

[a, c, j, o], [a,c, i, p] ...

I tried using itertools combinations, but quickly running into issues. Any hints?

Do you have a code example with itertools? – forgetso Aug 11 '20 at 19:08 — forgetso, Aug 11 '20 at 19:08

pitamer · Answer 1 · 2020-10-04T08:38:55.867

1

Is this what you are trying to achieve?

import itertools
from pprint import pprint

original_lst = [['a', 'b'], ['c','d'], ['e','f','g','h','i'], ['j','k','l','m','n'], ['o','p']]

def two_on_same_sublist(items, lst):
    for sub in lst:
        for i in itertools.combinations(items, 2):
            if all(x in sub for x in i):
                return True
            else:
                continue


def possible_combinations_of_items_in_sub_lists_no_rep(lst, n):
    flat_lst = [i for sublist in lst for i in sublist] # Make it one flat list
    return [i for i in itertools.combinations(flat_lst, n) if not two_on_same_sublist(i, lst)]

pprint(possible_combinations_of_items_in_sub_lists_no_rep(original_lst, 3))

edited Oct 04 '20 at 08:38

answered Aug 11 '20 at 19:25

pitamer

643
2
12
25

This will only give out one list. The OP wants combinations. – Harshal Parekh Aug 11 '20 at 19:26
It returns a list with a possible combination of items from the original list, which if I understand correctly, is what OP asked for... if OP wants several combinations, it's possible to use `[random_combination(lst, n) for i in range(num_of_combinations)]`. Still waiting for clarification from OP about what they want to achieve exactly :) @HarshalParekh @RSINGH – pitamer Aug 11 '20 at 19:34
*e.g: for combination of n =2 elements: [a,c] [b,c], [c,j]...so on* – Harshal Parekh Aug 11 '20 at 19:37
I am looking for ALL the combinations for a particular value of n. However each combination should not have more than one element from the same list. – RSINGH Aug 11 '20 at 19:38
Oh i see... Updated my answer to provide that, would love to hear if it works now as you expected @RSINGH :) – pitamer Aug 11 '20 at 19:44
Well 'a' and 'b' cannot be in the same combination since we can only choose one element for each original list – RSINGH Aug 11 '20 at 19:53
OK! Fixed again so that items from same sublist in the original list can't be combined :) @HarshalParekh – pitamer Aug 11 '20 at 20:25
hmm.still does not work. I see elements from same list in combinations – RSINGH Aug 11 '20 at 20:37
My bad! Works now @HarshalParekh – pitamer Aug 11 '20 at 20:53
Further improved and simplified the code again, this was a fun problem to solve :) – pitamer Aug 12 '20 at 05:48
Isnt it much simpler to convert the entire data into a dictionary based on element size. Then reference it by key where key is size? – Joe Ferndz Aug 12 '20 at 23:18
@JoeFerndz Could be! Your answer indeed seems more elegant :) However, after many misunderstandings and clarifications of OP's original intention (the examples given in the question are a bit confusing), I now believe what he wants is an **exhaustive list of possible combinations of items in the sublists of a given list, while no two items from each combination are both included in the same sublist of the given list.** So i think working with a dictionary won't necessarily improve simplicity here... – pitamer Aug 13 '20 at 07:58

Joe Ferndz · Answer 2 · 2020-08-12T07:40:01.057

I think you are looking for something like this.

Find the min and max size of sub list. Then create a dictionary with keys ranging from min to max.

Code:

from collections import defaultdict

c = defaultdict(list)

lst =  [['a','b'],
        ['c','d'],
        ['e','f','g','h','i'],
        ['j','k','l','m','n'],
        ['o','p'],
        ['q','r','s'],
        ['t','u','v'],
        ['w','x','y','z']]

a = min(map(len,lst)) #find min of sub list - here it will be 2
b = max(map(len,lst)) #find max of sub list - here it will be 5

for v in lst: #iterate thru the full list
    c[len(v)].append(v) #store values into a dictionary with key = len (sublist)

c = dict(c) #convert it back to normal dict

#iterate from min thru max and print the combinations
#skip if key not found in dictionary

for i in range (a, b+1):
    if i in c: print ('Combinations of n =',i, 'elements are :', c[i])

Output:

Combinations of n = 2 elements are : [['a', 'b'], ['c', 'd'], ['o', 'p']]
Combinations of n = 3 elements are : [['q', 'r', 's'], ['t', 'u', 'v']]
Combinations of n = 4 elements are : [['w', 'x', 'y', 'z']]
Combinations of n = 5 elements are : [['e', 'f', 'g', 'h', 'i'], ['j', 'k', 'l', 'm', 'n']]

How to find combination of n elements from list of lists while choosing single element for each list

2 Answers2