[Tutor] problem solving with lists

[Dennis Lee Bieber]

On Sat, 19 Mar 2022 14:55:31 +0100, <marcus.luetolf at bluewin.ch> declaimed
the following:

>First to dn’s answer:
>
>I am not an professional programmer. Programming with pyhon is a hobby in the sense of life long learning.
>
>And other than a course in C I have no knowledge of other programming languages. I am just trying to solve
>
>my problem with what little I know about python. That’s why I turned to tutor for help. I have found an
>
>algorithm and all required code steps but the very last one,  admittedly helped by most wellcome
>
>comments from tutor.
>

	Based upon the list archives, you've been trying to solve this problem
for over six years.
https://www.mail-archive.com/tutor@python.org/msg72192.html

	Over a period of 10 days, /that/ thread evolved into an explanation
that you were attempting to produce a solution to the "Social Golfer
Problem".

	In contrast, this thread has been running for 13 days, and there have
only been a few hints as to what the real problem to be solved is... And it
ISN'T eliminating any sets that have two or more elements in common. The
Social Golfer Problem rarely has a perfect solution -- normally the best
one can achieve is to minimize the repeated pairings.


>«Unique» means that other than single items/letters,  pairs of items/letters (pair1, pair2, pair3) can appear only once in
>
>all sublists. A sublist could be understood as a combination of pair1+pair2+pair3. At the end there should be only 12 sublists
>
>in 4 lists left.

	In most cases, there may be NO solution meeting that criteria.
https://www.localsolver.com/docs/last/exampletour/socialgolfer.html
claims that 32 players, in (8) foursomes, and playing for 10 days/weeks
does have a known solution with no repeated pairs.

"""
More generally the problem is to schedule m groups of n golfers over p
weeks, with maximum socialisation. The complexity of the problem is
unknown. 
"""

	Unfortunately, that web site, like many other hits on "social golfer
problem", wants to sell you their proprietary solution library.

https://en.wikipedia.org/wiki/Social_golfer_problem
https://en.wikipedia.org/wiki/Steiner_system
"""
The corresponding question for finding thirteen different disjoint
S(2,3,15) systems was asked by James Sylvester in 1860 as an extension of
the Kirkman's schoolgirl problem, namely whether Kirkman's schoolgirls
could march for an entire term of 13 weeks with no triplet of girls being
repeated over the whole term. The question was solved by RHF Denniston in
1974,[11] who constructed Week 1 as follows:

	<SNIP>

 Denniston reported in his paper that the search he employed took 7 hours
on an Elliott 4130 computer at the University of Leicester, and he
immediately ended the search on finding the solution above, not looking to
establish uniqueness. 
"""

	Javascript "near" solver at
https://github.com/islemaster/good-enough-golfers (and running page
https://goodenoughgolfers.com/ )


	
	A text description of the real-world problem, and not this confusing
emphasis on list of sublists of sublists (...) would have short-cut a lot
of this thread.

-=-=-=-
	Given a POOL of 16 golfers/players, who play a MATCH once a week (day),
in four FOURSOMES (16/4 => 4), over the course of a TOURNAMENT lasting five
weeks (days), devise a schedule assigning players to foursomes such that
the number of repeated pairings between foursomes is minimized.

Constraint: 
	Each of the 16 players is assigned to a foursome each week (day);
conversely no player may appear in multiple foursomes within a single week
(day).
-=-=-=-

Tournament	<=		top-level list, having five weekly (daily)
Matches		<=		sublists each having four groups of
Foursomes		<=		sublists/tuples/strings of length four

	Those terms would make following the discussion much cleaner, and
avoids getting bogged down in thoughts of "indexing" etc.

	While it may be possible to make a generalized program (allowing for
parameters for pool size, group size (threesome, foursome, quintets...) and
number of weeks (days) in the tournament... Everything I've read implies
that there is no simple numerical solution. Solutions appear to rely upon
brute-force searching, applying some sort of scoring to each repeated
pairing (is it better to have one pair repeat four times, or two pairs that
each repeat twice?).


	After all, an easy start for 16/4/5 case is simply

abcd	efgh	ijkl	mnop
aeim	bfjn		cgko	dhlp

wherein the second week take the first player of each foursome from the
previous week to make the first foursome of the new week, second players
for second foursome, etc. But you can't do that for the third week -- the
transform just reverses..


	This will likely be my last post within this thread. Attempting to
solve problems when much of the actual problem domain is being withheld
from the assistant is an exercise in futility...


-- 
	Wulfraed                 Dennis Lee Bieber         AF6VN
	wlfraed at ix.netcom.com    http://wlfraed.microdiversity.freeddns.org/