[Tutor] problem solving with lists

dn PythonList at DancesWithMice.info
Mon Mar 21 01:34:40 EDT 2022


Have I managed to understand the problem, this time?

On 21/03/2022 05.05, Dennis Lee Bieber wrote:
> On Sun, 20 Mar 2022 15:55:27 +0100, <marcus.luetolf at bluewin.ch> declaimed
> the following:
> 
>>> all_letters = ‘abcdefghijklmnop’ 
>>> number_of_lists = 5
>>> number_of_sublists per list = 4
>>> number_per_sublist = 4
>> to
>>> all_letters = ‘abcdefghi’ 
>>> number_of_lists = 4
>>> number_of_sublists per list = 3
>>> number_per_sublist = 3
>> to
>>> all_letters = 'abcdef'.

> 	The discussion would be much easier if you gave real names to all
> those... (since you later confirm this is the SGP)
> 
> 	number of weeks
> 	number of groupings
> 	players per grouping
> 
> This avoids all confusion over lists, sublists, etc... "week 1", "group 3",
> "player 2".

How about these as 'meaningful names':

players = "abcdefghijklmnop"
number_of_weeks = 5
number_of_groupings = 4
players_per_grouping = 4


>> seems rather straightforward.  But for now I cannot see yet how to use it to remove all non-uniques sublists/teams.

> 	You don't "remove" them! "Remove" implies you already placed a grouping
> into the solution and now are checking for if they meet the constraints.
> Instead you check the constraints for a candidate grouping BEFORE
ADDING it
> to the solution.

Yes, the more 'constructivist' approach is probably easier - it is
easier to 'see' as things are added to the solution, than it is to keep
track of what was there 'before' when subtracting/pruning. YMMV!


This solution keeps track of each player's history, ie if player-a is
grouped with players 'b', 'c', and 'd' in the first game, then:

player_history['a'] == {'b','c','d'}

and in the second game (s)he is grouped with players 'e', 'i', 'm'; then
it becomes:

player_history['a'] == {'b','c','d', 'e', 'i', 'm'}

and so-on (see output-report, below)

The player's history is used whenever (s)he is 'selected' to ensure that
there is no repetition of anyone who has participated in that player's
previous groupings.


>> SPG exactly describes my goal.
> 
> 	The SGP is not a week-end programming exercise. It is the subject of
> multiple university research papers in developing/optimizing
> constraint-based solver algorithms.
> 
> 	A one-time pass over the output of .combinations() will not be
> sufficient (especially as the criteria per week that no player appears more
> than once means going from "abcd" [the first foursome .combinations() spits
> out] has to skip all other groups that begin with "a", "b", "c" or "d" --
> and you can't get them back later. At a minimum you need to restart the
> .combinations() on each week. You'll really need to implement some way of
> backtracking ("we ran out of groupings without being able to place one ink
> 'this' position, back up and change the previously placed grouping and
> start over on this position") -- it is possible you might have to back all
> the way up to the first grouping and try a different value for it.

Which all serves to make me think that I have yet to grasp the
full-measure of the problem!


Herewith the output-report.

The "draw" for each week (who is playing whom during that week) appears
as four Python-lists under the week's sub-title. (the 'real' output)

Inspecting the "draw", one can visually-check that each player only
plays against everyone else, once - and only once - and exactly once
(per @Dennis' comment about byes - no, none of them necessary with this
combination of definitions)!

The 16-player listing (debug-print) underneath each week's draw, shows
how the program[me] keeps a record of which players each player has
played to-date - thus after each week's game it extends by another three
players' names/letters.

Finally, by the end of the league/tournament (whatever you want to call
the five-weeks of play, per definitions), every player is shown to have
played against every other player:-


/usr/bin/python3 /home/dn/Projects/Experiments/marcus.py

Draw for 5 week league

Draw for week 1
['a', 'b', 'c', 'd']
['e', 'f', 'g', 'h']
['i', 'j', 'k', 'l']
['m', 'n', 'o', 'p']


a ['a', 'b', 'c', 'd']
b ['a', 'b', 'c', 'd']
c ['a', 'b', 'c', 'd']
d ['a', 'b', 'c', 'd']
e ['e', 'f', 'g', 'h']
f ['e', 'f', 'g', 'h']
g ['e', 'f', 'g', 'h']
h ['e', 'f', 'g', 'h']
i ['i', 'j', 'k', 'l']
j ['i', 'j', 'k', 'l']
k ['i', 'j', 'k', 'l']
l ['i', 'j', 'k', 'l']
m ['m', 'n', 'o', 'p']
n ['m', 'n', 'o', 'p']
o ['m', 'n', 'o', 'p']
p ['m', 'n', 'o', 'p']


Draw for week 2
['a', 'e', 'i', 'm']
['b', 'f', 'j', 'n']
['c', 'g', 'k', 'o']
['d', 'h', 'l', 'p']


a ['a', 'b', 'c', 'd', 'e', 'i', 'm']
b ['a', 'b', 'c', 'd', 'f', 'j', 'n']
c ['a', 'b', 'c', 'd', 'g', 'k', 'o']
d ['a', 'b', 'c', 'd', 'h', 'l', 'p']
e ['a', 'e', 'f', 'g', 'h', 'i', 'm']
f ['b', 'e', 'f', 'g', 'h', 'j', 'n']
g ['c', 'e', 'f', 'g', 'h', 'k', 'o']
h ['d', 'e', 'f', 'g', 'h', 'l', 'p']
i ['a', 'e', 'i', 'j', 'k', 'l', 'm']
j ['b', 'f', 'i', 'j', 'k', 'l', 'n']
k ['c', 'g', 'i', 'j', 'k', 'l', 'o']
l ['d', 'h', 'i', 'j', 'k', 'l', 'p']
m ['a', 'e', 'i', 'm', 'n', 'o', 'p']
n ['b', 'f', 'j', 'm', 'n', 'o', 'p']
o ['c', 'g', 'k', 'm', 'n', 'o', 'p']
p ['d', 'h', 'l', 'm', 'n', 'o', 'p']


Draw for week 3
['a', 'f', 'k', 'p']
['b', 'e', 'l', 'o']
['c', 'h', 'i', 'n']
['d', 'g', 'j', 'm']


a ['a', 'b', 'c', 'd', 'e', 'f', 'i', 'k', 'm', 'p']
b ['a', 'b', 'c', 'd', 'e', 'f', 'j', 'l', 'n', 'o']
c ['a', 'b', 'c', 'd', 'g', 'h', 'i', 'k', 'n', 'o']
d ['a', 'b', 'c', 'd', 'g', 'h', 'j', 'l', 'm', 'p']
e ['a', 'b', 'e', 'f', 'g', 'h', 'i', 'l', 'm', 'o']
f ['a', 'b', 'e', 'f', 'g', 'h', 'j', 'k', 'n', 'p']
g ['c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm', 'o']
h ['c', 'd', 'e', 'f', 'g', 'h', 'i', 'l', 'n', 'p']
i ['a', 'c', 'e', 'h', 'i', 'j', 'k', 'l', 'm', 'n']
j ['b', 'd', 'f', 'g', 'i', 'j', 'k', 'l', 'm', 'n']
k ['a', 'c', 'f', 'g', 'i', 'j', 'k', 'l', 'o', 'p']
l ['b', 'd', 'e', 'h', 'i', 'j', 'k', 'l', 'o', 'p']
m ['a', 'd', 'e', 'g', 'i', 'j', 'm', 'n', 'o', 'p']
n ['b', 'c', 'f', 'h', 'i', 'j', 'm', 'n', 'o', 'p']
o ['b', 'c', 'e', 'g', 'k', 'l', 'm', 'n', 'o', 'p']
p ['a', 'd', 'f', 'h', 'k', 'l', 'm', 'n', 'o', 'p']


Draw for week 4
['a', 'g', 'l', 'n']
['b', 'h', 'k', 'm']
['c', 'e', 'j', 'p']
['d', 'f', 'i', 'o']


a ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'i', 'k', 'l', 'm', 'n', 'p']
b ['a', 'b', 'c', 'd', 'e', 'f', 'h', 'j', 'k', 'l', 'm', 'n', 'o']
c ['a', 'b', 'c', 'd', 'e', 'g', 'h', 'i', 'j', 'k', 'n', 'o', 'p']
d ['a', 'b', 'c', 'd', 'f', 'g', 'h', 'i', 'j', 'l', 'm', 'o', 'p']
e ['a', 'b', 'c', 'e', 'f', 'g', 'h', 'i', 'j', 'l', 'm', 'o', 'p']
f ['a', 'b', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'n', 'o', 'p']
g ['a', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'o']
h ['b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'k', 'l', 'm', 'n', 'p']
i ['a', 'c', 'd', 'e', 'f', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o']
j ['b', 'c', 'd', 'e', 'f', 'g', 'i', 'j', 'k', 'l', 'm', 'n', 'p']
k ['a', 'b', 'c', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'o', 'p']
l ['a', 'b', 'd', 'e', 'g', 'h', 'i', 'j', 'k', 'l', 'n', 'o', 'p']
m ['a', 'b', 'd', 'e', 'g', 'h', 'i', 'j', 'k', 'm', 'n', 'o', 'p']
n ['a', 'b', 'c', 'f', 'g', 'h', 'i', 'j', 'l', 'm', 'n', 'o', 'p']
o ['b', 'c', 'd', 'e', 'f', 'g', 'i', 'k', 'l', 'm', 'n', 'o', 'p']
p ['a', 'c', 'd', 'e', 'f', 'h', 'j', 'k', 'l', 'm', 'n', 'o', 'p']


Draw for week 5
['a', 'h', 'j', 'o']
['b', 'g', 'i', 'p']
['c', 'f', 'l', 'm']
['d', 'e', 'k', 'n']


a ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p']
b ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p']
c ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p']
d ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p']
e ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p']
f ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p']
g ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p']
h ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p']
i ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p']
j ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p']
k ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p']
l ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p']
m ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p']
n ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p']
o ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p']
p ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n',
'o', 'p']


Process finished with exit code 0


Is this what we're trying to achieve?
-- 
Regards,
=dn


More information about the Tutor mailing list