Ask Your Question
0

subsets with condition

asked 2010-09-18 02:37:03 -0500

sriram gravatar image

updated 2011-04-28 09:23:16 -0500

Kelvin Li gravatar image

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 flag offensive close merge delete

Comments

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

ccanonc gravatar imageccanonc ( 2010-09-18 05:19:36 -0500 )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?

ccanonc gravatar imageccanonc ( 2010-09-18 05:35:07 -0500 )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.

Sammy Black gravatar imageSammy Black ( 2011-03-30 14:36:28 -0500 )edit

1 answer

Sort by ยป oldest newest most voted
0

answered 2012-07-20 22:44:30 -0500

updated 2012-07-21 03:03:05 -0500

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):
...         G.add_edge(i,j,m[i,j])

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: H.add_edge(1,2,2)
sage: H.add_edge(1,3,1)
sage: H.add_edge(2,3,2)
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
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2010-09-18 02:37:03 -0500

Seen: 249 times

Last updated: Jul 21 '12