Hello Marcus,
I never exspected to get such motivating comments and advice !!!
Thank you again.
Much appreciated! Each of us contributes to this mailing list in
some way or another. And, not a one of us sprang fully-formed from
Zeus's head with our Python expertise.
1. I explain my task in plain text:
Flights (in golfers language) or Triples (in computer language) composed of
3 golfers (in golfers language) or 3 letters (in
computer language) play once a day for n days.
Each golfer or letter should only once be combined with another, meaning a
combination of 2 golfers/letters should never
be >1 for n days.
OK, so this certainly appears to be the social golfer problem or
some similar variant.
I had never heard of it before your posting and it is not a problem
space I'm familiar with. Earlier, people pointed out the similarity
of the Steiner triple system and Kirkman's schoolgirl problem. I
think this is where you should study now. I suspect that you would
benefit more from talking to somebody who knows combinatorics and/or
this particular problem.
In particular, I think the closest already-proposed partial solution
to your problem was from Marc Tompkins. You might have a second
look at that and see what you make of it:
https://mail.python.org/pipermail/tutor/2015-September/106695.html
I also find myself asking the same question Marc asked at the end of
his posting: How confident are you about the number 301?
2. I considered ['a +b', 'a + c', 'b+c'] == ['a','b','c']
This is a combination. So, for example, for this very small part of
your problem:
>>> list(itertools.combinations(('a','b','c'), 2))
[('a', 'b'), ('a', 'c'), ('b', 'c')]
Now, you need to figure out how to keep the stuff you want and pitch
the duplicates.
3. I'am glad that it can be done with all letters. However, with
Triples I need a number dividable by 3 so the maximum would be 24
golfers or letters.
That is why I limited my samples to 9 and 15. 5 and 7 would not
work since ther are prime numbers.
I hope to get a program allowing to change the varables like
number of days played(n) and number of golfers/letters, up to a
max of 24 according to different situations.
Here's how I would accomplish the second part (this is an
implementation suggestion only):
import sys
import string
if __name__ == '__main__':
try:
alphalength = int(sys.argv[1])
except IndexError:
alphalength = 5
alphabet = string.ascii_letters[:alphalength]
result = compute_solution(alphabet)
# -- print result or summary stats on result
You would still have to write the computation to solve your problem
and apply all the constraints you wish to apply.
Now, the part that I have not done anything with is the matter of
days played.
The posting of your sample with 5 letters below is correct.
I goofed in my generation of the list. After writing a bit of code
to try it out, I see that the last item in the list below, ('c',
'd', 'e'), should have been discarded because pair ('c', 'd') was
already seen.
[
('a', 'b', 'c'), # keep
('a', 'b', 'd'), # discard; subsequence ('a', 'b') already seen
('a', 'b', 'e'), # discard; subsequence ('a', 'b') already seen
('a', 'c', 'd'), # keep
('a', 'c', 'e'), # discard; subsequence ('a', 'c') already seen
('a', 'd', 'e'), # keep
('b', 'c', 'd'), # discard; subsequences ('b', 'c') and ('c', 'd') already
seen
('b', 'c', 'e'), # discard; subsequence ('b', 'c') already seen
('b', 'd', 'e'), # discard; subsequence ('b', 'd') already seen
('c', 'd', 'e') # discard: subsequenc ('c', 'd') already seen
]
That made me think itertools might not be the right tool.
It can be part of the solution. See above (and below). Of course,
it's not the whole solution--that's your challenge, isn't it?
Here are the parts of the problem with which itertools can help you.
#1: It can generate the list of possible triples for you:
itertools.combinations('abcde', 3)
#2: From each triple, it can generate the pairs:
itertools.combinations(('a', 'b', 'c'), 2)
Having discarded
the subsequences with "already seen's"
4 Triples/sequences are left but a variance of the contained letters:
'a' occurs 3 times
'b' occurs 1 time
'c' occurs 3 times
'd' occurs 3 times
'e' occurs 2 times
which of course does not fit my task.
However, I noticed variance gets smaller with bigger samples and might turn
0 with 24 letters.
The variance decrease seems nifty.
But I don't know how to eliminate the "already seen's" by code.
Ah-ha! Well, see Marc Tompkins' code for an example of tracking
"already seen" pairs. Here's a generic technique that will work for
identifying "already seen", but tailored for your problem.
# assume a single triple, for example
triple = ('a', 'b', 'c')
gen_pairs = lambda x: itertools.combinations(x, 2)
already_seen = set()
for pair in gen_pairs(triple):
already_seen.add(pair)
# after the loop completes, you should have:
# already_seen = {('a', 'b'), ('a', 'c'), ('b', 'c')}
You can then, later, test to see if the pair(s) are in the
already_seen set.
You are absolutely right that one has to write down first exactly his task
to be accomplished. But my knowledge goes only
as far as "Python for Infomatics" (by MOOC/Coursera) and "Practical
Programming" . I know there are a myriad of other
modules and tools etc. and there I need the help of "Pythonistas".
To where should I proceed now ?
I would suggest the following:
* write down the problem as you understand it
* write code to solve the problem
* find a shortcoming in the code (or your description of the problem)
* try to fix the problem description or the code
- if success, pat yourself on the back and drink a beer (or whatever)
- if failure, send the smallest possible relevant problem description and
code
to the Python tutor list and we will try to help
While this has been a bit of a fun problem and learning experience
for me, I am going to stop posting on this thread. I lack
sufficient experience in combinatorics to guide you in thinking
properly (and clearly) about this problem and that is where you are
stuck at the moment. Sorry I can't help you much further.
Good luck, Marcus,
-Martin
--
Martin A. Brown
http://linux-ip.net/
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
