[Tutor] Creating lists with definite (n) items without repetitions

[Peter Otten]

marcus lütolf wrote:

> Hello Peter, hello Martin,
> many thanks for your very quick response !!!
> 
> As for Peter's advice:
> 
>> At first I thought you might want itertools.combinations()
>>
>>>>> import string, itertools
>>>>> for t in itertools.combinations(string.ascii_lowercase, 3):
>> ...     print t # list(t) if you actually need a list
>> ...
>> ('a', 'b', 'c')
>> ('a', 'b', 'd')
>> ('a', 'b', 'e')
>> ('a', 'b', 'f')
>> ('a', 'b', 'g')
>> [snip]
>>
>> but that gives
>>
>>>>> sum(1 for t in itertools.combinations(string.ascii_lowercase, 3))
>> 2600
> 
> the 5 lists above do not match my task insofar as every of the 5 lists
> contains  'a' and 'b' which should occur only once, hence my count of a
> maximum of 301 lists, which might nor be correct 100%. My be one could put
> it in Python as follows:
>> ('a', 'b', 'c') = True
>> ('a', 'b', 'd')= False
>> ('a', 'b', 'e')= False
>> ('a', 'b', 'f')= False
>> ('a', 'b', 'g')= False
> I should probably tell you the real task are a series (maximum ~ 301)
> lists in which real names  of people are assigned to the items/letters for
> 2 people(golfers) can be in  the same list(flight)  only once for an
> extended period of time.

OK, you want all triples where no pair inside a triple is repeated.
There are 325 pairs, and one triple uses up three pairs.
That puts an upper limit of 325/3 = 108 on the number of triples.
You then have to find all sets of pairs where the union contains

My attempts to solve this analytically have failed so far, therefore I wrote 
a script that checks random triples for the above condition:


$ cat all_teams_101.py
import random
import sys
import textwrap
from itertools import combinations, count
from string import ascii_lowercase


if len(sys.argv) > 1:
    random.seed(int(sys.argv[1]))


def shuffled(items):
    items = list(items)
    random.shuffle(items)
    return items

triples = list(combinations(ascii_lowercase, 3))

best_teams = []
best_shuffled = None
try:
    for i in count():
        seen_pairs = set()
        teams = []
        shuffled_teams = shuffled(triples)
        for team in shuffled_teams:
            team_pairs = [
                frozenset(t) for t in
                [team[:2], team[1:], team[::2]]
            ]
            if all((pair not in seen_pairs) for pair in team_pairs):
                seen_pairs.update(team_pairs)
                teams.append(team)

        if len(teams) > len(best_teams):
            print(i, len(teams))
            best_teams = teams
            best_shuffled = shuffled_teams
except KeyboardInterrupt:
    print()
    print(textwrap.fill(" ".join(map("".join, best_teams))))
$ python3 all_teams_101.py 42
0 97
55 98
220 100
561 101
^C
bcq aoy nrz bhs gpx cjt cmu cnw fnq tvx cix afx bpv dhm hno dpy hil
cfy jlv cdg mnt bln htw aiu fhp jsw qru gkq egl gtu lqx ars kwz emr
inp jky kmp uwy gow hjx aep aqt kns bft biw ops efs ghr mov fgi lms
dnu bjm lyz cek fkv gmy dev qsy dlt dqw huz bdr nxy eiy dsz mxz flr
acz klu adk csv ehq bez eju foz avw iko jpq ewx gjz bkx prw abg qvz
krt fmw dfj jor irv ptz ajn dox sux imq clo eot ist bou gnv hvy
$ 

It's probably a good idea to ask your question in a mathematics forum -- 
this problem looks common enough to have a name and some brain power spent 
on it. 

(Google found https://en.wikipedia.org/wiki/Kirkman's_schoolgirl_problem 
which looks similar; maybe someone here can make sense of it)

> The next step would be to assign compatible and noncompatible attributes 
> to the items/letters which will reduce the maximum of possible
> lists(flights)