[EMAIL PROTECTED] writes: > dear pythonistas, > > So imagine that we have a set of sets S. If we pick arbitrarily one > set, s0, what are all the combinations of other sets in S which when > combined by set operations result in s0? > > s0 = set([1]) > s1 = set([1,2]) > s2 = set([2]) > S = set([s0,s1,s2]) > one answer we're searching for is s0 = s1 - s2 > > There may be arbitrarily many set elements (denoted by integers > 1,2,3,...) and arbitrarily many combinations of the elements composing > the sets s_i (s0, s1, ...). We can use any operation or function which > takes and returns sets. > > I think this problem is related to integer partitioning, but it's not > quite the same. The range of answers has a little combinatorial > explosion problem as S gains new members. In my problem, len(S) is > usually on the order of 1M, and in the worst case, 10M, and there are > on the order of 10k elements. > > My attempts to come up with an algorithm have not succeeded. Any ideas > occur to you folks? -- PB.
Unless your sets have some sort of pattern, it sounds to me like this problem is at least exponential... Good luck! -- Arnaud -- http://mail.python.org/mailman/listinfo/python-list
