overlapping sets

[Michael Spencer]

kpp9c wrote:
> I have a question... and ... whew ... i am gonna be honest, i haven't
> the slightest clue how to even start ... i am not sure if i used up all
> my good will here or can take a mulligan.. i love to try to at least
> post some lame broken code of my own at first... but like i said, not
> being a math person i am not even sure how to start or if it is even
> possible.
> 
> here's the deal... i have a dictionary that defines some collections..
> like so:
> 
> sets = { ('one') : [0, 4, 7, 9 ],
> ('two') : [0, 3, 7, 9 ],
> ('three') : [0, 4, 7, 11],
> ('four') : [0, 3, 7, 10 ],
> ('five') : [0, 4, 7, 10 ],
> ('six') : [0, 4, 8, 10 ],
> ('seven') : [0, 3, 6, 10],
> ('eight') : [0, 3, 6, 9 ],
> ('nine') : [0, 3, 7, 11 ],
> ('ten') : [0, 5, 7, 10 ] }
> 
> I every time i call this function i would like like it to return a
> collection at random, any collection, so long as it has all but one
> element that is the same. So if i grab [0, 4, 7, 9 ] as my first set
> my next set could be: [0, 3, 7, 9 ], or [0, 4, 8, 9 ], or [0, 4, 7,
> 10], or [1, 4, 7, 9 ], since all these sets contain 3 elements in
> common with the first, and only one that is new or different... but if
> my first run give me: [0, 4, 7, 9 ] i would not get [0, 5, 7, 10 ],
> since this is set has 2 elements that are unique. The goal it to move
> from set to set to set to set always with a maximum of overlap & common
> elements.
> 
> I wonder, if this is even possible, *and* if it can be done with sets
> that have as many as 7, 8, or even 9 elements or if this would be too
> slow to even attempt.
> 
> cheers,
> 
> kp8
> 
> [for the record using python 2.3 on a macintosh at the moment]
> 
Here's an example of a possible approach.  It uses a naive search algorithm, but 
it should illustrate the general idea:

# Search for a path through the nodes that changes only one member per step

nodes = [[0, 3, 6, 10], [0, 5, 7, 10], [0, 3, 7, 11], [0, 4, 8, 10],
[0, 4, 7, 11], [0, 3, 7, 9], [0, 3, 7, 10], [0, 4, 7, 10], [0, 3, 6, 9],
[0, 4, 7, 9]]

try:
     frozenset
except NameError: # 2.3 compatibility, untested
     from sets import ImmutableSet as frozenset

def get_graph(nodes):
     """From a list of sequences, return a graph, mapping each node to its
     neighbors - defined as nodes with all but one common element"""

     graph = dict.fromkeys([frozenset(s) for s in nodes])
     for s in graph:
         neighbor_len = len(s)-1
         graph[s] = [t for t in graph if len(s&t)==neighbor_len]
     return graph


def walk_nodes(nodes, walk_length = None):
     if walk_length is None:
         walk_length = len(nodes)
     graph = get_graph(nodes)
     def add_move(history):
         for path in history:
             last_move = path[-1]
             # remove the last_move from the graph: we can't go there again
             possible_next = graph.pop(last_move)
             # look in sequence at the possible neighbors
             # this is a naive - a better heuristic would perhaps be to
             # visit neighbors with fewer exits first
             for next in possible_next:
                 if next in graph:
                     # if the node is still in the paths dict, we haven't
                     # visited it yet, so let's go
                     yield path + [next]

     # Pick a starting point - naive!
     history = [graph.keys()[0]],
     # set up n nested generators, each representing one move depth
     for move in range(walk_length-1):
         history = add_move(history)
     # yield a generator of all paths through the graph of length walk_length
     # by trial and error, you can find the longest path
     return history



Apparently, there is no path through all 10 nodes:

 >>> list(walk_nodes(nodes))
[]

But there are a couple of 7-node paths:
 >>> list(walk_nodes(nodes,7))
[[frozenset([0, 9, 3, 6]), frozenset([0, 9, 3, 7]), frozenset([0, 11, 3, 7]), 
frozenset([0, 11, 4, 7]), frozenset([0, 10, 4, 7]), frozenset([0, 10, 3, 7]), 
frozenset([0, 10, 3, 6])],
[frozenset([0, 9, 3, 6]), frozenset([0, 9, 3, 7]), frozenset([0, 11, 3, 7]), 
frozenset([0, 11, 4, 7]), frozenset([0, 10, 4, 7]), frozenset([0, 10, 3, 7]), 
frozenset([0, 10, 5, 7])]]
 >>>

HTH, Michael