How to find how many items of list B forms list A

Admin 1
Viewed 65

I want to find minimum items of list B that forms list A. lets assume A=['abcdef'] and B=['abc','ad','adef','adef','bdf']. Then since items with index 0 and 2 contains all letters of list A, the answer will be 2. I used the combination to find all the possible combination of B. But I am not sure how to continue. It seems most optimized way is Brute Force.

A=['abcdef']
B=['abc','ad','adef','adef','bdf']

for L in range(0, len(B)+1):
    for subset in itertools.combinations(B, L):
        if subset==A:
            print(subset)
combinations brute-force list python string
1 Answers

Here is an extension of your attempt. I have used a rather confusing comprehension to flatten the the list out into a set so I can make use of straightforward set operations to check whether one is a subset of the other.

import itertools

A='abcdef'
B=['abc','ad','adef','adef','bdf']

set_a = set(A)
solved = False


for L in range(0, len(B)+1):
    for subset in itertools.combinations(B, L):
        s = set(item for sublist in subset for item in sublist)
        if set_a.issubset(s):
            print(f'String A can be made from {L} items of list B, specifically: {subset}')
            solved = True
            break
    if solved: break
user_114324340
Related