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] 6 1912
On Thu, 20060323 at 22:55 0800, 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 ] }
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
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_length1):
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 7node 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
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.
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(random.randint(0,di1)) )
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,k1)
rand_choice_idx = random.randint(0,dk1)
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(alphabet, 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 wrote: 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 # 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(random.randint(0,di1)) ) 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,k1) rand_choice_idx = random.randint(0,dk1) 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 )
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
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...
}
Lonnie Princehouse <fi**************@gmail.com> wrote: There is a sets.Set class built in to Python. You might want to use
In 2.4, there's also a set builtin type  you can keep using the sets
module from the standard library, but the builtin 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 This discussion thread is closed Replies have been disabled for this discussion. Similar topics
1 post
views
Thread by André Søreng 
last post: by

11 posts
views
Thread by Max M 
last post: by

3 posts
views
Thread by Phil Sandler 
last post: by

2 posts
views
Thread by Catherine Lynn Wood 
last post: by

reply
views
Thread by Bruce 
last post: by

4 posts
views
Thread by Charlie Brown 
last post: by

4 posts
views
Thread by =?ISO885915?Q?Jean=2DFran=E7ois?= Lemaire 
last post: by

5 posts
views
Thread by zacks 
last post: by
           