In de goeie ouwe tijd werden telefoonnummers nog opgezocht in een telefoonboek: een grote verzameling telefoonnummers die alfabetisch gerangschikt staan op naam. Sinds deze informatie ook via het Internet te raadplegen is, is het gebruik van de papieren versie sterk afgenomen.

telefoonboek
Geopend telefoonboek.

In België werd het eerste telefoonboek uitgegeven in 1884. Later werden de telefoonboeken uitgegeven door de Regie van Telegrafie en Telefonie (RTT) en Belgacom. In 1968 verwierf I.T.T.-Promedia de concessie voor het uitgeven van telefoonboeken. Hun Gouden Gids verscheen in 1969, eerst in Antwerpen en Luik. Een jaar later was deze cyclus rond en ontving elke telefoonabonnee zijn Gouden Gids en Witte Gids.

Een conflict tussen Belgacom en Promedia — bekend als de Belgische telefoonboekenoorlog — leidde ertoe dat de abonnees tussen 1995 en 1998 vier telefoongidsen ontvingen: een gouden en een witte gids van Belgacom én een gouden en een witte gids van I.T.T.. Na het oplossen van dit conflict ging Promedia — in 2007 omgedoopt tot Truvo — verder met de uitgave en distributie van beide telefoonboeken.

Opgave

Omdat de lijst van telefoonnummers soms heel groot kon worden, werden telefoonboeken traditioneel opgedeeld in meerdere volumes. Daarbij bevatte elk volume de telefoonnummers van de namen die beginnen met een reeks opeenvolgende letters uit het alfabet. We zullen twee manieren gebruiken om een opdeling van een telefoonboek te omschrijven.

Een eerste manier bestaat uit een stringvoorstelling (str) waarin elk volume wordt weergegeven als twee hoofdletters gescheiden door een koppelteken, waarbij de hoofdletters de eerste en de laatste letter aangeven van de reeks opeenvolgende letters uit het alfabet waarmee de namen in het volume beginnen. De verschillende volumes worden van elkaar gescheiden door één enkele spatie. Op die manier kan een opdeling van een telefoonboek bijvoorbeeld omschreven worden door de string

A-D E-J K-O P-Z

Bij deze omschrijving moet gelden dat het volledige alfabet wordt opgedeeld, en dat de volumes ook op elkaar volgen. Bovendien worden volumes die beperkt zijn tot namen die beginnen met één enkele letter kortweg voorgesteld door die ene letter. We schrijven dus niet D-D maar gewoonweg D.

Een tweede numerieke voorstelling stelt de opdeling van een telefoonboek voor als een tuple van strikt positieve natuurlijke getallen (int), waarbij elk getal staat voor het aantal letters in de reeks opeenvolgende letters uit het alfabet waarmee de namen in het volume beginnen. Zo kan de opdeling die we hierboven als voorbeeld gebruikt hebben ook omschreven worden als $$(4, 6, 5, 11)$$: het eerste volume omvat de eerste 4 letters (A-D), het tweede volume de volgende 6 letters (E-J), het derde volume de volgende 5 letters (K-O) en het vierde volume de laatste 11 letters (P-Z). Er moet gelden dat de som van de getallen van een numerieke voorstelling gelijk is aan 26.

Stel nu dat we het aantal namen kennen per beginletter, bijvoorbeeld:

A  B C  D  E  F G H I J  K L  M  N 0 P Q R  S  T U V W X Y Z
16 4 17 10 15 4 4 6 7 14 9 17 27 6 1 9 0 12 20 8 0 3 4 0 3 4

In totaal zijn er 220 namen, en de telefoonmaatschappij heeft beslist om een editie uit te brengen met 4 volumes. Idealiter bevat elk volume dus $$\frac{220}{4} = 55$$ namen. Een mogelijke verdeling is A-D E-J K-O P-Z met respectievelijk 47, 50, 60 en 63 namen. In absolute waarde wijken deze volumes dus 8, 5, 5 en 8 namen af van de ideale 55. We noemen de totale som van deze afwijkingen de delta van de opdeling van het telefoonboek. In dit geval bedraagt de delta dus 26. Een andere opdeling A-G H-O P Q-Z met aantallen namen 70, 87, 9 en 54 en afwijkingen van respectievelijk 15, 32, 46 en 1 van de ideale 55 namen, levert dus een delta van 94 op. We zouden op zoek kunnen gaan naar de opdeling van het telefoonboek met de kleinst mogelijke delta, maar dat zou iets te ingewikkeld zijn. Gevraagd wordt:

Voorbeeld

>>> volumes((4, 6, 5, 11))
'A-D E-J K-O P-Z'
>>> volumes((7, 8, 1, 10))
'A-G H-O P Q-Z'
>>> volumes((4, 7, 5, 10))
'A-D E-K L-P Q-Z'
>>> volumes((8, 3, 9, 7))
Traceback (most recent call last):
AssertionError: ongeldige opdeling

>>> aantallen('A-D E-J K-O P-Z')
(4, 6, 5, 11)
>>> aantallen('A-G H-O P Q-Z')
(7, 8, 1, 10)
>>> aantallen('A-D E-K L-P Q-Z')
(4, 7, 5, 10)
>>> aantallen('A-D F-K L-P Q-Z')
Traceback (most recent call last):
AssertionError: ongeldige opdeling

>>> namen = (16, 4, 17, 10, 15, 4, 4, 6, 7, 14, 9, 17, 27, 6, 1, 9, 0, 12, 20, 8, 0, 3, 4, 0, 3, 4)
>>> delta('A-D E-J K-O P-Z', namen)
26.0
>>> delta((7, 8, 1, 10), namen)
94.0
>>> delta('A-D E-K L-P Q-Z', namen)
18.0
>>> delta(42, namen)
Traceback (most recent call last):
AssertionError: ongeldige opdeling