[Tutor] Creating lists with 3 (later4) items occuring only once

Martin A. Brown martin at linux-ip.net
Sat Sep 26 19:37:53 CEST 2015


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/


More information about the Tutor mailing list