[Tutor] Creating lists with 3 (later4) items occuring only once
marcus lütolf
marcus.luetolf at bluewin.ch
Sun Sep 27 13:39:02 CEST 2015
Hello Martin.
I never exspected to get such motivating comments and advice !!! Thank you
again.
Referring to my statments below
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.
2. I considered ['a +b', 'a + c', 'b+c'] == ['a','b','c']
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. 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.
That is why I limited my samples to 9 and 15. 5 and 7 would not work since
ther are prime numbers.
The posting of your sample with 5 letters below is correct. 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. That made me think itertools might
not be the right tool.
However, I noticed variance gets smaller with bigger samples and might turn
0 with 24 letters.
But I don't know how to eliminate the "already seen's" by code.
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 ?
Have a sunny Sunday, Marcus.
----------------------------------------------------------------------------
----------------------------------------------------------------------------
----
-----Ursprüngliche Nachricht-----
Von: Martin A. Brown [mailto:martin at linux-ip.net]
Gesendet: Samstag, 26. September 2015 19:38
An: marcus lütolf <marcus.luetolf at bluewin.ch>
Cc: tutor at python.org
Betreff: Re: AW: [Tutor] Creating lists with 3 (later4) items occuring only
once
Good morning(PDT)/evening(CET) Marcus,
> again thanks for your endeavour, ist tought me to really think deeply
> how to specify my task fort he Python language.
> Before I start to work with your "heavy" piece of code for a beginner
> below I like to make the following statements:
>
> 1. my task is to create lists or tupleS (whichever works best)
> containing 3 letters, later to be assigned names, in unique sequences.
OK. So, your second round of postings was closer to the actual problem you
are trying to solve. And, now, it's clear to me that you are operating with
triples.
You are doing something with pairs, but I don't understand what.
See below.
> 2. My first approach with pairs like 'a b', 'a c',..... does not work
with
> itertools.combinations(s, 3): Although, it produces lists/tuples with
3
> pairs
> there are 4 letters in each list/tuple whereas I need only 3.
Understood.
> 3. Therfore, I'am working with single letters creating lists/tuples
> with 3
> letters: ('a', 'b', 'c'), ('a','b','d')........
> Using all 26 letters of the alphabet would correspond to Problem A:
> Impossible to handle.
Not impossible, at all. And, in fact, here is a wonderful point.
If you can describe the problem using a small sample and capture all of the
rules of your system (or model), then you can write a program to solve that
problem. Professional programmers often use small data samples like this to
test the validity of their code, before running the code on a larger input
data set.
Also, it sounds like you want to solve problem A, which is to enumerate (or
simply find the size of) the result set in this system you are constructing.
> Using only 15 letters would already create 455 lists/tuples.
> The 9 letters produce 84 lists/tuples.
Confirmed:
>>> len(list(itertools.combinations(string.ascii_lowercase[:9], 3)))
84
>>> len(list(itertools.combinations(string.ascii_lowercase[:15], 3)))
455
> So I am using 9 letters which is practical for one letter or name can
> be combined with 2 others 5 times or on 5 days, each letter/name can
> occur only once a day.
>
> But if I am isolating lists/tuple with unique sequences by hand
It is precisely here that I (and probably the others on this mailing
list) do not understand what you are trying to accomplish. What are the
rules that you are using for 'isolating lists with unique sequences'? It
sounds like something with subsequences.
I'm going to make a stab at writing down the rules I think you may be using.
I will probably be wrong. Please correct me.
As noted above, I'm going to use a very small sample, using an "alphabet" of
5 letters. I'm taking a stab at the rules in your system and writing down.
Could you correct and/or explain whether I have understood what you are
doing?
[
('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') # keep
]
Now, some additional, more general, comments....
> 4. I have come to the conclusion that my task is too mathematical for
> itertools.
It's possible that itertools may not have the tools exactly that you are
looking for, but several of us suggested it because there seems to be some
part of your problem that can be satisfied by the module. Maybe you need
some other algorithm or module.
I'll make an analogy. When you are building a house, you use many different
sorts of tools and materials. Though programming involves no tangible
result, there are many tools and techniques you can apply. Which sort of
tool we might recommend depends on what sort of house you want to build. Do
you want to build a house of stone, brick or wood? With curved railings?
Clear or stained glass windows?
We can help you by suggesting things like Python's itertools or other
modules. We can suggest alternate approaches or algorithms.
We can also help with the technical implementation (i.e. what does the code
look like), but we can only help if the problem is clearly understood.
Some of us can even help with the mathematical part of the problem (I, less
so than some of the others on this list).
Understanding the problem, though, is the beginning of the process of
writing software.
I will reproduce your wonderfully relevant comment:
> [taught] me to really think deeply how to specify my task [for
> the] Python language.
You will always benefit from thinking deeply about what you hope to
accomplish before starting to code. (I have known quite a few programmers
with decades of experience who will not touch the computer until they have
written a description of the problem on
paper.)
Also: There is no shame in writing code and throwing it away if it helps
you get closer to the solution. It's common (and a good idea) to throw away
code.
> I hope I can be successfull with your code below although it will me
> take time to comprehend it.
Don't worry unduly about my code. Note that it solves Problem B, providing
one possible example. This appears not to be what you want. It will not
enumerate all possible examples.
Good luck and enjoy the remainder of your weekend, Marcus,
-Martin
> -----Ursprüngliche Nachricht-----
> Von: Martin A. Brown [mailto:martin at linux-ip.net]
> Gesendet: Dienstag, 22. September 2015 03:10
> An: marcus lütolf <marcus.luetolf at bluewin.ch>
> Cc: tutor at python.org
> Betreff: Re: [Tutor] Creating lists with 3 (later4) items occuring
> only once
>
>
> Marcus,
>
> I have more questions for you, as well as a possible solution (though
> it's a bit more verbose than I would have liked to offer).
>
> Question:
>
> Problem A: Are you looking to identify the complete set of
> possible options for constructing the triples of pairs?
>
> Problem B: Are you looking only to construct one set that
> satisfies the problem? [see my lousy solution]
>
> You may observe that the question I ask is quite similar to the
> question asked by Francesco [0].
>
> If you are asking about the complete set of possible options (Problem
> A), then I submit to you that you are asking a mathematical question,
> not a Python question. If that's the case, perhaps you should look
> further into the Steiner system and/or ask again on the list.
>
> If you are asking about finding an individual solution satisfying the
> constraints, I submit to you that either my approach or Francesco's
> approach could work for you. If that's the case, then using
> random.sample may offer you some help. See my sample, below--it
> should work on Python 2.x or Python 3.x.
>
> Comments:
>
> * There are rules in your system about when a player can play
> again. The rules were not fully clear to me, so I allowed
> players to be selecteda second time, if there were no more
> players who had not already been chosen.
>
> * This program produces only one possible scenario for 7
> rounds of 3 distinct, simultaneously played 2-player games.
> No player can play twice in the same round. (Simple arithmetic
> determines the minimum number of players.)
>
> If your question is Problem A, then I wonder if you know anybody who
> knows combinatorics? I do not.
>
> -Martin
>
> [0]
> https://mail.python.org/pipermail/tutor/2015-September/106820.html
>
>
> #! /usr/bin/python
>
> from __future__ import print_function
>
> import sys
> import string
> import random
> import logging
>
> logging.basicConfig(stream=sys.stderr, level=logging.INFO) logger =
> logging.getLogger()
>
>
> class NotEnoughPlayers(Exception):
> pass
>
>
> def choose_game_participants(players, pcount=2):
> '''returns a tuple of players for a single game
> '''
> if len(players) < pcount:
> raise NotEnoughPlayers("not enough players, need %d, have only %d:
> %r" %
> (pcount, len(players), players))
> game = tuple(sorted(random.sample(players, pcount)))
> return game
>
>
> def choose_match_games(players, pcount=2, gcount=3):
> '''returns a list of games where no player is duplicated
> '''
> mcount = pcount * gcount
> if len(players) < mcount:
> raise NotEnoughPlayers("not enough players, need %d, have only %d:
> %r" %
> (mcount, len(players), players))
> eligible_players = random.sample(players, mcount)
> match = list()
> while eligible_players:
> m = choose_game_participants(eligible_players, pcount)
> for x in m:
> eligible_players.remove(x)
> match.append(m)
> match.sort() # optional
> return match
>
>
> def generate_rounds(players, pcount, gcount, rcount):
> games = set()
> matches = list()
> mcount = pcount * gcount
> eligible_players = list(players)
> if mcount > len(eligible_players):
> raise NotEnoughPlayers("not enough players (%d) to guarantee
> %d %d-player games per match" %
> (len(eligible_players), gcount, pcount))
> r = 1
> while r <= rcount:
> try:
> proposed_match = choose_match_games(eligible_players,
> pcount,
> gcount)
> except NotEnoughPlayers:
> logger.info("adding %d additional players in round %d to
> meet minimum pool requirements",
> mcount, r)
> how_many = mcount - len(eligible_players)
> eligible_players.extend(random.sample(players, how_many))
> continue
> already_played = games.intersection(set(proposed_match))
> if already_played:
> logger.info("discarding %d %r because %r have already played",
> r, proposed_match, list(already_played))
> continue
> else:
> games.update(proposed_match)
> matches.append(proposed_match)
> logger.info('Proposed match %r', proposed_match)
> for game in proposed_match:
> for player in game:
> eligible_players.remove(player)
> r = r + 1
> return matches
>
>
> def log_match_info(matches, detail=False):
> for mnum, match in enumerate(matches, 1):
> logger.info("match summary %d: %r", mnum, match)
> for gnum, game in enumerate(match, 1):
> if not detail:
> continue
> logger.info("match detail %d, game %d: players %r",
> mnum, gnum, game)
>
>
> def log_match_summary(matches):
> log_match_info(matches, detail=False)
>
>
> def log_match_detail(matches):
> log_match_info(matches, detail=True)
>
>
> if __name__ == '__main__':
> players = list(string.ascii_uppercase)
> random.shuffle(players)
> # players = set('ABCDEFGHIJ')
> pcount = 2 # players per game
> gcount = 3 # games per match
> rcount = 7 # rounds (of matches)
> matches = generate_rounds(players, pcount, gcount, rcount)
> log_match_detail(matches)
>
> # -- end of file
>
>
> --
> Martin A. Brown
> http://linux-ip.net/
>
>
> ---
> Diese E-Mail wurde von Avast Antivirus-Software auf Viren geprüft.
> https://www.avast.com/antivirus
>
>
>
--
Martin A. Brown
http://linux-ip.net/
---
Diese E-Mail wurde von Avast Antivirus-Software auf Viren geprüft.
https://www.avast.com/antivirus
More information about the Tutor
mailing list