Tävlingsprogrammering/Uppgifter/Bokstavslek

Bokstavslek

Du får givet en bokstavssekvens med högst 20 bokstäver där alla bokstäver är olika och valda bland versalerna A − Z. Du ska nu genom att utföra högst n omflyttningar (där n ≤ 100) ändra bokstävernas ordning så att den sekvens som bildas kommer så tidigt som möjligt i alfabetisk ordning. Varje omflyttning innebär att du byter plats på två intill varandra stående bokstäver. Körningsexempel:

Sekvens ? KROATIEN
Antal omflyttningar ? 5

Bästa sekvens: AKORITEN

Kommentar: Sekvensen kan till exempel erhållas på följande sätt:
KROATIEN → KORATIEN → KOARTIEN → KAORTIEN → KAORITEN → AKORITEN

Lösning

Om man försöker lösa denna uppgift genom att testa alla möjligheter kommer man inte så långt. För en vanlig rekursiv lösning kan vi räkna med storleksordningen 19^100 = 7E+127 operationer, och antalet tillstånd är alldeles för stort (20! = 2.4E+18) för att man ska ha nytta av dynamisk programmering. En lösning som testar alla möjligheter ligger så långt ifrån att klara uppgiften att den inte ens ger 1 poäng.

Här gäller det tydligen att tänka åt ett helt annat håll. Den bildade sekvensen ska komma så tidigt som möjligt i alfabetisk ordning, så en påminnelse om hur man sorterar i alfabetisk ordning kanske kan vara till hjälp. Man börjar naturligtvis från första bokstaven, sätter alla sekvenser som börjar på A före dem som börjar på B o.s.v. Därefter går man till andra bokstaven och sätter alla som börjar på AB före dem som börjar på AC och alla som börjar på BA före dem som börjar på BC (men efter alla A-sekvenserna) o.s.v.

Det är här som tricket kommer in. Om vi kan skapa en sekvens som börjar på A så ska vi naturligtvis alltid göra det. Och går det inte att skapa en sekvens som börjar på A så ska vi försöka få till stånd en som börjar på B. Vi behöver inte ta hänsyn till övriga bokstäver när vi fattar det beslutet. En sådan algoritm, som väljer det bästa alternativet för stunden, brukar kallas för en girig (greedy) algoritm.

Hur vet vi då om det går att få fram ett A (på säg position k) till position 1? Det sätt som kräver minst omflyttningar är förstås att flytta A:et framåt (alltså mot sekvensens start) i varje omflyttning och inte bry sig om vad som händer med övriga bokstäver. Detta tar k - 1 omflyttningar så beslutet kan fattas bara genom att jämföra detta tal med det givna talet n. Observera att detta är ett "allt-eller-inget"-beslut. Om det går att flytta A:et nästan ända fram så ska vi inte göra det i detta läge, utan vi ska istället hitta den "lägsta" bokstaven som kan flyttas ända fram till tätpositionen.

Har man väl klurat ut hur man ska besätta den första positionen är det lätt att göra samma procedur för var och en av de följande positionerna. I varje steg subtraherar man från n antalet omflyttningar man använde för denna position. Förr eller senare blir n = 0, och man kan inte komma längre. Eller också får man en fullständigt sorterad sekvens redan innan omflyttningarna tar slut.

Det återstår en viktig invändning. Ingen tvivlar väl längre på att det alltid är bäst att flytta fram A:et om det går. Men om man nu skulle ha fler omflyttningar tillgängliga än det absoluta kravet för att ta fram A:et, kan det då inte vara bättre att förbruka ytterligare några omflyttningar när man tar flyttar A:et, på ett sådant sätt att man förbereder för fortsättningen genom att sätta de övriga bokstäverna i en lämplig ordning? Eller med andra ord: är det verkligen alltid bäst att flytta bokstaven "rakt fram"?

Lyckligtvis kan man visa att det åtminstone aldrig är sämre att flytta bokstaven rakt fram. Eller närmare bestämt, om man behöver m omflyttningar för att komma från utgångsläget till en godtycklig sekvens som har A på tätpositionen, så behövs det alltid högst m omflyttningar för att nå till samma sekvens om man går "omvägen" om den sekvens där man flyttat A rakt fram. Anledningen är att den direkta framflyttningen inte ändrar de inbördes relativa positionerna för övriga bokstäver. Därför kan flyttningen av A ses som en oberoende handling.

Ett exempel förklarar förhoppningsvis det mesta. Om man vill ändra en sekvens från CDAB till ABCD är det förstås lockande att låta B:et följa med A:et framåt om vi har tillräckligt med omflyttningar. Alltså:

CDAB → CADB → CABD → ACBD → ABCD

Men med den giriga algoritmen skulle man helt enkelt först flytta fram A två steg och sedan B två steg, vilket skulle ge samma antal omflyttningar. Nedan följer en lösning till problemet i sin helhet.

#include <stdio.h>
#include <string.h>

int main(){
  char ord[100],m;
  int nb,i,j,k,n;

  printf("Sekvens ? ");
  scanf("%s",ord);
  nb=strlen(ord);
  printf("Antal omflyttningar ? ");
  scanf("%d", &n);
  for(i=0;i<nb-1 && n>=0;i++) {   //Loopa över positionerna så länge det finns omflyttningar kvar
    //Följande rader bestämmer den lägsta bokstav m som är inom räckhåll för framflyttning till aktuell position
    m='Z'+1;   //Starta med en oändligt hög bokstav
    k=-1;
    for(j=i;j<nb && j-i<=n;j++){  //Observera att ingen omflyttning, alltså fallet j=i, alltid är ett alternativ
      if(ord[j]<m) {
	m=ord[j]; 
	k=j;
      }
    }

    for(j=k;j>i;j--) ord[j]=ord[j-1]; //Flytta om bokstäverna
    ord[i]=m;
    n -= k-i; //Minska antalet tillgängliga omflyttningar
  }
  printf("%s\n", ord);
  return 0;
};

Här är en lösning med (delar av) standardbiblioteket i C++:

#include <string>
#include <algorithm>
#include <iostream>

int main(){
	std::cout << "Sekvens ? ";
	std::string s;
	std::cin >> s;
	std::cout << "Antal omflyttningar ? ";
	size_t turns;
	std::cin >> turns;
	std::string::iterator exc,pos2;
	for(size_t pos=0;pos!=s.size() && turns;++pos){
		pos2=s.begin()+pos;
		exc=std::min_element(pos2,s.begin()+std::min(pos+turns+1,s.size()));
			//Hitta ett element som passar bättre, inom den radien vi har
		turns-=size_t(std::distance(pos2,exc));
		std::rotate(pos2,exc,exc+1);
			//Förenkling av framflyttningen ger rotation, även om det troligtvis inte är den mest tidseffektiva lösningen
	}
	std::cout << "\nBästa sekvens: " << s << std::endl;
	return 0;
}

Ett lösningsexempel i Java som både går att läsa och förstå.

import java.util.*;

public class Bokstavslek
{
	//Antalet omflyttningar vi får göra.
	static int antal;

	//Letar fram indexet för den första förekomsten av den angivna bokstaven.
	/*
	ord: Vår array med bokstäver som representerar vårt ord.
	find: Bokstaven vi ska hitta.
	from: Vi vill leta efter bokstaven framför detta index i arrayn.
	*/
	public static int findFirst(char [] ord, char find, int from)
	{
		for(int i = from; i<ord.length; i++)
		{
			if(ord[i]==find) return i;
		}

		return from;
	}

	//Avgör om det är möjligt att flytta bokstaven från ett index
	// till ett annat index inom antalet tillåtna drag.
	/*
	ord: Vår array med bokstäver som representerar vårt ord.
	to: Indexet vi vill flytta till
	from: Indexet vi vill flytta från.
	*/
	public static boolean isPossible(char [] ord, int to, int from)
	{
		if(from-to<=antal) return true;
		else return false;
	}

	//Flyttar en bokstav från ett index till ett annat.
	/*
	ord: Vår array med bokstäver som representerar vårt ord.
	to: Indexet vi ska flytta till
	from: Indexet vi ska flytta från.
	*/
	public static void move(char [] ord, int to, int from)
	{
		for(int i = from; i>to; i--)
		{
			char tmp = ord[i];
			ord[i] = ord[i-1];
			ord[i-1] = tmp;

			//Vi har förbrukat ett drag.
			antal--;
		}
	}

	public static void main(String [] klein)
	{
		Scanner scan = new Scanner(System.in);

		System.out.print("Sekvens: ");
		String sekvens = scan.next();

		System.out.print("Antal omflyttningar: ");
		antal = scan.nextInt();

		//Omvandlar ordet till en char-array som är trivsammare att hanskas med.
		char [] ord = sekvens.toCharArray();

		//Skapar en kopia av ordet och sorterar bokstäverna.
		//På så sätt vet vi enkelt vilken bokstav vi bör leta
		// efter härnäst. Den som ligger längst fram är bäst osv.
		char [] optimal = Arrays.copyOfRange(ord, 0, ord.length);
		Arrays.sort(optimal);

		//Håller reda på vilka bokstäver vi har flyttat till
		// sin "rätta" position.
		boolean [] used = new boolean [ord.length];
		Arrays.fill(used, false);

		//Flyttar bokstäverna.
		for(int i = 0; i<ord.length; i++)
		{
			//Flyttar bästa möjliga bokstaven till vår position.
			for(int j = 0; j<ord.length; j++)
			{
				//Om den inte redan står rätt förstås.
				if(ord[i]!=optimal[j])
				{
					//Om vi redan använt den här optimala bokstaven
					// så går vi vidare till nästa varv i loopen.
					//D.v.s. vi kollar nästa bästa bokstav.
					if(used[j]) continue;

					//Hittar indexet för vår önskade bokstav.
					int from = findFirst(ord, optimal[j], i);

					//Kollar om det är möjligt att flytta bokstaven till
					// vår önskade position.
					if( isPossible(ord, i, from) )
					{
						//Flyttar bokstaven.
						move(ord, i, from);

						//Nu har vi använt den, den står rätt.
						used[j] = true;

						//Avbryter den inre loopen. Nu är vi ju klara
						// med den här positionen. Gå vidare till nästa.
						break;
					}
				}
				else //Om den redan står rätt.
				{
					//Då har vi redan använt det valet ju.
					used[j] = true;

					//Och vi går vidare på nästa position.
					break;
				}
			}

			//Onödigt att bara fortsätta köra på.
			if(antal==0) break;
		}

		//Gör om den bästa sekvensen till en String.
		String svar = new String(ord);

		//Skriver ut svaret.
		System.out.println("\nBästa sekvens: " + svar);
	}
}

Lösning i det kungliga språket Haskell.

-- Bokstavslek
module Main where
import IO
import Data.Maybe
import Data.List

main = do {
	putStr "Sekvens ? ";
	skvns <- getLine;
	
	putStr "Antal omflyttningar ? ";
	antal <- getLine;
	
	putStrLn $ "Basta sekvens: " ++ (flyttaOm (read antal) skvns)
}

flyttaOm :: Int -> String -> String
flyttaOm _ [] = []
flyttaOm 0 s = s 
flyttaOm n s = best:(flyttaOm (n - (fromJust $ elemIndex best s)) (delete best s))
	where
	best = minimum $ take (n+1) s