subsets with condition

given a collection say ([(0, 1), (0, 2), (0, 4), (3, 5)],[(0, 1), (0, 2), (0, 5), (3, 4)],[(0, 1), (0, 4), (0, 5), (2, 3)],[(0, 2), (0, 4), (0, 5), (1, 3)],[(0, 1), (1, 2), (1, 5), (3, 4)] }

How to obtain subset or sub collection say size 3 or as specified by user such that intersection between (first internal set and second internal set) is one set and (first internal set and Third internal set) is zero sets ,(second internal set and Third internal set) is one set . That is like ([(0, 1), (0, 2), (0, 4), (3, 5)],[(0, 1), (1, 3), (1, 5), (2, 4)],[(0, 4), (1, 3), (2, 5),(4,5)]

The number of intersection between sets in each to be specified by user. How to do without enumerating all subsets any hint.

edit retag close merge delete

You have overposted/spammed. Please don't do this.

( 2010-09-18 12:19:36 +0200 )edit

Do you want the number of duplicates, repetition of duplicates, or number of edges of intersection between sets?

Is your definition of set the normal one, where no duplicate is contained within the same set?

( 2010-09-18 12:35:07 +0200 )edit

You can create a set out of a list L with S = set(L). It will eliminate duplicates, and ignore the order. (You see the set elements sorted.) The set S has methods that impliment various set-theoretic operations. Type S.<tab> to see possibilities, such as S.intersect(T) which returns a the intersection of sets S and T.

( 2011-03-30 21:36:28 +0200 )edit

Sort by » oldest newest most voted

It seems to be not fully implemented in Sage and would be hard in general.

The first thing to do is to compute the intersection matrix of your collection as in the following code (I named S the collection).

sage: S = [Set([0, 1, 3, 7]),
...        Set([0, 5, 4, 6]),
...        Set([0, 8, 4, 7]),
...        Set([0, 8, 5, 9]),
...        Set([8, 5, 4, 2]),
...        Set([2, 3, 5, 6]),
...        Set([3, 6, 7, 8])]
sage: n = len(S)
sage: m = matrix(n)
sage: for i in xrange(n):
...      for j in xrange(n):
...          m[i,j] = S[i].intersection(S[j]).cardinality()


Let consider the graph G associated to the matrix (see wikipedia graph theory) where I put labels on edges instead of multiedges.

sage: G = Graph()
sage: for i in xrange(n):
...      for j in xrange(i):


Now, what you're looking for is a subgraph H (your intersection conditions) of your graph G. The question would be equivalent to a variation of the subgraph isomorphism problem and the induced subgraph isomorphism problem. The variation comes from the fact that your graphs G and H have some integer label on edges (or multiplicity of edges) and you are looking for a copy of H in G as labeled graphs... In any case, such a problem is NP-complete in general, meaning that a fast algorithm would be impossible to design. Depending on your intersection conditions (in your question H is just a cyclic graph) it may be better.

There is a brute force way to do subgraph search in Sage with subgraph_search but it does not handle your case. It is possible to modify slightly the code of subgraph_search in order to make it work in your case... I created a ticket for that trac #13280 hoping it will be available in the next release of Sage ;-)

With the patch applied, I get the following answer

sage: H = Graph()
sage: for s in G.search_subgraph_iterator(H, edge_labels=True):
....:     print s
[0, 2, 1]
[0, 2 ,3]
...
[6, 5, 4]


Then you can check that all those sub collections are answer to the question. As an example, I consider the first solution [0,2,1]

sage: S[0].intersection(S[2]).cardinality()
2
sage: S[0].intersection(S[1]).cardinality()
1
sage: S[2].intersection(S[1]).cardinality()
2

more