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

[Oscar Benjamin]

On 27 September 2015 at 12:39, marcus lütolf <marcus.luetolf at bluewin.ch> wrote:
> 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.

Ah okay. This is what I thought your problem was but with an
additional constraint. I will spell out the two constraints formally:

You want a set of triples where each triple consists of three distinct
players and:
1) Each player plays each other player exactly once.
2) It is possible to arrange the triples so that every player plays
once on each day.

Constraint 1 means that you need N=1mod6 or N=3mod6. Constraint 2
means that you need N to be a multiple of three so we cannot have
N=1mod6. This means that we must have N=3mod6 or in other words:

    N = 3, 9, 15, 21, 27, ...

If I understand correctly you are only interested to know how to find
a solution to constraints 1) and 2) for these values of N. You do not
care what happens for values of N where a perfect solution is
impossible.

> 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.

So you want every player to play the same number of times? That's
reasonable. Is it also important that every player plays every other
player exactly once (i.e. constraint 1) )?

Unfortunately you will not be able to meet constraint 1) for N=24
since it is an even number.

> 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 ?

I would suggest that you begin working on pen and paper. How can you
construct a solution for N=3, N=9 etc?

An algorithm occurs to me as follows. Consider N=9 so we have golfers ABCDEFGHI.

We know that player A needs to play some games so let's begin there

(A...
...

Player A will at some point need to play both B and C and has not
played them yet so

(ABC)
...

Player A has not played everyone and will need to play players D and E so

(ABC)
(ADE)
...

Continuing we have

(ABC)
(ADE)
(AFG)
(AHI)
...

Now player A has played everyone but player B hasn't so

(ABC)
(ADE)
(AFG)
(AHI)
(B...)
...

Player B has already played both A and C which leaves the
possibilities DEFGHI. At some point player B must play D so let's
assume that's what happens:

(ABC)
(ADE)
(AFG)
(AHI)
(BD...)
...

Who can play with B and D? Well B has played A and C and D has played
A and E. So that leaves FGHI. We now loop through those possibilities
trying each out. This is where the algorithm recurses:

(ABC)
(ADE)
(AFG)
(AHI)
(BDF) - F could be GHI
...

Now B has still not played everyone and at some point B must play G so
let's try that out:

(ABC)
(ADE)
(AFG)
(AHI)
(BDF) - F could be GHI
(BG...)
...

Okay so who can play with B and G. Well B has played ACDF and G has
played AF so we need something that is not ABCDFG which leaves EHI as
possibilities. Let's loop through these trying them out. We'll begin
with E:

(ABC)
(ADE)
(AFG)
(AHI)
(BDF) - F could be GHI
(BGE) - E could be HI
...

Now B still hasn't played everyone and there's only two possibilities
H and I. which gives

(ABC)
(ADE)
(AFG)
(AHI)
(BDF) - F could be GHI
(BGE) - E could be HI
(BHI) <- conflict!!
...

Oh dear H and I have already played each other. Now we need to back
track. Maybe we were wrong to choose E? We'll try H instead:

(ABC)
(ADE)
(AFG)
(AHI)
(BDF) - F could be GHI
(BGH) - H could be I  (E was already rejected on backtrack)
...

Now B has one more game to play against E and I:

(ABC)
(ADE)
(AFG)
(AHI)
(BDF) - F could be GHI
(BGH) - H could be I  (E was already rejected on backtrack)
(BEI)
...

Okay so now A and B have played everyone. What about C?

And so on...

Follow this through on pen and paper. I don't think it will take too
long. Once you understand the algorithm you can think about how to
tell the computer to do it.

The target is that every player has played every other. You will have
reached this target when the number of triples is N*(N-1)/6. Why is
that? Well how many pairs are there? I can make all pairs by combining
each of N people with each of the N-1 remaining people. However this
double counts each pair since I count AB and BA. So the number of
pairs is N*(N-1)/2. Each pair is contained in exactly one triple and
each triple contains 3 distinct pairs. It follows that the number of
pairs is 3 times the number of triples. So the number of triples is
N*(N-1)/6. If we were working with quadruples instead of triples then
each quadruple contains 6 distinct pairs so the number of quadruples
is N*(N-1)/12.

In general if we work k-tuples then the number of pairs in each
k-tuple is k*(k-1)/2. It follows that the number of k-tuples is
N*(N-1)/(k*(k-1)) so when we have that many we've reached a solution.
Clearly a necessary (but not sufficient) condition for the existence
of a perfect solution is that N*(N-1) is divisible by k*(k-1). We also
know that N-1 needs to be divisible by k-1 since player each player
plays every other player in groups of size k-1. Finally we have that N
itself must be divisible by k so that every golfer can play on every
day. Bringing these together we have that N is divisible by k and N-1
is divisible by k-1.

For triples this gives:

    N = 3, 9, 15, 21, 27, 33, ...

which is correct since we already established that N=3mod6.

For quadruples k=4 and we need that N is divisible by 4 and n-1 is
divisible by 3 which gives:

    N = 4, 16, 28, 40, 52, ...

In other words N=4mod12.

However is is possible that not all of these admit perfect solutions.

In general you may need to simply try and find a perfect solution
exhaustively but the above two results suggest the general form

    N=k mod k*(k-1)

This guarantees that N is divisible by k and N-1 by k-1. Which is
certainly a necessary condition but not necessarily a sufficient one.

--
Oscar