[Tutor] problem solving with lists

[Dennis Lee Bieber]

On Sat, 19 Mar 2022 10:34:00 -0400, Mayo Adams <mayoadams at gmail.com>
declaimed the following:

>So what's wrong  with Dennis Bieber's answer?
>

	Probably the same unspoken requirement: it isn't a solution to the SGP
(defined by pool size [# of players], group size [which I understand has to
divide evenly into the pool -- there are no "bye" weeks], and number of
weeks; though the referenced master's thesis uses the notation (# groups,
group size, weeks), which makes my (32, 4, 10) => (8, 4, 10); I will be
using my notation throughout).

	That is: 

		1)	for each week in the tournament, each player is assigned to
just one group

		2)	over the course of the tournament, there are no repeated pairs
of players

	By the definition of the strict SGP, this does mean that some player
pairs may never appear (each pairing appears 0..1 times in the tournament)

	A solution to 16/4/1 would be: "abcd" "efgh" "ijkl" "mnop". That meets
both #1 and #2. Granted, it also means, for example, that there are 12
pairings with each player that never occur. The goal being to maximize the
number of unique pairings.

	I have seen one paper that proposes a relaxed variant of the SGP. It
changes the 0..1 pairing requirement to 1..+; every pairing must occur at
least once, but some pairings may occur more than once. The goal here,
then, being to minimize the number of repeat pairings.

	I glanced at some of the master's thesis. Their initial solver library
(in SWI-Prolog, running on a MacBook with 2.16GHz Core 2 Duo and 1GB --
depending upon software, a Raspberry-Pi 4B 4GB could probably compete these
days <G>) could solve SGP(32, 4, 7) in 20 minutes, it failed to find a
solution for SGP(32, 4, 8) after a week of running.

	While SGP(32, 4, 10) has been proven to have a solution, the author's
improved/modified software [they borrowed an allocator from another system]
was incapable of running that case -- managing a solution for SGP(32, 4, 9)
[nine weeks, but not ten weeks]. The timings reported in that paper don't
include an SGP(16, 4, 5) case: SGP(15, 3, 5) and SGP(24, 4, 5) are shown,
taking upwards of 30 seconds when using their initial (unoptimized) solver.


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