# overlapping sets

Michael Spencer mahs at telcopartners.com
Fri Mar 24 09:36:57 CET 2006

```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)
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):
# 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

```