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 -- http://mail.python.org/mailman/listinfo/python-list