Problem : Given a Set A of 3 sets each set inside Set A contains 2-literal subsets ,find how many unique 3-literal set we can make by selecting exactly one subset from each set such that all the selected elements are all possible subsets of this 3-literal set.

Example : { {ad ,bb} ,{ac ,ad ,bc} ,{bc ,dd} } for  this specific set ,then number of unique 3-literal set is 2 :

1. (a,d,d)-> (ad ,ad ,dd)
2. (b,b,c)-> (bb ,bc ,bc)

Does there exist a efficient algorithm for this and can we extend it to k-literal set ,i.e given a set of k(k-1)/2 sets ,can we select exactly one subset from each of these set such that it forms a k-literal set.

By `k-literal Set` ,I mean ,A set that contains k variables ,and question above is asking the number of ways we can select elements from each set such that those chosen elements are the all possible 2-subsets of a K-literal set .


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.