On 3/30/13 4:56 PM, Gary McConnell wrote:
OK so thinking about it, even though your code is beautifully compact
and elegant, I think I am going to have to revert a little to the
"outer-inner-loop" structure in order to achieve what I need. Namely,
instead of storing "used" vectors, I store "used" bases and search
through the remaining orthogonal sets exhaustively. Otherwise I cannot
get at the bases which may share a vector with another basis but have
different "xRy" properties. I am trying to program this now - please
feel free to tell me a better way!!
Not a problem. I was hoping my code was a good starting off point to
rethinking the problem. I was playing with a way to just have a
function that generated all possible orthogonal sets of d vectors each,
and then you could test your relationship for all of them in all
possible ways. Maybe that's the best thing.
However, maybe at this point it would be good to ask on, say,
sage-combinat mailing list. You have a very combinatorial problem here,
and they have lots of tools for enumerating sets with various
constraints. For example, looking at
http://www.sagemath.org/doc/reference/combinat/sage/combinat/backtrack.html,
you could use SearchForest to implement your "find all independent sets
of size d" pretty easily. The roots would be the list of singletons,
and the children of a list could be found by:
* if the list has d elements in it, it has no children
* if the list has less than k<d elements in it, then you return all
lists of size k+1 where you basically append all vectors that are
orthogonal to all the things in your list.
* to make this efficient, you want to iterate through your vectors in
some sort of order, and then only test and add vectors that are ordered
past your last vector in your current list.
For example:
V=FiniteField(3)^4
L = list(V)
d=9
def find_children(node):
if len(node)==d:
return []
node_position = L.index(node[-1])
if len(node)+len(L)-node_position < d:
# not enough elements to finish off the list
return []
children = []
# find the last element
for v in L[L.index(node[-1])+1:]:
if all(v*w==0 for w in node):
children.append(node+[v])
return children
def post_process(node):
# only output nodes with the right length
if len(node)==d:
return node
else:
return None
s=SearchForest(roots=[[v] for v in L], children=find_children,
post_process = post_process,
category=FiniteEnumeratedSets())
# mutually orthogonal sets of size 9
A=list(s.depth_first_search_iterator())
print len(A)
print A
(see http://sagecell.sagemath.org/?q=e2a9c6b7-bb0c-40e6-9081-3609aaa3227f)
Anyway, s.depth_first_search_iterator() gives an iterator over all
independent sets of size d. Now you can test for your relations between
the independent sets. In fact, you could set up another SearchForest
for that too :). The nice thing about SearchForest is that it takes
care of all the pruning and other things for you. You can do
breadth-first or depth-first searches in it, etc.
Another way to think about your problem is: you have a graph with
vertices = vectors in N1, where two vectors are connected if their dot
product is nonzero. You're trying to find a list of M mutually
exclusive independent sets of size d, where the independent sets must
also satisfy some relationship relative to each other. Of course, you
could also take the complement and look for cliques. The combinat
people might have already implemented fast searching for independent
sets, etc.
Feel free to share your code with us; we might be able to give you
further pointers. It'd also be fun to see where this research is headed
(e.g., a link to a paper), if it's appropriate. It'd be cool to see
another paper in the Sage library links:
http://www.sagemath.org/library-publications.html
Thanks,
Jason
--
You received this message because you are subscribed to the Google Groups
"sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
