overlapping sets

[kpp9c]

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]

[Adam DePrince]

Re: overlapping sets

On Thu, 2006-03-23 at 22:55 -0800, kpp9c wrote:[color=blue]
> 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 ] }[/color]

Look at this from the perspective of a graph.

Draw on paper your collections. Circle them. Those are your nodes.
Now draw a line between nodes that are "compatable " in the way you
describe.

You can use a dict to represent a graph.

If I have this graph:

A - B
B - C
A - C
C - D

then

{'A':'BC', # Remember, strings are sequences in their own right, I'm too
lazy to write ['B','C']
'B':'AC',
'C':'ABD' }

You are going to do the same. Just make your lists tuples instead,
lists can't be dict keys. Now, lookup your current node in your dict
and you will get your neighboors. Use random.choice to pick one, and
move on.

I don't know what the ('eight'), ('nine') keys are all about, but your
biggest impediment is how you are looking at the problem.

For reference http://www.python.org/doc/essays/graphs.html

As for detecting neighboors, sure that's easy, but first you have to try
to use a for loop first on your own to tell how many positional items
any two lists differ by.

Cheers and good luck - Adam DePrince

[Michael Spencer]

Re: overlapping sets

kpp9c wrote:[color=blue]
> 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]
>[/color]
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)==neigh bor_len]
return graph


def walk_nodes(node s, walk_length = None):
if walk_length is None:
walk_length = len(nodes)
graph = get_graph(nodes )
def add_move(histor y):
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_leng th-1):
history = add_move(histor y)
# 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:
[color=blue][color=green][color=darkred]
>>> list(walk_nodes (nodes))[/color][/color][/color]
[]

But there are a couple of 7-node paths:[color=blue][color=green][color=darkred]
>>> list(walk_nodes (nodes,7))[/color][/color][/color]
[[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])]][color=blue][color=green][color=darkred]
>>>[/color][/color][/color]

HTH, Michael

[Gerard Flanagan]

Re: overlapping sets

kpp9c wrote:
[color=blue]
> 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.
>[/color]

probably not very efficient but I think it roughly does what you want.
(maybe add a boolean 'sort' parameter, to select sorted output or not):

# k is the length of the required output lists, 0<k<n
# n is the number of lists to output

import random

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

def randomiser( a_list, n, k ):
d = len( a_list )
choice = range(d)
vector = []
for i in range(k):
vector.append( choice.pop(rand om.randint(0,d-i-1)) )
yield [ a_list[s] for s in vector ]
#yield sorted( a_list[s] for s in vector )
for _ in range(n):
rand_vector_idx = random.randint( 0,k-1)
rand_choice_idx = random.randint( 0,d-k-1)
rand_vector_val = vector[rand_vector_idx] #remember old value
vector[rand_vector_idx] = choice.pop( rand_choice_idx )
choice.append( rand_vector_val ) #add old value back to choice
yield [ a_list[t] for t in vector ]
#yield sorted( a_list[t] for t in vector )

print
for item in randomiser(alph abet, 10, 4):
print item

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

Gerard

[Gerard Flanagan]

Re: overlapping sets

Gerard Flanagan wrote:
[color=blue]
> kpp9c wrote:
>[color=green]
> > 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[/color][/color]
[color=blue]
>
> # k is the length of the required output lists, 0<k<n
> # n is the number of lists to output
>
> import random
>
> alphabet = [ 0, 3, 4, 5, 6, 7, 8, 9, 10, 11 ]
>
> def randomiser( a_list, n, k ):
> d = len( a_list )
> choice = range(d)
> vector = []
> for i in range(k):
> vector.append( choice.pop(rand om.randint(0,d-i-1)) )
> yield [ a_list[s] for s in vector ]
> #yield sorted( a_list[s] for s in vector )
> for _ in range(n):
> rand_vector_idx = random.randint( 0,k-1)
> rand_choice_idx = random.randint( 0,d-k-1)
> rand_vector_val = vector[rand_vector_idx] #remember old value
> vector[rand_vector_idx] = choice.pop( rand_choice_idx )
> choice.append( rand_vector_val ) #add old value back to choice
> yield [ a_list[t] for t in vector ]
> #yield sorted( a_list[t] for t in vector )
>[/color]


Sorry, I realise this doesn't answer your question - it is the
collections themselves which are your 'alphabet', not the set of their
elements. Looks like it's Graph Theory for you!

Apologies.

Gerard

[Lonnie Princehouse]

Re: overlapping sets

There is a sets.Set class built in to Python. You might want to use
this instead of lists. It defines some handy set operations like
intersection, union, and so on.

from sets import Set

my_sets = {
'one' : Set([0,4,7,9]),
'two' : Set([0,3,7,9]),
etc...
}

[Alex Martelli]

Re: overlapping sets

Lonnie Princehouse <finite.automat on@gmail.com> wrote:
[color=blue]
> There is a sets.Set class built in to Python. You might want to use[/color]

In 2.4, there's also a set builtin type -- you can keep using the sets
module from the standard library, but the built-in set is faster.

If you need compatibility with both 2.3 and 2.4, getting the best set
implementation available in each case, the common idiom is:

try:
set
except NameError:
from sets import Set as set

The interface to use the set type/class is the same in either case.


Alex