Is there a better way to iterate through sets (A, B, C) choose (a, b, c)

The problem of choosing different numbers of items from each set can be converted to choosing one item from each set in a new collection of sets by repeating the sets the required number of times i.e. A choose 3 , B choose 2 , C choose 2 becomes choose 1 from each A,A,A,B,B,C,C. This is now the problem of finding a system of distinct representatives (sdr).

It is possible to find if a collection of sets has at least one sdr by the following. Let the collection of sets be S = { A_0 , A_1 , A_3 , ... , A_n } and X be the union of all A_i , and call its elements x_0 , x_1 , x_2 , ... consider the (bipartite) graph with a node for each A_i called N(A_i) and a node for each x_i called N(x_i) with edges connecting N(A_i) with N(x_j) if x_j is in A_i the problem of finding a sdr is the same as the problem of finding a matching of this graph that covers every N(A_i). Such a matching is a maximum matching so if at least one exists the Hopcroft Karp algorithm will find it. So to see if a collection of sets has a sdr run hopcroft karp on its graph then check the matching covers every N(A_i)

How could we check if an output set is valid? (e.g. {1,2,3,4,9,13,15} in the example) The elements of a valid output set have at least one one-to-one correspondence with the input sets A_i i.e. let an output set be W = { y_0 , y_1, ... , y_n } then there is at least one way to pick a distinct A_i for each y_j such that y_j is in A_i if we construct a new collection of sets SN = { B_0 , B_1, B_3, ... , B_N } where B_i is the collection of sets A_j that contain y_i finding this correspondence is just finding a sdr for SN. so to check the output set is valid check there is an sdr of this new collection of sets. also if we did this construction for a subset of W there would be a sdr if there is one for W

Using the module networkx for an implementation of hopcroft karp the following checks if a collection of sets (s) has an sdr

import networkx as nx

def hasSDR(s):
    x=set.union(*s)
    setnames = ["set"+str(i+1) for i in range(len(s)) ]
    B = nx.Graph()
    B.add_nodes_from( setnames , bipartite=0)
    B.add_nodes_from( x , bipartite=1)
    B.add_edges_from( [( setnames[i] , j ) for i in range(len(s)) for j in s[i] ] )
    hk = nx.bipartite.hopcroft_karp_matching(B,top_nodes=setnames)
    return all( i in hk for i in setnames )

Then we can find if an output set is valid (assuming its of the right size) with

def possibleSDRSet( s , w ):
    sn = [ { j for j in range(len(s)) if i in s[j] } for i in w ]
    return hasSDR( sn )

if this function is given w that is of size less than the number of sets in the collection it will only return false if w is subset of no valid output sets

To loop through all subsets of length n of X , and then test if they are valid output sets we could do (with a generator) (this is idea 2 in the question)

def allsets( s , req = set() ):
    if len(req) == len(s):
        if possibleSDRSet( s , req ): yield req
        return
    x = set.union(*s) - req
    if len(x) == 0: return
    xr = x.pop()
    sr = [i - {xr} for i in s]
    for i in allsets( sr , req ): yield i
    for i in allsets( s , req | {xr} ): yield i

This takes as arguments a collection of sets and a required set of elements, it then picks an element not in the required set, it then splits the search to sets without that element and sets with that element; Doing the first by making a new collection of sets with the element removed from all sets in the collection and the second by adding the element to the required set

However many of these branches may not need to be considered, when we remove an element from all the sets in the collection there may no longer be an sdr so we could check if there is still an sdr with hasSDR and only continue in that branch if there is. When we add an element to the required list possibleSDRSet may be able to rule out there being any SDRs in that branch so we could check that aswell, giving

def _findSDRSetsRec( s , req ):
    if len(req) == len(s):
        yield req
        return
    x = set.union(*s) - req
    xr = x.pop()
    sr = [ i - {xr} for i in s ]
    if hasSDR( sr ):
        for i in _findSDRSetsRec( sr , req ): yield i
    reqp = req | {xr}
    if possibleSDRSet( s , reqp ):
        for i in _findSDRSetsRec( s , reqp ): yield i

def findSDRSets(s):
    if not hasSDR(s): return
    for i in _findSDRSetsRec( s , set() ): yield i

The first of these functions assumes s and req have been checked by the two tests so there needs to be a wrapper that checks there is an sdr. Doing the example:

s = ({1,3,5,7,9,11,13,15},)*3 +({4,7,8,9,10,12},)*2 + ({1,2,5,6,7,14},)*2
for i in findSDRSets(s): print(i)

Using this method should offer a speed up over those you listed if there are only a small number of valid output sets, however the allsets method appears faster for the example given

I would probably start with a new map that has all numbers that occur in any set as keys. For each number, a list of sets that contain the number is noted. Building this takes O(n), whereas O is the total amount of distinct numbers in all sets.

You need to exhaustively find all valid solutions so there might not be much room of optimization left. The algorithm is now O(n!).

1. Go through the map recursively by making one of the valid decisions at each number (take number or not, when you take it from which set would it be). For this you keep track in your arguments how many choices per set are still left.
2. The only way to obtain duplicate solutions now is where you branch off taking a number several times, by taking it from a different set. You might further reduce that by returning information when branching off (e.g., the "take 5 (current map key) from set 3" branch returns "i also took 7, 10, 11" and you give that information to the next call "take 5 (current map key) from set 7" so it may prune.

The pruning is more complicated but doable, the question is, is it worth it. For example, you are in the "take 5 from set 7" branch and know that 7, 10, 11 are already used by another branch. You could check if the choices you still have left (e.g. now you have 3 more choices left from set 3) allow for other numbers than 7, 10, 11 by checking if set 3 still has any other number. The check for this is easy if you sort both the sets and the map according to number/key value first, because you can count the numbers higher than your current number in the set (using an ordered set!).