Question: How to search if sets in a list are subsets of another list of sets?

Hello 

I need a procedure that given two lists of sets A and returns a list of lists such that L[i] is the list of j such that A[i] subset B[j]. Here is an example:

ans6 := [{alpha[1, 8], alpha[2, 2], alpha[2, 5], alpha[2, 8], alpha[3, 6], alpha[3, 9]}, {alpha[1, 8], alpha[2, 2], alpha[2, 5], alpha[2, 8], alpha[3, 3], alpha[3, 6]}, {alpha[1, 8], alpha[2, 2], alpha[2, 5], alpha[2, 7], alpha[3, 6], alpha[3, 8]}, {alpha[1, 8], alpha[2, 2], alpha[2, 5], alpha[2, 7], alpha[3, 3], alpha[3, 8]}, {alpha[1, 8], alpha[2, 2], alpha[2, 5], alpha[2, 7], alpha[3, 3], alpha[3, 6]}, {alpha[1, 8], alpha[2, 2], alpha[2, 4], alpha[2, 5], alpha[3, 3], alpha[3, 6]}, {alpha[1, 8], alpha[2, 1], alpha[2, 2], alpha[2, 5], alpha[3, 3], alpha[3, 6]}, {alpha[1, 8], alpha[2, 0], alpha[2, 2], alpha[2, 5], alpha[3, 3], alpha[3, 6]}, {alpha[1, 5], alpha[2, 8], alpha[3, 6], alpha[3, 7], alpha[3, 8], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 5], alpha[3, 7], alpha[3, 8], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 5], alpha[3, 6], alpha[3, 8], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 5], alpha[3, 6], alpha[3, 7], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 5], alpha[3, 6], alpha[3, 7], alpha[3, 8]}, {alpha[1, 5], alpha[2, 8], alpha[3, 4], alpha[3, 7], alpha[3, 8], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 4], alpha[3, 6], alpha[3, 8], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 4], alpha[3, 6], alpha[3, 7], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 4], alpha[3, 6], alpha[3, 7], alpha[3, 8]}, {alpha[1, 5], alpha[2, 8], alpha[3, 4], alpha[3, 5], alpha[3, 8], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 4], alpha[3, 5], alpha[3, 7], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 4], alpha[3, 5], alpha[3, 7], alpha[3, 8]}]:

ans7 := [{alpha[1, 8], alpha[2, 2], alpha[2, 5], alpha[2, 7], alpha[3, 3], alpha[3, 6], alpha[3, 8]}, {alpha[1, 5], alpha[2, 8], alpha[3, 5], alpha[3, 6], alpha[3, 7], alpha[3, 8], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 4], alpha[3, 6], alpha[3, 7], alpha[3, 8], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 4], alpha[3, 5], alpha[3, 7], alpha[3, 8], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 4], alpha[3, 5], alpha[3, 6], alpha[3, 8], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 4], alpha[3, 5], alpha[3, 6], alpha[3, 7], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 4], alpha[3, 5], alpha[3, 6], alpha[3, 7], alpha[3, 8]}, {alpha[1, 5], alpha[2, 8], alpha[3, 3], alpha[3, 6], alpha[3, 7], alpha[3, 8], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 3], alpha[3, 5], alpha[3, 7], alpha[3, 8], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 3], alpha[3, 5], alpha[3, 6], alpha[3, 8], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 3], alpha[3, 5], alpha[3, 6], alpha[3, 7], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 3], alpha[3, 5], alpha[3, 6], alpha[3, 7], alpha[3, 8]}, {alpha[1, 5], alpha[2, 8], alpha[3, 3], alpha[3, 4], alpha[3, 7], alpha[3, 8], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 3], alpha[3, 4], alpha[3, 6], alpha[3, 8], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 3], alpha[3, 4], alpha[3, 6], alpha[3, 7], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 3], alpha[3, 4], alpha[3, 6], alpha[3, 7], alpha[3, 8]}, {alpha[1, 5], alpha[2, 8], alpha[3, 3], alpha[3, 4], alpha[3, 5], alpha[3, 8], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 3], alpha[3, 4], alpha[3, 5], alpha[3, 7], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 3], alpha[3, 4], alpha[3, 5], alpha[3, 7], alpha[3, 8]}, {alpha[1, 5], alpha[2, 8], alpha[3, 3], alpha[3, 4], alpha[3, 5], alpha[3, 6], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 3], alpha[3, 4], alpha[3, 5], alpha[3, 6], alpha[3, 8]}, {alpha[1, 5], alpha[2, 8], alpha[3, 3], alpha[3, 4], alpha[3, 5], alpha[3, 6], alpha[3, 7]}, {alpha[1, 5], alpha[2, 8], alpha[3, 2], alpha[3, 6], alpha[3, 7], alpha[3, 8], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 2], alpha[3, 5], alpha[3, 7], alpha[3, 8], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 2], alpha[3, 5], alpha[3, 6], alpha[3, 8], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 2], alpha[3, 5], alpha[3, 6], alpha[3, 7], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 2], alpha[3, 5], alpha[3, 6], alpha[3, 7], alpha[3, 8]}, {alpha[1, 5], alpha[2, 8], alpha[3, 2], alpha[3, 4], alpha[3, 7], alpha[3, 8], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 2], alpha[3, 4], alpha[3, 6], alpha[3, 8], alpha[3, 9]}, {alpha[1, 5], alpha[2, 8], alpha[3, 2], alpha[3, 4], alpha[3, 6], alpha[3, 7], alpha[3, 9]}]:

and my procedure

SubsetPairs:= (A::list(set), B::list(set))->
    map(z-> [ListTools:-SearchAll](true, map(w-> z subset w, B)), A)
:
SubsetPairs(ans6, ans7);

The result of applying SubsetPairs is:

[[], [], [1], [1], [1], [], [], [], [2, 3, 8, 23], [2, 4, 9, 24], [2, 5, 10, 25], [2, 6, 11, 26], [2, 7, 12, 27], [3, 4, 13, 28], [3, 5, 14, 29], [3, 6, 15, 30], [3, 7, 16], [4, 5, 17], [4, 6, 18], [4, 7, 19]]

When it is used for long lists, it takes a long time to return the results.  I wonder if a more time- and memory-efficient code can be implemented (perhaps Threads or Grid can be used).

In addition to that, how can a diagram (figure, plot, ...) be drawn to show which subset of the first list is linked to which subsets of the second list (including no link as well).  The length of the first list is always smaller than the length of the second list.  

Many thanks

 

Please Wait...