Exempel: Permutationer

Sven-Olof Nyström
OOP med Java våren -25
Informationsteknologi
Uppsala Universitet

Problem: Givet en fil med ord, hitta grupper med ord ur filen som är varandras permutationer.

Exempel på permutationer:

larma, alarm
pusta, putsa, stupa

Jag rekommenderar att du tar dig tid och funderar på hur du skulle lösa problemet innan du tittar på lösningen nedan.

Permutationer, lösning

Nå, det finns en lösning som är både enkel och effektiv.

Börja med att definiera en funktion alphabetize som tar en sträng och returnerar en sträng med bokstäverna i alfabetisk ordning.

Nu kommer alphabetize("larma") att returnera strängen "aalmr". På samma sätt returnerar alphabetize("alarm") också "aalmr".

Sen bygger vi en tabell Map<String,List<String>> där strängarna läggs in enligt den alfabetiserade nyckeln.

När vi genererar en nyckel genom att sortera bokstäverna kommer "larma" och "alarm" att få samma nyckel.

Vid varje nyckel lagras en lista av de strängar som har den nyckeln.

Två strängar med samma nyckel är varandras permutationer och hamnar på samma lista.

Kort mellanspel 3: Klassen StringBuffer

Om man bygger upp en ny sträng i metoden alphabetize med strängkonkatenering (skrivs med "+" i Java) blir klassen String lite ineffektiv. Eftersom en sträng inte kan modifieras skapas nya strängar istället för att utöka existerande.

För att tillåta effektivare konstruktion av strängar finns klassen StringBuffer. Den definierar (bland annat) en metod append som adderar nåt till buffern. Metoden append är bland annat definierad för de åtta primitiva typerna och (förstås) för String.

Exempel:

x = "a" + 4 + "c"

kan även skrivas

StringBuffer y = new StringBuffer();
y.append("a");
y.append(4);
y.append("c");
x = y.toString()

... men eftersom metoden append returnerar buffern kan man kedja ihop anropen:

x = new StringBuffer().append("a").append(4).append("c").toString()

Ovanstående är en typisk användning av StringBuffer. Anta att vi vill bygga en sträng av godtycklig längd. Så här skulle man kanske göra med String:

	String s = "";
	for (int i = 0; i < 10; i++) {
	    s = s + "x";
	}
	System.out.println(s);

men med StringBuffer:

	StringBuffer sb = new StringBuffer();
	for (int i = 0; i < 10; i++) {
	    sb.append("x");
	}
	String s = new String(sb);
	System.out.println(s);

Några metoder:

char charAt(int i)

Returnerar det tecken som lagras vid position i

void setCharAt(int i, char c)

Sätter tecknet vid position i till c.

String toString()

Konverterar buffern till en sträng. (Metoden returnerar en sträng med samma innehåll.)

Alphabetize

Låt oss först titta på metoden alphabetize.

Vi börjar med att räkna hur många gånger varje bokstav förekommer i strängen. Vi löser detta med en tabell count av typen SortedMap<Character, Integer>. Koden som räknar hur många gånger en bokstav förekommer liknar koden i programmet Freq.java som räknar antal förekomster av olika ord.

Så om vi har ett ord larma kommer tabellen count att innehålla

a -> 2
l -> 1
m -> 1
r -> 1

Notera att eftersom tabellen är en TreeMap är nycklarna ordnade. Vi skapar en StringBuffer som vi kallar result för den sorterade strängen. Vi ser till att allokera plats för precis så många tecken som vi behöver i result (detta är inte helt nödvändigt; en StringBuffer kan växa vid behov).

Sedan är det bara att loopa igenom nycklarna och placera varje tecken i result. Vi använder metoden entrySet för att betrakta count som en mängd av par av nyckel (Character) och värde (Integer).

I exemplet förekom bokstaven a två gånger, så vi placerar två a'n i result. Övriga bokstäver (l, m och r) förekom en gång.

Till sist konverterar vi result till en sträng (med metodanropet toString()) och returnerar strängen.

I exemplet blir resultatet "aalmr".

private static String alphabetize(String s) {
    //Sortera tecknen i en sträng genom att räkna hur många gånger
    //varje tecken förekommer

    SortedMap<Character, Integer> count =
	new TreeMap<Character, Integer> ();

    int len = s.length();
    for (int i=0; i<len; i++) {

	char c = s.charAt(i);

	if (count.containsKey(c)) {
	    count.put(c, count.get(c)+1);
	}
	else {
	    count.put(c, 1);
	}
    }

    StringBuffer result = new StringBuffer(len);

    for (Map.Entry<Character, Integer> e : count.entrySet()) {
	char c = e.getKey();
	int n = e.getValue();

	for (int i=0; i<n; i++) {
	    result.append(c);
	}
    }
    return result.toString();
}

Huvudprogrammet

Låt oss nu titta på main-metoden. Den är (som alltid) deklarerad static. (I just det här programmet är alla metoder statiska.) Metoden main tar som vanligt ett argument, en array av strängar. Vi börjar med att kolla att arrayen har längd 2, detta motsvarar att man ger två argument till Perm. Här är ett exempel på hur perm kan anropas på kommandoraden:

java Perm svenska2.txt 4

(Första argumentet är filnamnet; jag har två färdiga svenska ordlistor med olika teckenkodningar. Andra argumentet är storleken på de grupper av permuterade ord som vi är intresserade av.) Om arrayen args ej har längd två skrivs en förklarande text ut och programmet terminerar.

Sedan konverteras andra argumentet till ett heltal (andra argumentet är args[1], vi räknar ju från noll). Sen anropas metoden readWords som tar filnamnet och läser in filen i en tabell av typen Map<String,List<String>>. Givet denna tabell är det enkelt att ta reda på vilka permutationer som är större än ett visst gränsvärde. Det görs i metodanropet till printPermutations.

public static void main(String[] args) {
    if (args.length != 2) {
        System.err.println("Usage: java Perm <File> <Min group size>");
        System.exit(1);
    }

    int minGroupSize = Integer.parseInt(args[1]);

    // Read words from file and put into simulated multimap
    Map<String,List<String>> wordMap = readWords(args[0]);

    // Print all permutation groups above size threshold
    printPermutations(wordMap, minGroupSize);
}

readWords

Metoden readWords tar ett filnamn och läser in ord från den filen till en tabell. Den tabell vi bygger upp har typen Map<String,List<String>>. Det betyder att nycklarna i tabellen är strängar och de värden vi associerar med varje nyckel är listor av strängar.

Exempel: Om vi läser strängarna

alarm
avart
avtar
larma
tarva

bygger vi denna tabell:

aalmr -> [alarm, larma]
aartv -> [avart, avtar, tarva]

(Nyckeln "aalmr" är associerad med en lista som innehåller strängarna "alarm" och "larma", och motsvarande för nyckeln "aartv".)

Denna metod innehåller kod för att läsa in ord från en fil. Jag kommer att ta upp I/O senare, men för den som är intresserad kommer en kortfattad förklaring. Ni kan läsa mer om I/O i Skansholms bok.

En try-catch sats används för att fånga olika typer av fel (exceptions). Eftersom läsning och skrivning av filer ofta orsakar fel kräver Java att såna operationer skrivs i en try-catch sats. (Jag kommer att säga mer om exceptions och IO i ett senare avsnitt.)

Vi skapar ett objekt av klassen BufferedReader. Det gör att vi kan läsa en rad i taget från filen, med metoden readLine. Om readLine returnerar null betyder det att vi har läst till slutet av filen, så vi loopar tills readLine returnerar null.

Om readLine inte returnerade null, betyder det att vi just läst in ett ord (i den lokala variabeln word). Vi slår upp word i tabellen wordMap, och binder resultatet till en variabel l med typ List<String>.

Om l är null betyder det att vi inte sett denna nyckel tidigare. I så fall skapar vi en ny lista, binder l till denna lista, och lägger in listan i tabellen.

Till sist lägger vi in ordet i listan och läser in ett nytt ord från filen. Sedan fortsätter while-loopen.

catch-satsen som står sist ser till att fånga olika typer av fel som kan uppstå vid hantering av filer (de kallas IOExceptions).

private static Map<String,List<String>> readWords(String fileName) {
    Map<String,List<String>> wordMap =
        new HashMap<String, List<String>>();
    try {
        BufferedReader in =
            new BufferedReader(new FileReader(fileName));

        String word = in.readLine();
        while(word != null) {
            String alpha = alphabetize(word);
            List<String> l = wordMap.get(alpha);
            if (l==null) {
                l = new ArrayList<String>();
                wordMap.put(alpha, l);
            }
            l.add(word);

            word = in.readLine(); // Read next word
        }
    }

    catch(IOException e) {
        throw new RuntimeException(e);
        //Don't know what to do with IO exceptions
    }
    return wordMap;
}

printPermutations

Metoden är ganska enkel. Vi går igenom tabellen wordMap och skriver ut de listor som är minst lika långa som minGroupSize. Metoden values returnerar en samling av alla värden som lagras i tabellen (kom ihåg att wordMap lagrar listor av strängar så vi får alltså en samling av listor).

Sedan loopar vi igenom samlingen av listor med en for-loop och tittar på en lista i taget. Om listan är minst lika lång som minGroupSize skriver vi ut den.

private static void printPermutations(Map<String,List<String>> wordMap,
                                      int minGroupSize) {
    for (List<String> l : wordMap.values()) {
        if (l.size() >= minGroupSize) {
            System.out.println(l.size() + ": " + l);
        }
    }
}

En testkörning

Vi avslutar med en testkörning. Som input tar vi följande svenska ordlista program/ordlista/svenska2.txt:

AB
abbedissa
abborre
abbot
abbé
abderit
abdikation
Abisko
abnorm
abonnemang
abonnent
abonnera
abort
Abraham
abrupt
abscissa
absid
absint
absolut
absolutist
...

Filen innehåller 24208 ord, så jag skriver inte ut hela.

Nå, testkörning ger:

$ java Perm svenska2.txt 4
4: [ikast, kista, sikta, skita]
6: [adel, dela, elda, lade, leda, leda]
4: [prisa, rispa, sirap, spira]
4: [rät, trä, trä, ärt]
4: [avel, elva, leva, vela]
4: [meta, meta, team, tema]
4: [avart, avtar, tarva, trava]
...

(Vissa ord, tex leda, står två gånger i ordlistan eftersom de är både substantiv och verb.)

Du hittar programmet här: program/collect/Perm.java