Uppslagsproblem

Jag vet inte hur "officiellt" detta namn är på denna typ av problem, eller "dictionary problems" (som låter bättre), men det är ett rätt passande namn. Samtliga problem av denna typ har följande drag gemensamt:

* Ett alfabet är definierat som en mängd av bokstäver, t ex alla gemener a-z. "Bokstäverna" kan även vara siffror eller andra tecken. Alfabetet är dessutom en ordnad mängd, dvs en bokstav i alfabetet kommer "först", och därefter kommer de andra bokstäverna i en otvetydig ordning.
* Ett ord är definierat som en sekvens av bokstäver som uppfyller vissa regler. Exempelvis kan en regel vara att ordet måste bestå av högst 5 bokstäver eller att alla bokstäver i ordet ska vara olika.
* Ett språk är definierat som mängden av alla giltiga ord. Även denna mängd är ordnad eftersom bokstäverna i alfabetet är ordnade.
* Antalet ord i språket är väldigt stort - det är i praktiken omöjligt att generera alla ord inom acceptabel tid.
* Uppgiften går ut på att man givet ett ord i språket bestämmer dess ordningsnummer (där 1 oftast är det första ordet) och/eller att man givet ordningsnumret tar reda på vilket ord som finns på denna plats i språket.

En vanligt förekommande term i dessa sammanhang är "lexikografisk ordning" vilket innebär sortering i alfabetisk ordning. Om inget annat sägs i uppgiften menas normalt ASCII ordning.

Ett enkelt exempel bör räta ut eventuella frågetecken:

Exempel: Låt alfabetet bestå av bokstäverna a-z. Ett giltigt ord i språket har exakt 6 bokstäver. Skriv ett program som avgör vilket ord som finns på position x i språket. Det första ordet (x=1) är "aaaaaa" och detsista ordet är "zzzzzz".

Detta är ett väldigt enkelt exempel - varje bokstav i ordet kan väljas fritt från alfabetet oberoende av de tidigare bokstäverna i ordet. Lösningen till problemet blir i den närmaste trivialt - det är egentligen samma sak som att konvertera ett tal från basen 10 till basen 26. Antalet giltiga ord i språket är för övrigt 26^6 = 308,915,776.

Exempel: Låt alfabetet vara som ovan (a-z) samt att ett giltigt ord måste innehålla exakt 6 bokstäver. Dessutom måste ordet innehålla 6 unika bokstäver.

Vi börjar med att räkna ut antalet ord i språket (vilket i och för sig inte är nödvändigt för att lösa uppgiften). Det är inte så svårt - första bokstaven kan vara vilken som helst av a-z, 26 stycken. Andra bokstaven kan vara alla utom den som valdes nyss, dvs 25 st, osv. Totalt antal blir 26*25*24*23*22*21 eller 26!/(26-6)! = 165,765,600.

Här måste vi dock tänka till lite mer. Eftersom antalet ord är så pass många är det förstås helt meningslöst att försöka loopa igenom alla ord och kolla vilket som kommer på den eftersökta platsen. Här måste vi istället använda den generella metod som man löser i princip alla sådana här problem på: man tar först reda på vilken bokstav som kommer först, sedan nästa bokstav osv. Man loopar alltså över antalet bokstäver, inte över antalet ord. För varje position i ordet loopar vi sedan över samtliga möjliga bokstäver i denna position och avgör direkt om detta är den rätta bokstaven för denna position.

Hur avgör man vilken bokstav som ska vara vid en given position? Det är detta som är nyckeln i den här typen av uppgifter - man räknar ut (på något sätt), HUR många ord som börjar med en viss bokstav på en viss position. Om vi söker ord nummer 7 i alfabetet (OBS: Här, och i resten av texten, räknar jag ord 0 som det första ordet i språket - detta brukar underlätta en del. Vanligtvis brukar dock uppgiften ha 1 som startindex.) och det finns 5 ord
som börjar med bokstaven 'a', så kan givetvis inte ordet starta med bokstaven 'a'. Istället vet vi nu att det är ord nummer 2 av de som börjar med 'b' eller en ännu senare bokstav. Om det finns 10 ord som börjar med bokstav 'b', vet vi nu att ordet börjar med bokstaven 'b'. Därefter går vi ett steg framåt i ordet och kollar position nummer 2. Genom att upprepa denna process får vi följande enkla algoritm: (pseudokod)

  x = the ordering number of the word we're looking for
  len = the final number of letters in the word
  curword = ""
  for i=0 to len-1
    for c=start of alphabet to end of alphabet
      curword[i]=c
      y = number of possible words starting with curword
      if x<y then break inner loop
      x=x-y
    end
  end
  return curword

Koden ovan antar att antalet bokstäver i ordet är detsamma för alla ord i språket. Så behöver givetvis inte vara fallet. Lyckligtvis finns det ett enkelt trick för att komma runt detta: man lägger till en extra bokstav i alfabetet som motsvarar ingen bokstav alls. Givetvis kan denna speciella "bokstav" endast förekomma i början av ordet och inte var som helst, så det kan ändå komplicera beräkningen av antalet ord som börjar med en viss sekvens av bokstäver.

Vi har nu reducerat problemet till att bestämma _hur_ många ord i språket som börjar med en viss sekvens av bokstäver. Kan vi lösa det problemet, har
vi löst det ursprungliga problemet genom att helt enkelt applicera algoritmen ovan.

Vi återgår till exemplet ovan. Hur många ord börjar med en given sekvens av t ex 3 bokstäver? Vi vet att bokstav 4 kan väljas fritt bland de återstående 23 bokstäverna som inte valts hittills. Sedan kan bokstav 5 väljas fritt av de 22 kvarvarande bokstäverna efter det osv. Mer generellt, antalet ord som börjar med x givna bokstäver är exakt (26-x)*(25-x)*...*21.

Låt oss studera en lite mer komplicerad uppgift. Vi definierar ett "zick-zack tal" som ett tal där siffrorna i talet alternerande är högre
respektive lägre än föregående siffra (och den andra siffran är alltid högre än den första. Dessutom ska alla siffror i talet vara unika. De sju minsta zick-zack talen som använder siffrorna 1-5 är t ex 13254, 14253, 14352, 15243, 15342, 23154, 24153 (uppgiften är tagen från BIO 1999).

Problemet är alltså, givet de siffror vi får (och måste) använda (t ex 1-5 som ovan), finn det n'te minsta zick-zack talet.

Återigen handlar det helt enkelt om att avgöra hur många ord (zick-zack tal alltså) som börjar med en viss sekvens av bokstäver (siffror). Här blir det
dock genast svårare, eftersom antalet beror på tidigare val man gjort. T ex så finns det två stycken tal som använder siffrorna 1-5 som börjar med 24... (24153 och 24351) medan det bara finns ett tal som börjar med siffrorna 23... (23154).

Tricket för att lösa uppgiften är att finna de faktorer som bestämmer antalet möjliga tal som börjar med en viss sekvens. Det finns ingen standardmetod för att göra detta, utan det gäller bara att hitta ett samband, ofta ett rekursivt sådant. I det här fallet är dessa faktorer två stycken: antalet möjliga siffror som kan direkt följa nästa siffra, samt antalet siffror som är kvar. Det spelar ingen roll _vilka_ siffror som är kvar eftersom en siffra _endast_ begränsas av dess föregående siffra (att man inte får välja samma siffra flera gånger är inte samma typ av begränsning, man kan se det som att man istället minskar ner utbudet av lediga siffror). När det gäller inledningen 24... så är antalet möjliga siffror för den tredje positionen 2 stycken: antingen en 1:a eller en 3:a. Antalet siffror kvar är förstås 3. I fallet 23... måste nästa siffra vara en 1:a. Notera att antalet möjliga siffror på position 3 i dessa fall råkar
vara exakt det antal tal som börjar med sekvenserna 24... och 23..., men det beror endast på att det är så få siffror kvar att välja. Vi har nu krympt problemet ytterligare. Det återstår att beräkna antalet möjliga tal givet att vi vet antalet olika siffror som kan vara på nästa position, samt hur många siffror som är kvar i talet. Denna beräkning kan göras rekursivt. Antag t ex att vi har 7 siffror kvar, och att nästa siffra kan vara 3 stycken av dessa. Vi betecknar resultatet av denna beräkning som f(7,3). Detta skulle t ex kunna motsvara att vi har kvar siffrorna 1,2,3,5,6,7,8 och att den senaste valda siffran är 4 samt att nästa siffra ska vara lägre än den föregående. För att beräkna f(7,3) undersöker vi alla 3 möjliga val, dvs i det här fallet siffrorna 1, 2 och 3. Om vi väljer 1 så kan vi välja vilken av de 6 kvarvarande siffrorna nästa gång. Väljer vi 2 kan vi sedan välja någon av de 5 kvarvarande, osv. Vi får att f(7,3) = f(6,6)+f(6,5)+f(6,4). Mer generellt,

  f(x,y) = f(x-1,x-1) + f(x-1,x-2) + ... + f(x-1,x-y).
 
Detta kan se lite krångligt ut, men om ni beräknar några fler specifika värden på f(x,y) så hoppas jag ni inser att det blir så. Återstår gör då basfallen - f(0,0) är förstås 1 (vi har använt oss av alla siffror, alltså har vi ett giltig zick-zack tal) och f(x,0) är förstås 0 (det finns inga giltiga siffror att välja för nästa siffra). Denna funktion kan - bör! - förstås beräknas med hjälp av dynamisk programmering, så man inte evaluerar samma f(x,y) flera gånger.


Uppgift 1: Implementera Zig-Zag numbers enligt metoden ovan.

Än så länge har vi bara gått åt ett håll: givet ett ordningsnummer, finn ordet. Det är också vanligt att man måste kunna gå åt andra hållet (eller åt båda hållen), dvs givet ett giltigt ord, finn dess ordningsnummer i språket. Detta problem - att gå åt "andra hållet" - är förstår väldigt
snarlikt det första problemet. Faktum är att det finns en mycket enkel och effektiv metod för att göra detta om man redan har en rutin för att gå åt ena hållet, och den metoden är binärsökning. Jag utgår ifrån att ni är bekant med binärsökning, men det kan vara lätt att glömma bort att detta är en mycket kraftfull algoritm i många sammanhang, som man inte får glömma bort.

Så här kan en binärsökning t ex se ut: (findword returnerar det ord som finns på en viss position i språket)

  s=word we want to find the ordering number for
  lo=0
  hi=number_of_words
  while (lo<hi) {
    x=(lo+hi)/2
    i=strcmp(findword(x),s)
    if (i==0)
      return x // Word is at this position in language
    if (i<0)
      lo=x+1
    else
      hi=x
  }
  return -1;  // Word not in language

Två saker att notera: jag skriver alltid binärsökning så att det undre indexet (lo) pekar på det första talet inom det kvarvarande intervallet, medan det övre indexet (hi) pekar på det första talet utanför intervallet. Detta är ofta mer praktiskt, och det är t ex så STL fungerar. Dessutom utgår jag här ifrån att antalet ord i språket går att beräkna. Om det skulle vara problematisk kan man istället sätta hi till MAXINT eller något annat tillräckligt stort tal (se bara till att beräkningen lo+hi inte orsakar overflow!!) och se till att findword returnerar något specialvärde om man skulle försöka indexera ett ord som inte finns i språket.

Givetvis kan man göra exakt tvärtom - man skriver en funktion som givet ett ord finner ordningstalet, och sedan gör binärsökningen åt andra hållet. Detta brukar normalt sätt vara svårare, om inte annat bli binärsökningen mer komplicerad eftersom både lo och hi kommer vara strängar istället för tal, och alla strängar kommer inte tillhöra språket (att jämföra med talen, som samtliga är giltiga ordningstal).

Uppgift 2: Givet alla tal från 1 till n (1 <= n <= 1,000,000,000), vilket är det m'te (1 <= m <= n) talet i lexikografisk ordning? T ex om n=16 så är
talen 1-16 i lexikografisk ordning 1, 10, 11, 12, 13, 14, 15, 16, 2, 3,..., 9 och är n=1001 så är de första talen 1, 10, 100, 1000, 1001, 101, 102 etc.

Jag tänkte också kort ge några exempel på närliggande problem som också kräver att man arbetar med en siffra i taget istället för att loopa igenom
att möjliga tal. (gäller även Bonus Bonds).

Uppgift 3: Antag att vi skriver ut talen 1, 2, 3, ..., n och räknar antalet siffror vi använder oss av, var siffra för sig. Om n=12 t ex så har vi använt oss av 5 ettor (förkommer i talet 1, 10 och 11, 12), en nolla (i 10), två tvåor (i 2 och 12) och en av varje siffra 3 till 9. Givet en vektor på 10 element som innehåller det maximala antalet siffror vi får använda, hur många tal (från 1) kan vi skriva ut utan att överskrida antalet siffror? T ex om indatavektorn är {1,5,1,1,1,1,1,1,1,1} så är svaret 11 eftersom det krävs 2 tvåor för att skriva ut talen 1 till 12, men vi har bara en tvåa. Ändrar vi det tredje element till 2 (dvs {1,5,2,1,1,1,1,1,1,1}) så blir svaret 12 - vi har exakt så många siffror av alla sorter som krävs för att skriva alla tal mellan 1 och 12.

Tips: Använd binärsökning istället för att direkt försöka ta reda på svaret - det är mycket lättare.


Tävlingsuppgifter

Problem Tävlingens hemsida Hjälp och kommentarer
Twofive
 IOI 2001 SVÅR!!!
Bonus Bonds
 Problem set archive

Tillbaka