augusti 19, 2007

Recension av Keith Devlin, Gary Lorden: The Numbers Behind Numb3rs: Solving Crime with Mathematics

TV-serien Numb3rs handlar om bröderna Don, FBI-agent, och den yngre brodern Charlie som är en matematikprofessor. Charlie är den egentlige "hjälten" i serien där hans matematiska begåvning (genialitet!) gör att Don kan lösa sina fall. Speciellt skoj är att matematiken i TV-serien är central och man har gjort sig möda om att göra den så korrekt som möjligt. Inte speciellt förvånande (för mina reguljära läsare) är serien en stor favorit.

Serien ska strax börja på fjärde säsongen och då passar det utmärkt att en bok om (kring) serien kommer ut. Det är matematikerna Keith Devlin och Gary Lorden som skrivit The Numbers Behind Numb3rs: Solving Crime with Mathematics (ISBN: 9780452288577) som gör en populärvetenskaplig exposé över matematiken som används i serien.

De två författarna är väl lämpade att skriva boken:
Keith Devlin, professor i matematik och är nog mest känd som Math Guy och skriver i den (populär)matematiska kolumnen Devlin's Angle (Archives). Devlin har även skrivit flera böcker (där 1988 års utgåva av Mathematics - the New Golden Age var en stor inspirationskälla för mitt matematikintresse).

Gary Lorden kände jag däremot inte till innan serien Numb3rs. Han är professor i matematik och "chief mathematics consultant" till TV-serien. Den senare rollen beskrivs t.ex. i CaltechNews-artikeln Crime and Computation.

Boken är "oteknisk" skriven och det krävs inga speciella matematiska förkunskaper (förutom sådana som normal skolgång bör ha gett). Det finns få formler/ekvationer och de som finns förklaras nästan alltid ingående.

När jag först läste om boken trodde jag att alla kapitel skulle behandla Numb3rs-relaterade saker och endast sådana. Man har istället valt en mer utökad variant och det saknas Numb3rs-koppling i några kapitel, t.ex. kapitel 5, "Image Enhancement and Reconstruction" som handlar om bildbearbetning i samband med efterverkningarna av lynchningen av Rodney King. Det görs också intressanta genomgångar av matematiken i och kring rättegångarna (som inte alls är med i TV-serien), t.ex. bevisvärdet av DNA-test och fingeravtryck samt kring urvalet av jurys. Denna utökning fungerar bra, även om det möjligen kan vara lite förledande i marknadsföringen.

En av de stora fördelarna med populärvetenskapliga böcker är att man blir inspirerad att läsa vidare i det ämne som behandlas. Tyvärr försvåras sådan vidareläsning genom att det i många kapitel inte finns några litteraturreferenser eller vidareläsningstips (det finns dock flera kapitel som har mycket referenser). Möjligen har författarna ansett att läsarna själv söker efter obekanta termer via sökmotorer eller Wikipedia. Fel approach enligt min mening.

Trots bristerna tycker jag om boken och rekommenderar den till de som också gillar TV-serien. Och rekommenderar TV-serien för den som inte sett den.

Bokens kapitel
Här är en listning av kapiteln och några kommentarer kring dem.


Se även
Devlins artikel om TV-serien NUMB3RS gets the math right.

Jag har köpt de två första säsongerna från Discshop. Tyvärr saknas här de kommentatorspår som finns i region 1-varianterna.

Recensionen New Book Explains How Math Can Help Solve Crimes finns även som pratversion inklusive författarnas (autentiskt återgivna förutsätter jag) röster.

Sajten Redhawke NUM3RS med länkar till matematiska begrepp

Dr. Andrew Nestler's Analysis of NUMB3RS

Min favoritblogg i Numb3rsiana: num3rs blog

Succén med TV-serien har även knoppat ett samarbete mellan CBS, Texas Intstrument och National Council of Teachers of Mathematics i form av sajten We All Use Math Every Day där lärare kan hämta material som kopplas till de olika avsnitten. Aktiviteter för respektive säsong (sorterad i bloggordning):
Season 1
Season 2
Season 3

Posted by hakank at 11:21 FM Posted to Böcker | Machine learning/data mining | Matematik | Social Network Analysis/Complex Networks | Comments (0)

juli 23, 2007

Terence Tao videoföreläsning 'Structure and Randomness in the Prime Numbers' (matematik, talteori)

Terence Tao anses vara en av matematikens klarast lysande stjärnor. Enligt artikeln Terence Tao: The "Mozart of Math":


"Terry is like Mozart -- except without Mozart's personality problems," said John Garnett, professor and former chair of mathematics in the UCLA College. "Mathematics just flows out of him." "Mathematicians with Terry's abilities appear only once in a generation," said Garnett. "He's probably the best mathematician in the world right now. Terry can unravel an enormously complicated mathematical problem and reduce it to something very simple. We're amazingly lucky to have him at UCLA."


Hans videoföreläsning Structure and Randomness in the Prime Numbers (.smil videoformat) är en populärt hållen och mycket trevlig föreläsning om talteori, t.ex. primtalstvillingar och Riemann-hypotesen (som anses vara ett av de knepigaste matematiska problemen). Slides (PDF).

(Not: Jag hade lite problem med att videoströmmen slutade att strömma efter cirka 8 minuter och efter cirka 35 minuter. Det vara bara att starta om på nytt. Ibland funkade det att snabbspola, men inte alltid.)


Se även
Taos blogg What's new (som ersätter den gamla "proto-bloggen" What's new)
Information for media, en samling av artiklar om Tao
En kort TV-biografi (strömmande bilder, alltså)
Några kapitel (.ps-fil) från boken Solving Mathematical Problems: A personal perspective. Och kan beställas t.ex. här (ISBN: 9780199205608).


(Via den relativt nyfunna favoritbloggen God Plays Dice.)

Posted by hakank at 06:18 EM Posted to Matematik | Video podcasts | Comments (1)

februari 19, 2007

Den som ändå bodde kring Uppsala: 1 mars pratar Persi Diaconis om matematik och trolleri

Den 1 mars 2007 är det Celsius-Linneföreläsning å Uppsala Universitet. Celsius-föreläsningen är Persi Diaconis som föreläser om Mathematics and magic tricks

bulletin.se-notisen Trollkonster och empatiska djur på årets Celsius-Linnéföreläsningar beskriver ner:


Celsiusföreläsningen hålls av Persi Diaconis, professor i statistik och matematik vid Stanford University. Diaconis har använt matematiken för att utveckla magiska trick, och är bland annat känd för att ha bevisat att en vanlig kortlek måste blandas sju gånger för att vara ordentligt blandad. Sättet på vilket magiska trick fungerar är minst lika fascinerande som tricken själva, menar han, och kommer att visa detta bland annat genom att demonstrera några trick.

Är det någon besökare som vill ta anteckningar och publikt (eller privat) delge dem?


(Det finns fler Linnéevenemang.)

Posted by hakank at 05:57 EM Posted to Husgudar | Matematik | Trolleri, magi etc | Comments (4)

oktober 22, 2006

Dagslänkar 2006-10-22 - Om senaste avsnittet av numb3rs

Om senaste numb3rs-avsnittet ("Traffic").

numb3rs blog: Traffic as a fluid flow

The Econophysics Blog: Randomness & the 'Ludic Fallacy' on Numb3rs

Texas Instrument har en sajt kring TV-serien:
We All Use Math Every Day, där t.ex. Activities med länkar till nedladdningsbara PDF-filer etc.

Posted by hakank at 09:33 FM Posted to Matematik | Comments (0)

juli 10, 2006

Ytterligare forskning kring fotboll

Jaha, nu är VM-fotbollen över och det kommer nog att kännas lite tomt kring 21-tiden de närmsta dagarna. Kul att ha sett de flesta matcherna, med eller utan bok att ta till i de få fall då det varit riktigt tråkigt.


Under de gångna veckorna har några fotbollsforskningslänkar samlats på hög och det är dags att rensa.

Slate: World Cup Game Theory - What economics tells us about penalty kicks., av Tim Hartford som skriver kolumnen The Undercover Economist och för övrigt ganska nyss kommit ut med boken The Undercover Economist (ISBN: 0316731161), och som ännu nyssare erhållits.

Gelf Magazine: The Game Theory of Penalty Kicks

The Sports Economist: Tinkering with the World Cup
The Sports Economist: Statistical analysis of World Cup fouls

Ivars Peterson MathTrek-artikel om den nya konstruktionen av bollen: Bending a Soccer Ball

The Econophysics Blog: Predictive Markets for the World Cup?

Freakomonics Blog: What can the World Cup teach us about markets?
Freakonomics Blog: In soccer, it is not whether you win or lose, but how you play the game
Are stars born or made? Here’s what World Cup 2006 has to say on the issue.
Marginal Revolution: Why I find soccer boring

Bok: John Wesson The Science of Soccer (ISBN: 0750308133) som handlar om både fysikaliska delarna av fotboll (t.ex. vinklar och krafter) och mer matematiska, t.ex. spekulation i varför planen respektive målen är av de mått som de har (formel gives), om straffläggning etc. Har endast bläddrat i boken, men den verkar spännande.


Se även
Mer om forskning kring fotboll
Straffsparkar i fotboll och annan fotbollsmatematik
Optimering av fotbollstittande


Andra bloggar om: .

Posted by hakank at 11:20 FM Posted to Matematik | Spelteori och ekonomi | Sport, idrott, hälsa | Comments (0)

juni 26, 2006

Mer om forskning kring fotboll

I Studio Ett intervjuades nyss Patric Andersson, forskare vid Handelshögskolan: Finns det psykologiska mål? Vi gör ett försök att skilja mellan myter och sanningar i alla påståenden dessa dagar om fotboll, världens största sport. Patric Andersson, forskare vid Handelshögskolan deltar.. Djuplänk.

Presentation av Patric Anderssons forskning finns t.ex. i pressmeddelandet Forskning slår hål på myter om fotbollens ekonomi och psykologi. Den workshop man talar om är Workshop om fotbollens ekonomi och psykologi, och det mer fullständiga.programmet finns på EconPsyFootball06 - The University of Mannheim workshop on Economics and Psychology of Football (tyvärr hittades inga nedladdningsbara papers där).


Se även
Paric Andersson, Mattias Ekman, Jan Edman: Forecasting the fast and frugal way: performance and information-processing strategies of experts experts when predicting the World Cup 2002 in soccer (PDF)

DI.se: Experternas gissningar inte bättre än dina egna
DI.se: Ny studie från handelshögskolan dömer ut analytiker (2004-09-29)


Optimering av fotbollstittande som innehåller länkar till andra forskningsrön om fotbollsforskning.
Straffsparkar i fotboll och annan fotbollsmatematik


Andra bloggar om: , .

Posted by hakank at 05:53 EM Posted to Matematik | Sport, idrott, hälsa | Comments (0)

juni 19, 2006

Lite nördmusikmotvideos

Eftersom jag inte tycker att Botten Anna-låten (knuff-länk) är speciellt bra (även om idén att förväxla en båt med en chatbot är skoj men det är en långsökt koppling och en väldigt dålig ordvits, (*)) så kommer här några motvideos:

* statz rapperz
* Finite Simple Group (of Order Two) (se vidare Klein Four Store).


(*) Association: Jag undrar hur Magrittes tavlor egentligen låter, och Dalis. Någon bara måste har tonsatt dem.


Andra bloggar om: , .

Posted by hakank at 07:04 EM Posted to Matematik | Comments (3)

juni 13, 2006

Mathematisk podcast: mathgrad podcast

Mathgrad Podcast är en sajt med podcastar kring vardagsmatematik, dvs mer eller mindre vardagsproblem sett ur matematiska ögon. Se exemplen nedan.

Målet med sändningarna beskrivs på följande sätt:


Welcome to the home of the Mathgrad Podcast where we discuss everyday math for everyday people. My goal is to discuss the mathematics behind many real life topics in a way that even the worst mathphobe will gain some insight.

Samt att fresta till vidare studier av matematik.

Här finns en lista över programmen. Det finns även Show notes, i skrivande stund endast för de fem första programmen.

Några exempel:
* Deal or no deal - Mathematics behind deal or no deal

* Moore's Law and Exponentials - Just how fast do things grow that grow exponentially

* Mathematics of Sharing - How can we divide things so that everyone is happy?

* Voting - Why the 2 party system? - We examine the mathematics of voting theory, learn some bad news about fair voting, and look at some specific and often used voting schemes.

* Maps and the lies they tell us - We explore the mathematics behind maps.


Jag har ännu inte lyssnat på alla programmen, men de jag hört har varit skoj.

Andra bloggar om: , .

Posted by hakank at 07:31 FM Posted to Matematik | Comments (4)

juni 08, 2006

Vilken boll är rundast? Slumpmässighet i sporter

I P1 pratades precis om att fotboll är den mest slumpmässiga sporten. Matematikern som intervjuades, Torbjörn Lundh, har skrivit Which ball is the roundest? – a suggested tournament stability index (PDF).

Abstract:


All sports have components of randomness that team not to win every game. According to many spectators of the charm when following a competition or a match. less of this unpredictability? We suggest here a general stability index, which could measure this randomness factor and different sports. As an illustration we use exemplify squash, and soccer. Results will also be given on tournaments football, ice-hockey, and handball. Furthermore, we will optimization questions that turned up on the way.

(Funnen via sidan Vetenskapsfestival 2006)

Uppdatering
Intervjun kan (förhoppningsvis) ålyssnas via följande djuplänk.

Malin på Vetenskapsnytt skrev i vintras (onsdag, januari 04, 2006) om en liknande undersökning: Fotboll är den mest spännande sporten, säger forskare, där följande paper omnämns:
E. Ben-Naim, F. Vazquez, S. Redner What is the most competitive sport? (arXiv.org)


We present an extensive statistical analysis of the results of all sports competitions in five major sports leagues in England and the United States. We characterize the parity among teams by the variance in the winning fraction from season-end standings data and quantify the predictability of games by the frequency of upsets from game results data. We introduce a mathematical model in which the underdog team wins with a fixed upset probability. This model quantitatively relates the parity among teams with the predictability of the games, and it can be used to estimate the upset frequency from standings data. We propose the likelihood of upsets as a measure of competitiveness.


Andra bloggar om: , .

Posted by hakank at 07:42 FM Posted to Matematik | Sport, idrott, hälsa | Statistik/data-analys | Comments (3)

april 22, 2006

Divisorträd: unika sätt att göra konsekutiva uppdelningar

Vilka - och hur många - unika sätt kan man göra följande "konsekutiva delningar" av ett antal saker. Tänk t.ex. på de olika unika sätt man kan dela upp N antal spelkort i olika högar. Metoden man arbetar med är följande:

- börja med en hög av N saker

- dela upp dessa saker i ett antal högar så att det är lika många saker i varje hög

- ta en av dessa högar och fortsätt på samma sätt tills det bara finns
en sak i varje hög

Eller på ett något mer matematiskt språk: på vilka - och hur många - olika unika sätt man kan dela upp ett tal i dess divisorer (förutom 1 och talet själv).

Not: Eftersom nedanstående inte har (matematiskt) bevisats så är det endast en hypotes (en förmodan).

Uppdatering. Hmm, jag har hittat en inkonsekvens i nedanstående. Inte bra. Återkommer...


Program: Divisor tree
Det program som används för att undersöka dessa konsekutiva delningar är Divisor tree / / Consecutive dealing in heaps. Nedanstående förklaringar är förhoppningsvis tillräckligt för att förklara programmet.

Notera att programmet endast arbetar med värden mellan 2 och (lite halv godtyckligt) 30000 av datorsnällhetsskäl.


Inledande exempel
Låt oss göra det mer åskådligt med 16 saker (t.ex. 16 spelkort).

För N = 16 finns det 4 olika sätt.


16 / 2 heaps = 8 things in each heap (2 -> 8 -> ..)
     8 / 2 heaps = 4 things in each heap (2 -> 4 -> ..)
         4 / 2 heaps = 2 things in each heap (2 -> 2 -> 1)
     8 / 4 heaps = 2 things in each heap (4 -> 2 -> 1)
16 / 4 heaps = 4 things in each heap (4 -> 4 -> ..)
     4 / 2 heaps = 2 things in each heap (2 -> 2 -> 1)
16 / 8 heaps = 2 things in each heap (8 -> 2 -> 1)

Found 4 ways for N = 16.

Beskrivning av det första (unika sättet):
* Först har vi 16 saker.
* Dessa delas upp i två högar med 8 saker i varje hög.
* Vi tar en av dessa två högar och har nu en hög med 8 saker. Denna delar vi upp i 2 högar så vi får 4 saker i varje hög.
* Vi tar en av dessa högar och delar upp i 2 högar med två saker i varje hög.
* Vi tar sedan en av dessa högar och delar ut i 2 högar med 1 sak i varje hög.

Men sedan kan vi inte gå vidare eftersom det nu är endast 1 sak i varje hög. Man skulle i och för sig kunna dela upp 1 sak i 1 hög i det oändliga men det är inte tillåtet i detta spel. Regel: När det endast finns 1 sak i en (färdigutdelad) hög är man klar med denna uppdelnin.

Antal saker som fanns i de högar vi använder under utdelningen är: 16, 8, 4, 2, (1).

Tittar vi på exempelkörningen ser vi att en unik väg (ett unikt sätt) är avslutat om raden avslutas med -> 1. Står det däremot -> .. så fortsätter uppdelningen och man går vidare till nästa (inskjutna) rad. Denna trädliknande struktur är anledningen till att det kallas för divisorsträd där de olika uppdelningssätten grenar ut sig. (Möjligen skulle det kunna kallas för divisorsstad eftersom det är vägar vi pratar om eller divisorsskog efterom det är flera träd med olika grenar, men ingendera av dessa känns lika naturligt som -träd).
De 4 olika sätten för N = 16 är följande, där talen anger antal saker i varje hög. Den första raden motsvarar alltså den långa beskrivningen ovan.

16 -> 8 -> 4 -> 2
16 -> 4 -> 2
16 -> 4 -> 2
16 -> 8 -> 2

För N=12 finns det 5 vägar (avslutas med 2 eller 3)

12 / 2 heaps = 6 things in each heap (2 -> 6 -> ..)
     6 / 2 heaps = 3 things in each heap (2 -> 3 -> 1)
     6 / 3 heaps = 2 things in each heap (3 -> 2 -> 1)
12 / 3 heaps = 4 things in each heap (3 -> 4 -> ..)
     4 / 2 heaps = 2 things in each heap (2 -> 2 -> 1)
12 / 4 heaps = 3 things in each heap (4 -> 3 -> 1)
12 / 6 heaps = 2 things in each heap (6 -> 2 -> 1)

Found 5 different way(s) for n = 12.


Primtal
Om det finns ett primtal antal saker i en hög finns det endast ett sätt (en väg) att dela upp i lika antal högar, nämligen att dela så att det finns en sak i varje hög. T.ex. om man har 13 kort så kan man endast dela ut dem i 13 olika högar med 1 kort i varje hög.

En väg avslutas alltså om det blir en hög innehåller primtal stycken saker. Eller mer korrekt: Om det är primtal antal stycken blir nästa uppdelning så många högar med 1 sak i varje hög.


Primtalskvadrater
För 4 saker så finns det bara ett sätt: nämligen att dela upp i två högar med två saker i vardera.

4 / 2 heaps = 2 things in each heap (2 -> 2 -> 1)

Found 1 different way(s) for n = 4.

Detta är ingen slump. För varje kvadrat av primtal (2^2=4, 3^2=9, 5^2=25, 7^2=49 osv) så finns det endast ett sätta att göra uppdelningen.

Båda dessa specialfall, primtal och primtalskvadrater utnyttjas i den rekursiva algoritm för att räkna ut antalet unika konsekutiva uppdelningar, och som beskrivs nedan.


Antal uppdelningar, heltalssekvenser
Om man nu räknar antalet unika sätt att göra denna typ av uppdelningar för N = 1.. 32 får vi följande heltalssekvens:


1,1,1,1,1,2,1,2,1,2,1,5,1,2,2,4,1,5,1,5,2,2,1,12,1,2,2,5,1,9,1,8

Här är en graf över sekvensen för N = 1 .. 512:

Ett bra sätt att analysera denna typ av matematiska (eller algoritmiska) strukturer är att se om det finns andra strukturer som har samma heltalssekvens. Det gör man lämpligen via On-Line Encyclopedia of Integer Sequences (som beskrivits tidigare i Heltalssekvenser). Ovanstående sekvens fanns inte med! Inte heller hittades sekvensen via superseeker som är en tjänst där man mailar in sekvensen och där systemet gör väldigt många olika typer av transformationer av sekvensen. Inte heller där hittades sekvensen.

Så det verkar som om ovanstående sekvens är ganska ovanlig. Lite märkligt eftersom det känns som en "naturlig" metod. Vi ser nedan att det är en "kusin" till en känd heltalssekvens.


Rekursiv definition
Ovanstående sekvens räknades ursprungligen ut genom att skapa vägarna i en tidig version av programmet Divisor tree, men sedan skapades (upptäcktes) en metod för att räkna ut dessa värden mycket enklare. Här är pseudokoden för metoden:


divtree(n):
   # n > 0
   if n == 1 then value = 1 # specialfall för n = 1
   elsif prime(n) then value = 1 # primtal
   else if prime_square(n) then value = 1 # kvadrat av ett primtal
   else if # annars: loop igenom divisorerna av n
     for div = divisors(n) do
     next if div == 1 or div == n # se kommentaren nedan
     value = value + divtree(div) # summera divisorernas värden rekursivt

   return value

Notera raden med "next" i for-loopen. Den innebär att om divisorn är 1 eller n så adderar man inte något värde för denna divisor. (Det är genom att förändra next-raden som vi hittar sekvensens kusin. Se nedan) Notera också att det är en rekursiv definition.

Pratversionen av metoden är ungefär: Om N är 1, ett primtal eller en primtalskvadrat så finns det ett unikt sätt att göra en delning. Om N är något annat så summerar man divtree-värdena för N:s divisorer (alla divisorer förutom 1 och N själv).

Det tarvar kanske ett exempel på detta, så låt oss titta på N = 24 (dvs 24 saker). Först divisorsträdet:

24 / 2 heaps = 12 things in each heap (2 -> 12 -> ..)
     12 / 2 heaps = 6 things in each heap (2 -> 6 -> ..)
         6 / 2 heaps = 3 things in each heap (2

Posted by hakank at 11:09 FM Posted to Matematik | Program | Comments (2)

april 19, 2006

de Bruijn-sekvenser av godtycklig längd

För några år sedan skrevs ett program för att skapa de Bruijn-sekvenser, som kortfattat kan förklaras som en sträng (cykel) som innehåller ("testar") alla förekomster av delsträngar, där delsträngarna är representationer av tal. Mer förklaringar och exempel ges i de Bruijn-sekvenser (portkodsproblemet) och programmet de Bruijn sequence. I slutet finns även några andra referenser.

De metod som dessa sekvenser konstrueras ger endast stränglängder med jämna potenser, dvs 2^2 = 3, 2^3 = 8, 3^2 = 9, 3^3 = 27 osv. En fråga som ställdes tidigt var: Kan man skapa sådana sekvenser för en godtycklig längd, t.ex. 11, 17 eller 52 och för godtycklig bas, 2, 6,11 etc? Basen är alltså den kodning av talen man använder, där.basen 2 ger en binär representation (0,1), basen 3 använder 0, 1,2 osv.

Svaret på frågan är: Visst kan man det!

Än så länge har jag dock inte kommit på en vacker algoritm som den som finns för "vanliga" de Bruijn-sekvenser. Se The (Combinatorial) Object Server, Information on necklaces, unlabelled necklaces, Lyndon words, De Bruijn sequences (i slutet på sidan finns det länkar för att ladda ner källkod).


Programmet "de Bruijn arbitrary sequences"
Programmet de Bruijn arbitrary sequences visar några av resultaten av denna undersökning. Troligen behövs lite förklaringar av programmets metoder och parametrar och sådant bistår jag så gärna med.


Metoden: slumpa cykler
Principen för att skapa dessa sekvenser är enkel: Skapa en de Bruijn-graf och slumpa fram cykler i denna graf tills en av korrekt längd hittas.

Denna slumpmässighet är det som gör att programmet inte tillåts arbeta med speciellt stora värden.


de Bruijn graf
En de Bruijn-graf är en graf där kopplingarna mellan talen (noderna) följer "de Bruijn-regeln" att ett tals suffix ska vara ett annat tals prefix i deras *-ära representation. T.ex. det binära talet 000 kan kopplas till 001, talet 001 med 010 och 011 osv. Baser större än 2 hanteras på motsvarande sätt.

Exempel: Här visas kopplingarna i grafen för n = 16 i basen 2. Inom parentes visas den binära representation av talet.

0: 0 1 (0000)
1: 2 3 (0001)
2: 4 5 (0010)
3: 6 7 (0011)
4: 8 9 (0100)
5: 10 11 (0101)
6: 12 13 (0110)
7: 14 15 (0111)
8: 0 1 (1000)
9: 2 3 (1001)
10: 4 5 (1010)
11: 6 7 (1011)
12: 8 9 (1100)
13: 10 11 (1101)
14: 12 13 (1110)
15: 14 15 (1111)

Här är en mer grafisk representation (skapat med programmet dot).
(klicka på bilden för att förstora den).


Antalet noder
Antalet noder i de Bruijn-grafen räknas ut enligt följande (motsvarar nearest_power i pseudo-koden nedan):
- om n är en jämn potens för basen används n noder (talen 0..n-1). T.ex. n=16 bas 2 är 2^3 är en sådan jämn potens.
- annars är antalet noder den närmaste efterföljande jämna potensen för basen. Exempel: För n=7 (bas 2) blir det 8 noder (2^3=8 ). För n=21 bas 3 blir det 27 noder (3^3=27 ) osv.

Kopplingsgrafen är enkel att räkna ut och principen ses nog vid närmare granskning av några exempel. Hur som helst kommer här pseudo-kod:


# nearest power in the choosen base, or N itself if N is a power
next_pow = nearest_power(N, base)
half_pow = next_pow / base;

for num (0..next_pow-1) {
   for b (0..base-1) {
     x = base * (num % half_pow);
     conn = x + b;
     graph->add_edge(num, conn); # connect num -> conn
   }
}


Kort förklaring av programmet
Programmet har en del parametrar vilka här förklaras.

N (2..64): Det är stränglängden (eller antal objekt). Kan vara mellan 2 och 64.

Base (2..4): Basen som ska användas. T.ex. för bas 2 är det binär representation (0,1). Giltiga värden är 2,3 eller 4.

Type: normal / reversed: Normal innebär att sekvensen visas normalt från vänster till höger och de binära (bas-ära) talen kodas normal (7 binärt är "0111"). Det lägsta talet börjar decimalcykeln. Reversed är då man vänster på allting: de binära (etc) koderna är omvända (7 visas som "1110") och det högsta talet i decimalcykeln visas först.

Show connections: Visar kopplingarna för den de Bruijn-graf som byggs upp.

Show sequence: Här visas de individuella representationerna.


Exempel
Här är ett exempel på på en av många möljiga sekvenser för n = 52 i basen 4:

Sequence:0001012131301132230220330300323123212013332002102331

Cycle (in decimal): 0 1 4 17 6 25 39 29 55 28 49 5 23 30 58 43 44 50 10 40 35 15 60 51 12 48 3 14 59 45 54 27 46 57 38 24 33 7 31 63 62 56 32 2 9 36 18 11 47 61 52 16

Sequence check:

000101213130113223022033030032312321201333200210233100
000 (0)
 001 (1)
  010 (4)
   101 (17)
    012 (6)
....


Begränsningar
Som ovan nämnts bygger programmet på en slumpning av cyklerna. Det kan ta en stund att slumpa fram cykler av korrekt längd i stora grafer så finns det några begränsningar för att datorn inte ska bli sönderkörd:

N: mellan 2 och 64
base: mellan 2 och 4

Om någon läsare nu (eller sedan) upplever ett starkt behov av sådana sekvenser med större längd / bas så är det bara att kontakta mig (hakank@bonetmail.com så kan vi säkert ordna något.


Vidare utveckling
Denna slumpmässiga metod fungerar om det är relativt små värden av N och bas. Men för större värden är det inte en tillgänglig metod. I stället bör en deterministisk algorim skapas.

Ett pågående projekt är också att försöka minska antalet noder i grafen så att det inte blir så många möjliga cykler att leta igenom.


Not
Jag är osäker på om ovanstående fortfarande kan kallas för en de Bruijn-sekvens när man använder denna alternativa approach.


Se även
de Bruijn sequence (den "vanliga" formen)
de Bruijn-sekvenser (portkodsproblemet)

MathWorld deBruijnSequence
COS: Information on necklaces, unlabelled necklaces, Lyndon words, De Bruijn sequences

Posted by hakank at 06:52 EM Posted to Matematik | Program | Comments (0)

april 18, 2006

Choco: Constraint Programming i Java

Bakgrund
Mitt intresse för Constraint Programming (CP) (som tidigare kallades Constraint Logic Programming, CLP) väcktes för ett antal år sedan strax efter en företagskamp (som kort beskrevs i Uppdaterat program: AnaCheck), där ett av uppdragen var följande matematiska pyssel:

Vilken är den minsta differensen man kan få mellan två tal om man måste använda samtliga siffror (0..9) exakt en gång?

Lösningen presenteras nedan.

Ungefär samtidigt stötte jag på Constraint (Logic) Programming och med detta och liknande pyssel i bakhuvudet, och blev väldigt fascinerad av programmeringsparadigmet. Kanske inte så förvånande eftersom många standardexempel är just matematiska pyssel.

Tanken är att man endast behöver skriva de problemspecifika villkoren (constraints), sedan får systemet lista ut bästa sättet att lösa problemet. Det finns många olika metoder och heuristiker för att lösa problemen, och ibland måste hjälpa till så att lösningen kommer denna sidan regnbågen eftersom vissa problem är mycket tunga.

Ett citat som ofta nämns i sammanhanget är Eugene C. Freuder (CONSTRAINTS, April 1997)


Constraint programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it..


Prologbaserade system
I början arbetade jag mestadels med logikprogramspråket Prolog som "moderspråk", Sicstus Prolog samt ECLiPSe Constraint Programming System (det senare inte att förväxlas med utvecklingsmiljön med ungefär samma stavning).


Imperativa språk
Som komplement till de Prologbaserade systemen har jag letat efter mer imperativa - samt icke-kommersiella - moderspråk såsom Java, C, C++, Perl, Python, eftersom vissa saker är lättare att programmera med sådana språk (men ibland svårare) En av dessa implementationer Python-constraint och nämns i kommentarerna till Sesemans matematiska klosterproblem samt lite Constraint Logic Programming.


Choco
Så till det system jag har kollat i nyligen: det Java-baserade Choco. I slutet av anteckningen finns fler referenser.

Choco är snabbt och det har en stor mängd funktioner. Exemplen nedan är endast för "finita domäner" (löses med hjälp av heltal), men det finns även domäner med reella tal samt mängder.

Det är dock inte lika elegant att skriva constraints som i Sicstus/ECLiPSe, vilket vi nu kommer att titta på.


Minsta differensproblemet - en jämförelse av kodskrivning
För att tydliggöra skillnader och likheter mellan Choco och de Prologbaserade systemen visas hur minsta differensproblemet kan lösas i respektive system.

I ECLiPSe skriver man själva constraint-delen av problemet på följande sätt; i Sicstus Prolog skriver man snarlikt. Obs: koden är inte riktigt komplett att bara köra.

:-lib(fd), lib(fd_search), lib(fd_global),lib(fd_domain).

% ....

LD = [A,B,C,D,E,F,G,H,I,J], % deklarera de 10 variablerna
LD :: [0..9], % intervallet för variblerna, mellan 0 och 9
fd_global:alldifferent(LD), % alla värden ska vara olika

%
% constraints
%

% A + B + C + D + E = F + G + H + I + J
X #= 10000*A+1000*B+100*C+10*D+E,
Y #= 10000*F+1000*G+100*H+10*I+J,

% differensen ska bli positiv
X #< Y,

% differensen
Diff #= Y - X,

% minimera differensen (Diff) samt heuristik för att hitta lösningen snabbt
minimize(search(LD,0,anti_first_fail,indomain_max,credit(64,bbs(15)),[]),Diff).

Elegant och lite magiskt, eller hur?

Motsvarande Choco-program är lite längre, främst eftersom det saknas syntaktiskt socker. Det går att pressa antalet rader (sådant har gjorts) men här görs en mer expressiv form för att jämförelsen ska bli tydligare. Programmet finns att ladda ner här nedan.


// Choco program

import choco.Problem;
import choco.*;
import choco.integer.*;

public class LeastDiff {

public static void main(String[] args) {
new LeastDiff().puzzle();
}

public void puzzle () {
Problem pb = new Problem();

// definiera variablerna A .. J så att dess värden är mellan 0 och 9
IntDomainVar A = pb.makeEnumIntVar("A", 0, 9);
IntDomainVar B = pb.makeEnumIntVar("B", 0, 9);
IntDomainVar C = pb.makeEnumIntVar("C", 0, 9);
IntDomainVar D = pb.makeEnumIntVar("D", 0, 9);
IntDomainVar E = pb.makeEnumIntVar("E", 0, 9);
IntDomainVar F = pb.makeEnumIntVar("F", 0, 9);
IntDomainVar G = pb.makeEnumIntVar("G", 0, 9);
IntDomainVar H = pb.makeEnumIntVar("H", 0, 9);
IntDomainVar I = pb.makeEnumIntVar("I", 0, 9);
IntDomainVar J = pb.makeEnumIntVar("J", 0, 9);

IntDomainVar[] letters = {A,B,C,D,E,F,G,H,I,J};

IntDomainVar Diff = pb.makeBoundIntVar("Diff", 0, 10000);

// Temporära variabler
IntDomainVar X = pb.makeBoundIntVar("X", 0, 100000);
IntDomainVar Y = pb.makeBoundIntVar("Y", 0, 100000);

// alla värden ska vara unika
for (int i = 1; i <= 9; i++) {
for (int j = 0; j <= 9; j++) {
if (i==j) {
continue;
}
pb.post(pb.neq(letters[i], letters[j]));
}
}

// X = A+B+C+D+E
pb.post(pb.eq(X, pb.scalar(new int[]{10000, 1000, 100, 10, 1},
new IntDomainVar[]{A,B,C,D,E})));

// Y = F +G + H + I + J
pb.post(pb.eq(Y, pb.scalar(new int[]{10000, 1000, 100, 10, 1},
new IntDomainVar[]{F,G,H,I,J})));

// Diff = X - Y
pb.post(pb.eq(pb.minus(X, Y), Diff));

// minimera skillnaden
pb.minimize(Diff,false);

// nu ska vi lösa problemet
Solver s = pb.getSolver();
pb.solve(true);

// Skriv ut lösningen
System.out.println("Result: "+ A.getVal() + B.getVal() + C.getVal() +D.getVal() + E.getVal() + " - " + F.getVal() + G.getVal() + H.getVal() + I.getVal() + J.getVal() + " = " + Diff.getVal() );

} // end puzzle

} // end class


Lösningen som ges av dessa båda program är samma, nämligen

50123 - 49876 = 247


Några körbara (kompilerbara) Choco-program
Här är källkoden till några andra mindre Choco-program, varav några är standardproblem inom constraint programming. Choco-distributionen innehåller några andra.

LeastDiff2.java: Ovanstående exempel
FurnitureMoving.java: Planering av möbelflyttande, använder cumulative.
Knapsack.java: ett enkelt knapsack-problem (minimize)
Zebra.java: ett standardpyssel
Seseman.java: Choco-versionen av Sesemans matematiska klosterproblem


Se även
om Choco:
Choco: projektsidan på Sourceforge
Wiki
User guide
Choco API
Forum

om constraint programming
Roman Barták: On-line Guide to Constraint Programming
Roman Barták: Constraint Programming: In Pursuit of the Holy Grail (PDF)


tidigare skrivet om C(L)P
Sesemans matematiska klosterproblem samt lite Constraint Logic Programming
Automatisk "lösning" av Minesweeper i Mozart/Oz


JaCoP är ett annat Javabaserat system, utvecklat vid Lunds Universitet som man kan få tillgång till om man frågor någon av dess skapare. Har inte kollat in det så mycket ännu, men det verkar också trevligt.

Posted by hakank at 09:59 EM Posted to Constraint Programming | Matematik | Pyssel | Comments (0)

mars 05, 2006

Ivars Peterson blogg Math Trek (nöjesmatematik)

En av mina stora favoriter inom nöjesmatematiken (recreational mathematics) är Ivars Peterson. För ett tag sedan begåvades han med en blogg: MathTrek. Det är troligen inget slump att det råkar vara samma namn som dennes matematikkolumn.


Se även
Math Trek archives .
MatheMUSEments: Articles about math in everyday life.
Bokussökning: Ivars Peterson.

Rekreationell matematik ocn annat tankegodis

Posted by hakank at 09:06 FM Posted to Matematik | Comments (0)

november 21, 2005

Bloggforum 3 - Några tankar samt Isobels och Lisas pizzeriabordsproblem

Nedanstående är inte avsedd att vara någon fullständig redovisning av vad som hände eller gjordes under Bloggforum 3 eller helgen kringgärdande detta evenemang. Snarare är det tankar kring det man pratade om i och utanför det formella programmet. Vad gäller fysiska trajektorier och de yttre omständigheterna kan refereras till Mats Anderssons utmärkta och innehållsrika Summering av Bloggforum 3.

Ett stort tack till Rebecca Crusoe, Stefan Geens och Erik Stattin för deras fina arbete att anordna ett så intressant program, och som gjorde det möjligt att få förmånen träffa så väldigt trevliga och intressanta personer.

Det har skrivit väldigt mycket redan om forumet. De naturliga samlingspunkterna är
- Bloggforum 3
- del.icio.us/tag/bloggforum3

Bloggen är död
Temat (med glimten i ögat) för detta forum var "Bloggen är död". Det är egentligen absurt att nu när begreppet blogg håller på att bli känt för en större allmänhet anser man att bloggen är död.

Personligen har jag sedan ett tag känt att formatet känts begränsande i vissa fall. I såväl bloggverktyg som kommentarer finns en tendens att endast bry sig om det som skrevs nyligen. Det innebär att det man skrivits tidigare (t.ex. en vecka, en månad eller ett år sedan) inte läses längre i ett naturligt sammanhang. Denna dominans till det kronologiska har alltså stört mig rätt länge. I vissa fall är det naturligt eftersom det ofta är dagsaktuella frågor som diskuteras och man anser att debatt etc är över. Men det man missar är samlandet av kunskap kring det som man - eventuellt - kom fram till.

Det verkar även finnas andra som haft liknande tankar kring begränsningarna, men kanske av andra skäl, vilket inte är så konstigt. Nu har man hunnit experimenterat med mediet, funnit det som passar ens egna syften och identifierat det som är mindre intressant. Det verkar gälla såväl traditionell (text)bloggning, podcasting som videobloggning. Detta är tiden att fundera över mediers inneboende begränsningar.

Stefan Geens undrar lite Bloggforum 3 - what I saw vad Bloggforum 4bör innehålla. Det rykte som Jon skriver om i sin kommentar är något som bl.a. jag själv underblåst (eller vad det nu är man gör med rykten), eftersom jag inte tror att det finns behov för ett Blogg-forum om ett halvår, och diskuterade detta lite med både Erik Stattin och Stefan Geens i helgen.

Däremot ser jag mycket fram emot ett X-forum (alternativt X-logg-forum) där man visar hur det-vi-nu-nu-kallar-blogg ("the thing formerly known as blog") har utvecklats och förändrats, och hur det eventuellt påverkat t.ex. socialt eller tekniskt. Självklart kommer det fortfarande att finnas bloggar med eller utan t.ex. wiki-liknande utökningar, men jag tror och hoppas att vi kommer att se en större variantion i såväl form som innehåll.

Troligen har det om ett halvår även hänt saker inom lagstiftning, politik, media samt i det sociala landskapet (t.ex. olika typer av forskning kring bloggning) som är väl värt att föreläsa om eller ha sessioner kring.

Som Ben Hammersley beskriver i sin "Åtta idéer som verkligen kommer att revolutionera 2000-talet (och varför blogging inte är en av dem)" är bloggen i sig inte inte en någon revolutionerande idé, men inkorporerar många av de idéer som har eller kommer att revolutionerna informationsamhället eller åtminstone påverka det.


Web 2.0 och agenter
Under flera tillfällen diskuterades det Web 2.0, t.ex. med Simon Winter, Henrik Torstensson och Jon Åslund. Jag har inte stenkoll på vad det är och tycker det liknar det som man sa kring 98/99 om webben eller t.ex. när WAP kom. Men nu har det faktiskt blivit möjligt för en företagsam person att göra dessa applikationer med öppna API och "öppen data".

En sak som jag har saknat i diskussionerna är intelligeta agenter som kommunicerade med varandra för att lösa all världen (informations)problem. Vad blev de egentligen av? Jag vill ha min shoppingagent!


Jyri Engström: Sociala object
Jyri Engströms föredrag var det föredrag som jag var mest intresserad av och var även det som jag uppskattade mest. Engström poängterade att det viktiga med sociala mjukvaroprogram (och man borde kunna se bloggen som ett sådant) är gemensamma sociala objekt, där objekt kan vara väl definierat men även uppstå spontant efter ett tag.

Som exempel på hur viktigt det är med gemensamt socialt objekt visades en av mina favoriter bland Monty Python-sketcherna: Fotbollsmatchen mellan grekiska och tyska filosofer. Detta fick mig att parafrasera Wittgensteins berömda setens från Filosofiska undersökningar: "a serious and good philosophical or social work could be written that would consist entirely of jokes from Monty Python".

Inledningsvis nämnde Engström några böcker som jag har faktiskt läst och skrivit lite om, se mer Social Network Analysis och Complex Networks - En liten introduktion. Se även tidigare bloggningar: Social Network Analysis/Complex networks.

Engström rekommenderade även en nyutkommen bok (den där med bilderna på det italienska mötet respektive potatisodlingen) och som verkar intressant: John Thackara In The Bubble - Designing in a Complex World.

Det antyds att Lotta at Work kommer att publicera ljud/video från Engströms föredrag.


Ben Hammersleys vision
Ben Hammersley hade en något provocerande rubrik på sitt föredrag "Åtta idéer som verkligen kommer att revolutionera 2000-talet (och varför blogging inte är en av dem)" som fick sin förklaring, och gav faktiskt en koppling till bloggandet genom att bloggande (och bloggare) "inkorporerar" alla(?) dessa punkter.

Föredraget var intressant även om jag inte riktigt håller med honom i hans undergångsbeskrivning. Hans tes att detta är en unik tid som vi aldrig tidigare skådat känns också som en något omotiverad kontemporär-centrism, dvs att vår tid är viktigare eller mer märkvärdigt än tidigare tider. Vad är det för märkvärdigt med vår tid? Å andra sidan är uppgång och nedgång av civilisationer inte heller någon naturlag.


En kommentar kring en detalj som verkar vara viktigt för resonemanget. Hammersley menar att den tekniska utvecklingen numera bara fortsätter att öka genom att den tekniska utvecklingen förstärker sig själv, t.ex. genom att snabbare datorer gör det möjligt att skapa ännu snabbare datorer som i sin tur möjliggör skapande av snabbare datorer etc. Han stödde denna tes med en bild föreställande en exponentiell kurva som påstods visa att datorerna blir allt snabbare/billigare/kraftfullare datorerna utan någon gräns eller avtagande. Troligen kan man även tolka kurvan som en logistisk kurva, eftersom den i början ser den ut som en exponentiell kurva men planar sedan ut till en "mättnadsnivå". En alternativt tolkning att det var i stort sett samma kurva ("sinuskurva") som Hammersley tidigare visat att symboliserade tidigare civilisationer hade följt: först uppgång, sedan nedgång ("crawling in the mud"?) och sedan uppgång igen och sedan nedgång. Således är det inte nödvändigt att det är en exponentiell tillväxt.

Han varnade i och för sig för att beskrivningen skulle störa personer med vissa kunsaper inom historia och teknik (samt eventuellt matematik).

Hur som helst var det ett mycket energirikt och inspirerande föredrag. Det finns en ljudupptagning via Lotta at Work.


Mozz Hussain: MSN Spaces i praktiken
Mozz Hussain "Busting blogging myths - the present and future of blogging" handlade om erfarenheterna kring MSN Spaces. Det var i och för sig intressant och gav inblickar i den sociala strukturen kring bloggar, men detaljerna fastnade inte så mycket. Kanske beror detta på att MSN Spaces inte representerar så mycket den typ av bloggning som jag själv tycker är mest intressant att följa, det som bl.a. Jonas Söderström kallar för kunskapsbloggar.


Copyfight
Detta hade jag sett framemot, bl.a. eftersom Simon Winter var med i panelen. Simon är en av mina absoluta favoriter bland de svenska bloggarna och som jag haft förmånen att träffa flera gånger tidigare. Simon summerar några av sina tankar kring debatten i Vad är viktigt med upphovsrätt?.

Med en något elak förenkling kan man säga att man kom fram till att man egentligen inte vet vad som gäller. Det var dock intressant att följa debatten, speciellt de konkreta exemplen som framfördes såväl från panelen som publiken.

Debatten blir inte lättare med att begreppen "kopiering", "fildelning", "piratkopiering" nu är så inflammerade att det verkar som en vettig diskussion av det är omöjlig, och det känns som om antipiratbyrå-sidan för tillfället äger dessa begrepp. Ett förslag är att försöka hitta en mer neutral begreppsapparat som gör det möjligt att föra rationella diskussioner. Under kvällen föreslogs det att begreppet "kopiera filer" skulle bytas ut mot det neutrala "kgegg" (så tror jag att det stavas), ett ord som länge sökt sin användning.


Gamla vänner, nya vänner samt att bli överraskad
Waldemar på Teche skriver följande i Det bloggforum jag inte var på:

Jag är lite förvånad över bloggosfären fortfarande håller i sig som en enad miljö. Trots allt är det ju rätt skilda ämnen och åsikter som avhandlas numer, men att man ännu delar en gemensam plattform... det tyder på att det kanske kommer att hålla i sig.

Ett skäl till kan exemplifieras med just Bloggforum är just att där finns så många olika intressen men alla har en gemensam referensram: bloggar. De allra flesta är också sådana som brinner för något och sådana personer är nästan alltid intressant att träffa eller få kontakt med (undantag finns naturligtvis). Det är flera kluster som - speciellt i Bloggforum - blandas i det gemensamt intresse av att uttrycka sig . I pausar, lunchen eller på "cocktail-partyt" kan man mingla med personer som man normalt inte träffar. Precis som i riktiga vänskapslivet kan man bli "hit it off" med en väns vän eller dennes vän

Den sociala poängen med dessa tillställningar är flerfaldig: att träffa sina gamla vänner, att prata med dem man har läst men inte träffats tidigare, samt helt enkelt bli överraskad av ett möte med någon man inte ens kände till. Detta sistnämnda ska inte underskattas.

På ungefär samma sätt vill man att sociala nätverkssystem ska fungera. Nyhetsbevakningsystem och rekommendationssystem har liknande syften:
- man vill bli uppdaterad inom de områden man känner väl till
- man vill lära sig mer inom ett ämne
- man vill bli överraskad av nya kunskaper eller ämnen.


En social nätverksanalys-kommentar: I många Bloggforum 3.0-redogörelser länkas det till personerna som träffats. Det skulle vara intressant att jämföra dessa med t.ex. bloggrullen eller de man länkat till föregående samt eventuellt efterföljande. Avspeglar kontakterna på Bloggforum det normala sociala mönstret inom bloggosfären? Min egen intuition kring detta är att cocktail-parties har en annan social dynamik än de dagliga bloggkontakterna.


Några längre-än-kortare kontakter
Här är den nästan-obligatoriska lista över personer som träffades och som pratades med mer än några sekunder. De med (*) anger nya IRL-bekantskaper. Det skulle ta alldeles för lång tid att skriva ner vad vi pratade om så det blir i stort sett endast en uppräkning av namn. Tack till er för trevliga pratstunder.

- Mats Andersson, resekamrat, hotellrumssdelare, gåtlösare samt galapetter
- Steffanie Müller
- Simon Winter
- Stefan Geens
- Andreas Haugstrup (*)
- Henrik Torstensson
- Någonting Söderström(?), Henrik Torstenssons ej bloggande kompis (*).
- Eric Wahlforss (*)
- Erik Stattin
- Jenny Isaksson (*)
- Niki Bergman (*)
- Rebecca Crusoe
- Daniel Lundh (*)
- Håkan Hakke Karlsson, varvid våra respektive skulder tillvarandra nu är reglerade.
- Rosemari Södergren (*)
- Erik Starck
- Jimmy Wilhelmsson
- Johnny Söderberg, mitt mål att prata med honom mer än några sekunder blev uppfyllt.
- David Hall
- Lisa Förare Winbladh
- Isobel Hadley-Kamptz (*), naturen av vår kontakt beskrivs nedan under "Isobels och Lisas pizzeriabordsproblem".
- Jonas Söderström
- Jon Åslund (*)
- Coola morsan, men vi hade lämnat vår musikideologiska skiljelinjer bakom oss.
- Oscar Swartz (*)
- Karolina Lassbo (*).
- Per Gudmundsson


Två personer som jag inte träffade men hade tänkt prata med:
- Patrik Wallström (som jag skulle hälsa från en gemensam vän tillika listsvågrar)
- Christian Ubbesson (listsvåger och arbetar med saker, text mining, som jag är intresserad av)


Geekighet
Jag var med i flera diskussioner om geeekighet, vilket nog faller sig naturligt på en så här rätt geekig tillställning. Många av de personer som jag pratade med eller åhörde kan nog anses vara geekar, i alla fall i en något vidare mening (se nedan).

* en mer allmän diskussion med Steffanie Müller som började med att hon ansåg mig vara en större geek än hon själv (som om man kan jämföra geekigheter på detta sätt), varpå vi diskuterade naturen av detta begrepp.

* Jimmy Wilhelmsson berättade om dokusåpan FCZ som består av ett gäng geekar som spelar fotboll (och som jag inte sett men ändå stött på indirekt i ett rätt geekigt sammanhang) där geeken nu får ett ansikte och personlighet.

* både direkt och indirekt med Jon Åslund - som jag uppfattar som en übergeek, och det är en komplimang, Jon - i alla fall de facetter jag såg, vilket möjligen avspeglar mina egna intressen och värderingar. Lite roligt här är att jag förra söndagen stötte på Jons namn i ett helt annat sammanhang; nästan helt annat, eftersom det var i samband med att Hakke lämnade in sina svar på Bloggforum-pyssel i lite för poetiska formuleringar, nämligen att Jon är skapare av det underbara programspråket The Shakespeare Programming Language som jag känt till tidigare.

Det finns ett test The Nerd? Geek? or Dork? Test där jag själv fick följande resultat:


Pure Nerd
82 % Nerd, 47% Geek, 43% Dork
For The Record:

Man definierar de olika begreppen på ett sätt som jag inte nödvändigtvis håller med om.


A Nerd is someone who is passionate about learning/being smart/academia.
A Geek is someone who is passionate about some particular area or subject, often an obscure or difficult one.
A Dork is someone who has difficulty with common social expectations/interactions.

You scored better than half in Nerd, earning you the title of: Pure Nerd.

The times, they are a-changing. It used to be that being exceptionally smart led to bei
ng unpopular, which would ultimately lead to picking up all of the traits and tendences
associated with the "dork." No-longer. Being smart isn't as socially crippling as it o
nce was, and even more so as you get older: eventually being a Pure Nerd will likely be
replaced with the following label: Purely Successful.

Isobels och Lisas pizzeriabordsproblem
Under lunchen satt vi (Lisa, Rosmarie, Johnny, Hakke, hakank samt Daniel) på en pizzeria. Efter en stund ropar Lisa: "Isobel!" varpå denna kom fram till vårt bord. Efter lite inledandes flamsande ville naturligtvis Isobel och Lisa uttrycka sin ömsesidiga vänskap genom en kram eller liknande, varvid man insåg snabbt att ett logistiskt problem hade uppstått genom att bordplaceringen var sålunda:

Förkortningar:
1: Lisa (som alltså är den som känner Isobel)
2: Rosmarie
3: Johnny
4: Hakke
5: hakank
6: Daniel

Bordplaceringen:
_ V Ä G G
V 2 4 6
Ä _ _ _ Isobel (stående och rörlig)
G 1 3 5
G
_ V Ä G G

Där "V Ä G G" - på härsan och tvärsan - betyder omgärdande av en vägg eller väggliknande hinder. Bordet motsvaras av "_ _ _".


Problem: Hur optimerar man en hälsningsceremoni mellan Lisa och Isobel?
Eftersom sällskapet omslutes av tre väggar (eller väggliknande hinder) finns det inget sätt sätt för Isobel och 1 att enkelt uttrycka en fysisk hälsningsceremoni utan att 3 och 5 förflyttar sig från soffan. Det fanns ingen plats under bordet för Isobel att krypa in under, och det var såväl fysiskt, ekonomiskt som socialt omöjligt att använda bordet som transportsträcka. (Alternativa lösningar som att använda en wire för att utnyttja det lediga luftrummet ansågs inte realistiskt eftersom vi skulle alla vara tillbaka inom rätt kort tid och kranarbetarna var troligen på lunch under denna tid. Att använda elektronisk utrustning för att t.ex. skicka hälsningsemail, hälsnings-SMS eller bloggogram tänkte man troligen inte på i den då innevarande stunden.)


Lösningsalternativ A
Följande lösning är troligen det normala förfarandet i liknande uppkomna situationer. Inom parentes anges kostnaden för förflyttningen (se även kommentaren nedan), där vi här antar att förflyttning av en plats kostar 1 (dvs en enhet något).

a) Isobel flyttar sig en liten bit ut från bordet för att ge plats åt 5 (1)
b) 5 makar sig ut från bordet (1)
c) 3 makar sig ut från bordet (2)
d) 1 makar sig ut från bordet (3)
e) 1 uttrycker sin vänskap med Isobel (0)
f) 1 makar sig tillbaka till sin plats (3)
g) 3 makar sig tillbaka till sin plats (2)
h) 5 makar sig tillbaka till sin plats (1)
i) Isobel återställer sig på sin plats. (1)
Summa kostnad: 1 + 1 + 2 + 3 + 0 + 3 + 2 + 1 + 1 = 14

Lösningsalternativ B
Det finns en variant till A där Isobel i stället makar sig in i soffan enligt följande schema:

a) Isobel flyttar sig en liten bit ut från bordet (1)
b) 5 makar sig ut från bordet (1)
c) 3 makar sig ut från bordet (2)
d') Isobel makar sig in till plats 2 (2+1.5=3, se nedan)
e) 1 uttrycker sin vänskap med Isobel (0)
f') Isobel makar sig ut från bordet (2*1.5=3, se nedan)
g) 3 makar sig in till sin plats (2)
h) 5 makar sig in till sin plats (1)
i) Isobel återställer sig på sin plats. (1)
Summa kostnad: Summa kostnad: 1 + 1 + 2 + 3 + 0 + 3 + 2 + 1 + 1 = 14

Isobel behöver här endast förflytta sig två (2) platser vilket ger en kostnad på 2, men eftersom Isobel är fullt påklädd i vacker förvinterskrud medför förflyttning i soffa en något större kostnad per förflyttning, dvs 2 * 1.5 (kostnad 3).

Det är alltså samma kostnad för alternativ A och B (14).


Alternativ C: en mer kostnadseffektiv lösning
Efter snabbt övervägande föreslogs en "proxylösning":


Isobel kramar 5 (0.5)
5 kramar 3 (0.5)
3 kramar 1 (0.5)
1 kramar 3 (0.5)
3 kramar 5 (0.5)
5 kramar Isobel (0.5)
Totalkostnad: 6 * 0.5 = 3.

Eftersom kramar i en soffa förnärvarande har en kostnad på cirka 0.5 skulle detta ge en totalkostand på 6*0.5 = 3 var det naturligtvis bättre än de ovanstående föreslagna alternativa lösningarna.

Alternativ D: mer effektiv lösning och den implementerade
Den lösning som faktiskt implementerades var med (kind)pussar. Som tidigare anges kostnaden inom parentes.

a) 1 pussar 3 (0.1)
b) 3 pussar 5 (0.1)
c) 5 pussar Isobel (0.1)
d) Isobel pussar 5 (0.1)
e) 5 pussar 3 (0.1)
f) 3 pussar 1 (0.1)
Totalkostnad: 0.6

Detta verkar således vara det optimala tidsödande sättet om man använder hälsningsceremonierna kram eller kindpuss.

Kommentarer
I föreslagningsalternativen A och B antogs en kostnad 0 för kram mellan 1 och Isobel men i C antogs den vara 0.5. Hur går detta ihop? Jo, helt enkelt genom att här anta att vinsten för hälsningsceremonin också är 0.5. Detta kan med rätta kritiseras, och man kan här fundera på om det överhuvudtag går att jämföra kostnaden de två principiella olika hälsningsmodellerna:
* direkt hälsningsceremoni, dvs där Lisa och Isobel verkligen hälsar på varandra
* den indirekta ceremonin (proxyvarianten) där hälsningen skrev via andra på platsen närvarande personer.

Om vinsten i den direkta hälsningsmodellen är tillräckligt stor kan alternativ A eller B vara att föredra framför C och D. Vidare forskning - förhoppningsvis kompletterade med empiriska studier - inom området kan förhoppningsvis klargöra detta.

Vidare utökning av modellerna bör även studera de vinster som uppstår hos proxy-personerna. I ovanstående modell har vi helt ignorerat vinsterna för 3 och 5 som får förmånen att interagera med 1, med Isobel samt med varandra. Troligen är sådana vinster inte försummbara.


Två noter
a) Om Isobel eller för den delen 1, 2, 3, 4 respektive 6 skulle känna sig kränkta av ovanstående beskrivning bes det om ursäkt.
b) Det inses snabbt att ovanstående beskrivning - i sin nuvarande form - inte skulle bli publicerad i Hänt-i-Veckan eller liknande förmedlingsmedier, oavsett om det funnes kompletterande tillfällestagna bilder på de alternativa lösningarna. Möjligen skulle bilderna själva kunna publiceras med en något mer snärtig bildtext, t.ex. Algoritmchock kring logistiskt hälsningsceremoniproblem eller - mer troligen - Pusschock med Isobel!.

Posted by hakank at 09:59 EM Posted to Blogging | Matematik | Pyssel | Comments (9)

november 04, 2005

Sesemans matematiska klosterproblem samt lite Constraint Logic Programming

Bengt O. Karlsson ställde igår en matematisk gåta: Ett aritmetiskt problem av Hans Jacob Seseman. Se även den omslutande anteckningen Sesemania (som avslutas med en personlig anmaning). [Uppdatering: Titeln på den nyss angivna anteckningen är felaktig och ska vara Sesemana, men felskrivningen upplevdes av Bengt som en nära-Freud-upplevelse. Och hur kan man underlåta att ge Bengt en sådan njutning? Därför står felstavningen kvar i sin ursprungliga - men alltså felaktiga - prakt. Se något mer i kommentarerna till Bengts Sesemana -artikel. I sanningens namn korrigerades först felet, men sedan korrigerades rättet och denna uppdatering skrev som ett förtydligande.]

Det var ett kul litet problem, och inte speciellt svårt att lösa. En av utmaningarna var att korrekt tolka gammelsvenskan för att förstå vad problemet egentligen bestod av. Försök gärna lösa problemet själv innan ni läser vidare eller läser kommentarerna till problemet.

Uppdatering 2
På begäran har programmet Seseman's Convent Problem (se nedan) nu även möjlighet att visa unika lösningar, eller - mer korrekt - samla lösningar som är lika vad gäller rotation, spegling etc. Denna unicifiering har gjorts i CGI-programmet, ursprungligen som ett analysstöd för att eventuellt senare göra sådant i CLP-programmet.


Problemet
Problemet består av 4 liknande delproblem där det gäller att givet ett visst antal personer i ett kloster (nunnor samt eventuellt "tillkomne Karlar") ska man placera ut dessa personer i rum så att vissa villkor uppfylls.

A, B, C, D, E, F, G, H betecknar klostrets olika rum. Rummet "_" används inte, forutom att presentera en fin kvadrat.

A B C
D _ E
F G H

Ett krav är att vissa rader/kolumner ska ha summan 9:

A + B + C = 9
A + D + F = 9
C + E + H = 9
F + G + H = 9

Ett annat krav är att totalantalet personer ska vara en av de fyra summorna (24, 28,20, 32), som man själv fick lista ut med lite enkelt aritmetik. Villkoret är alltså:


A + B+ C + D + E + F + G + H = Totalsumma

Notera att det inte står någonting om huruvida rum kan vara tomma eller ej (se nedan om detta).

I kommentarerna till problemet visades ett antal olika lösningar, och det visar sig att problemet inte är entydigt eftersom några delproblem har flera lösningar, varav några presenteras av Fredriik och Hakke (också en Håkan K) samt undertecknad (Håkan K).


Constraint Logic Programming
Men det finns fler lösningar än så.

Problemet löstes ursprungligen med penna och baksidan av ett papper, men efteråt skapades ett litet CLP-program (Constraint Logic Programming) för att generera de olika lösningarna, närmare bestämt i det Prolog-baserade programspråket ECLiPSe (Gratis att ladda ner, men man måste anhålla om en licens.)

ECLiPSe-programmet finns här. Den centrala funktionen i programmet innehåller i stort sett endast de matemaitksa uttrycken ovan.

seseman(Rowsum, Total, FirstNum, LD) :-
LD = [A,B,C,D,E,F,G,H], % deklarera variablerna

% FirstNum = 0: empty rooms allowed
% FirstNum = 1: empty rooms not allowed
LD :: [FirstNum..9],

% Radsumma/Kolumnsumma
A+B+C #= Rowsum,
A+D+F #= Rowsum,
C+E+H #= Rowsum,
F+G+H #= Rowsum,

% summan av alla tal = Total
A+B+C+D+E+F+G+H #= Total,

labeling(LD).

Den magiska genereringen av giltiga lösningar enligt restriktionerna (constraints) hanteras av labeling.


För att köra programmet från kommandoraden anger man följande:

eclipse -b seseman.ecl 9 24 1 -e 'go.'

där 9 är radsumman, 24 totalsumman. Talet 1 är ett hack för att ange att inget rum får vara tomt (0 om rum får vara tomma). -e 'go' är anropet till funktionen go och -b anger filnamnet.


Lösningar och ett webb-program
Det skrevs även ett webb-program som kommunicerar med ECLiPSe-programmet: Seseman's Convent Problem (monastary är munkkloster, convent är nunnekloster). Detta program gör det också möjligt att ändra på parametrarna skulle man så önska leka lite.

T.ex. finns det 7 lösningar för totalsumma 20 om man inte tillåter tomma rum och hela 73 lösningar om tomma rum tillåts.

Notera att programmet inte tar hänsyn att två lösningar kan vara samma fast de är roterade, spegelvända etc. Uppdatering Jodå, det gör det nu.

För de fyra olika totalsummorna som angav i problemet förevisas här antalet lösningar och om rum får vara tomma eller ej:
24 personer, tomma rum tillåts ej: 85 lösningar
24 personer, tomma rum tillåts: 231 lösningar

Som problemet är formulerat finns det dock bara en korrekt lösning för första delproblemet (24 nunnor): samtliga rum innehåller vardera 3 nunnor.

28 personer, tomma rum tillåts ej: 35 lösningar
28 personer, tomma rum tillåts: 165 lösningar
20 personer, tomma rum tillåts ej: 7 lösningar
20 personer, tomma rum tillåts: 73 lösningar
32 personer, tomma rum tillåts ej: 1 lösning
32 personer, tomma rum tillåts: 35 lösningar


Programmet har dock kvar begränsningen att maximalt antal personer som får finnas i ett rum är 9. Vi kan väl säga att det beror på att jag vill vara snäll mot webbservern. Om man vill leka med större värden kan man ändra 9 till något annat (t.ex. Total) på denna rad:

LD :: [FirstNum..9],


Kommentarer
Jag har inte hittat någon ren matematisk lösning på problemet, men en sådan kanske kommer (av någon). Ovanstående program gör det i alla fall möjligt att empiriskt studera problemet. Uppdatering: Det finns en bok Sesemans problem som kanske innehålla slika lösningar.


Man kan möjligen misstänka att Fredrik nu kommer att skriva ett mycket elegantare Python-program för detta problem.


För den som vill läsa mer om Constraint Logic Programming kan rekommenderas Programming with Constraints av Kim Marriott och Peter Stuckey. Boken innehåller många exempel som finns att ladda ner.

Posted by hakank at 11:48 EM Posted to Constraint Programming | Matematik | Program | Comments (12)

oktober 28, 2005

Lagoma tal och dess släktingar

I en maildiskussion skrev Mats Andersson följande (något redigerat) apropå ett hotells (*) belägenhet:

sqrt(2) är nog det lagomaste talet som finns. Näst efter Pi. Och E. Och Phi.

Detta gjorde mig nyfiken på definitionen av lagoma tal. google är som vanligt inte till någon hjälp i de allra viktigaste frågorna. Därför är egendefinitioner den enda lösningen. Ett förslag till definiton är alltså följande.


Lagoma tal
Ett lagom tal (ett lagomt tal) är ett tal som är tillräckligt litet för att kunna representera en kort gångsträcka om den representerar kilometer. Exempel på lagoma tal: 1, sqrt(2), E, Phi.

Avståndet får dock inte vara för litet eftersom då får man ingen motion. Se vidare Motionella tal. Kan t.ex. användas för att representera avstånd mellan ett hotell och Slottet (i Stockholm eller annorstädes).

Det finns ännu ingen bevisat både objektiv och effektiv metod att säkerställa ett tals lagomhet. Existensen av de hitills funna lagoma talen har bevisats genom experimentella metoder.


Not: även väldigt små tal kan vara lagoma tal, men då får de inte representera en engångssträcka utan måste vara periodiskt utsträckt över både tid och rum. T.ex. sin(x) kan motsvara ett sådant tal, men man bör dock vara försiktig att använda denna funktion i blåsigt väder utan mössa eller mössliknande öronbeskydd.


Motionella tal
Tal som räknat i kilometer rask gångtakt ger bra motion. Se även Lagoma tal som är något mindre. Se även Nationella tal.


Nationella tal
Tal som endera är ett Lagoma tal eller Motionella tal (vilka se) och avser avstånd inom det egna landet.

Tal som avser avstånd i annat land - eller annorstädes där risken att gå vilse anses vara större - kallas för Irr-nationella tal.


Simmetriska tal
Yngre kusin till Lagoma tal. Tal som avser avstånd i badhus och liknande vattenomslutande inrättningar.


(*) Liten tävling: Den förste som kan korrekt gissa vilket hotell det var som inspirerade till ovanstående bjuds på en öl eller motsvarande vid bästa tillfälle. Varken Mats Andersson eller jag är i stånd att gissa (eftersom vi faktisk vet svaret) och får därför inte vara med i tävlingen.

Posted by hakank at 07:24 EM Posted to Humor | Matematik | Comments (21)

september 04, 2005

Svaren på Augusti-pyssel

Här kommer så de eftersökta (?) svaren på 2005 års Augusti-pyssel. Pysslen är samtliga saker som jag själv leker med från tid till annan.


Fråga 1) Vad står här egentligen och varför (dvs enligt vilken metod): 1045668080


Svar: Det står "hakank" i bas 36. Detta kan lämpligast kontrolleras via programmet base_conv, se vad som står för bas 36. Programmet beskrevs mer i base_conv: Konvertering av ord till tal till ord just som en ledtråd till denna gåta.


Fråga 2) Vad står här egentligen och varför: 15604225

Svar: Det står "messages". Enligt följande mekanism

1. En faktorisering av talet ger följande primtal: 5, 7,13, dvs 15604225 = 5^2 * 7 * 13 * 19^3.

2. Om man tar positionerna i alfabetet "a".."z" och låter "a" har position 1, "b" position 2 etc, för dessa faktorer får man bokstäverna: "e", "g", "m", "s". Faktorn 5^2 motsvarar två stycken "e", 7^1 motsvarar ett "g" etc. Hela denna konvertering skapar bokstäverna: "e","e","g","m","s","s","s" enligt följande:

alpha = "abcdefghijklmnopqrstuvxyz"
alfa[5] = e # 5^2 : 2 stycken e
alfa[7] = g # 7^1: 1 styck "g"
alfa[13] = m # 13^1: 1 styck "m"
alfa[19] = s # 19^3: 3 styck "s"

Eftersom talet 1 (som motsvarar "a") alltid är en giltig faktor så kan denna bokstav också ingå. Den slutliga bokstavsmassan blir alltså

0 eller flera "a" (här behövs exakt ett "a")
e
e
g
m
s
s
s

dvs e e g m s s s samt eventuellt ett gäng a.


Efter lite anagrammerande kryper det korrekta svaret "messages" fram..

OK, a-konstruktionen gjorde det kanske onödigt svårt, och var det som antyddes i den uppdaterade kommentaren på Augusti-pyssel-sidan. Sorry 'bout that.

Fråga 3) Vad ska stå i stället för "?" i nedanstående?

Så kommer vi till sekvenserna där bara ett tal var givet. I kommentarerna gavs sedan en ledtråd med det omedelbart föreliggande talet.

a) ...., 1596, ?

Svar: 2583. Detta är summan av de 15 första Fibonacci-talen och svaret är det 16:e talet i denna serie, dvs 2583.


# Fibonacci talen
> fibonacci(i)$i=1..15;
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610


# summan av de 14 första
> sum(fibonacci(i),i=1..14);
986

# 15 första
> sum(fibonacci(i),i=1..15);
1596

# och så de 16 första
> sum(fibonacci(i),i=1..16);
2583

# hela serien
> seq(sum(fibonacci(i),i=1..a), a=1..16);
1, 2, 4, 7, 12, 20, 33, 54, 88, 143, 232, 376, 609, 986, 1596, 2583

Sekvensen som fås av summan av de första a Fibonacci-talen är för övrigt 1 snäpp ifrån Fibonacciserien:

> seq(sum(fibonacci(i),i=1..a)+1, a=1..16);
2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584

Eller snarare: Det är en Fibonacci-liknande rekursiv serie där men i stället för att utgå från (1,1) som generatorer utgår man från (1,2).


b) ...., 78, ?

Svar: 91. Serien är addition av de a (12) första naturliga talen och nästa tal är det 13 talet i denna serie.


> 1+2+3+4+5+6+7+8+9+10+11;
66

> 1+2+3+4+5+6+7+8+9+10+11+12;
78

> 1+2+3+4+5+6+7+8+9+10+11+12+13;
91

# hela serien
> seq(sum(i,i=1..a),a=1..13);
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91


c) ...., 129, ?

Svar: 160. Detta är summering av de första primtalen och svaret är det 11 talet i denna serie: 160 som fås när man adderar 31 till 129 = 160.


> ithprime(i)$i=1..10;
2, 3, 5, 7, 11, 13, 17, 19, 23, 29


> 2+3+5+7+11+13+17+19+23;
100

> 2+3+5+7+11+13+17+19+23+29;
129

> 2+3+5+7+11+13+17+19+23+29+31;
160

# hela serien
> seq(sum(ithprime(i),i=1..a),a=1..11);
2, 5, 10, 17, 28, 41, 58, 77, 100, 129, 160


Fråga 4) Vad är det gemensamma för nedanstående ord?
* besökes
* eksem
* gömmes
* webb


Svar: Samtliga dessa ord innehåller endast bokstäver med primtalspositioner (cf diskussionen kring fråga 2). Primtalsbokstäverna är alltså där positionen står först. (Not: positionen 1 för "a" har jag redan bett om ursäkt för.)

1:a
2:b
3:c
5:e
7:g
11:k
13:m
17:q
19:s
23: w
29:ö

Orden med respektive faktorer:
* besökes: 5757950 = 2 * 5^2 * 11 * 19^2 * 29
* eksem: 67925 = 5^2 * 11 * 13 * 19
* gömmes: 3259165 = 5 * 7 * 13^2 * 19 * 29
* webb: 460 = 2 * 5 * 7^2

Notera att orden inte innehåller samma antal faktorer (antal bokstäver) som det givna talet, utan är ord som endast innehåller dessa bokstäver oavsett hur många förekomster av bokstaven som ingår. Denna fråga var mestadels med som en ledtråd till fråga 2.

Posted by hakank at 12:24 EM Posted to Matematik | Comments (0)

augusti 29, 2005

Kortsamlarproblemet (coupon collector problem) i mindre och isolerade nätverk med fullständigt utbyte av kort

Introduktion

När jag var liten samlade jag en hel del på samlarkort, t.ex. flaggor, ishockey-/fotbollsspelare etc. Det var alltså sådana kort där man köpte osett, ett eller flera kort i en påse (med eventuellt medföljande tuggummi eller annat godis) och sedan antingen köpte man nya eller bytte man till sig de kort man inte hade. Den stora poängen var naturligtvis att få hela serien komplett. (Det fanns säkert en fin social poäng i att träffas och byta sådana kort, men sådana finesser uppfattade man nog inte i denna ålder, typ kring 10+ år.)

Speciellt för flaggorna kommer jag ihåg att det fanns vissa kort som var väldigt svåra att få tag på (var det Mexiko med nummer 104, eller kanske var det Kenya?). Om jag nu kommer ihåg detta korrekt var det några få lyckostar som fått detta kort och vi andra dräglade djupt över dessa rara kort.


Kortsamlarproblemet (coupon collector problem)
Det finns ett klassiskt problem inom statistiken/sannolikhetsläran som handlar om detta: kortsamlarproblemet (coupon collector problem, dvs kupongsamlarproblemet) där man studerar hur många kort man behöver köpa i genomsnitt (eller för en viss säkerhetsgrad) på att få samtliga kort i en sådan samlarserie. Det visar sig att det är ointuitivt många: För att få tag i samtliga kort i en serie av 100 kort behöver man i medeltal köpa 519 kort. (Enkel formel för detta : 100*sum(1/(1:100)) ~ 519, där 100 i formeln är just antal unika kort i samlarserien.)

Men detta antal fluktuerar naturligtvis: för att vara säker till 95% att få tag i samtliga kort krävs 791 inköpta kort. Se även min Simuleringssida för lite mer om detta; sök på "samlarkortproblemet ".

Man kan notera att ovanstående beräkningar endast gäller för en person som ensam inhandlar kort. Om man tillåter byte av kort är det en annan sak, och det är precis det som det följande kommer att handla om.


Samlarkortproblemet i ett isolerat nätverk med fullständigt utbyte
För ett tag sedan hade jag en diskussion med en kompis om detta. Denne - som vi kan kalla för E - hävdade att företagen troligen inte tillverkar lika många av varje kort, just för att få oss att köpa fler kort för att få tag i samtliga.

Denna konspirationsteori är möjligen korrekt, men jag började undra om denna effekt kunde uppstå även om företaget tillverkade lika många exemplar av alla kort, och att det vi råkat ut för var en "klustereffekt", dvs att de kort som vi i vårt lilla nätverk var en slumpmässigt urval med de traditionella egenskaperna hos sådana urval.

E antog att företagen som skapar korten alltså tillverkar vissa kort i färre upplagor, säg att de färsta (sic!) är en tiondel av de som tillverkas mest. Min utgångspunkt var att denna effekt skulle kunna vara subjektiv enligt "regeln" att om man slumpmässigt drar ett antal olikfärgade kulor från en påse med lika fördelning så är det mycket stor sannolikhet att något antal är färre än de övriga och att det finns en färg som dras fler gånger.

Detta är något man kan testa med en simulering. Vilket har gjorts.


Sammanfattning
Som vi kommer att se uppstår faktiskt denna typ av effekt (E-effekt) om det totalt köps in ett mindre antal samlarkort. För 700 inköpta kort blir förhållandet mellan minst antal kort och flest antal kort rätt exakt 1/10.

Här nedan kommer även andra saker att visas, t.ex. denna effekt hos Lotto-dragna nummer, där samma förhållande är 1/2, vilket även uppstår i en simulering. Kanske inte så remarkabelt men intressant.


Lokalt nätverk med fullständigt utbyte av samlarkort
Först en sak om nätverket. Den modell som vi här arbetar med innebär att det finns en mindre grupp, säg ett 10-tal personer, som har fritt utbyte av samlarkort inom gruppen men inte har något som helst kort-utbyte med några externa personer eller andra nätverk. Denna fullständiga isolering av inköpen gör modellen enkel att simulera.

(Man skulle även kunna studera komplexa nätverks-effekter kring detta, dvs att någon i Husieskolans krets känner någon i Stockholm och byter till sig de i Husie-kretsens ovanliga kort. Ju fler sådana svaga länkar mellan olika (inte helt isolerade) nätverk det finns, desto större blir naturligtvis den totala kretsen vilket leder till att denna lokala nätverkseffekt vi talar om här blir mindre.)


Modell och simulering
Tänk nu följande som översättning av samlarkortproblemet i ett lokalt nätverk till slumpmässig dragning av heltal i ett intervall.

En grundläggande förutsättning är att det faktiskt skapas exakt lika många kort, och att man globalt har lika stor chans att köpa alla kort, men vi studerar endast en mindre krets (nätverk) av personer som får tillgång till ett urval av dessa, t.ex. där tobakaffärens och den där kioskens urval.

Låt oss för enkelhetens skull anta att samlarkortserien har 100 olika kort. Dessa 100 olika korten motsvaras i simuleringen då av de första 100 positiva heltalen (1..100 alltså). Ett inköp av ett kort motsvarar att man slumpmässigt drar ett tal inom detta intervall, där alla tal har lika stor chans att dras. Detta görs s.a.s. med återläggning, så att ett tal har möjlighet att dragas igen.

Man drar slumpmässigt n stycken sådana tal, vilket alltså motsvarar inköp av n stycken samlarkort.

Efter det beslutade antalet "kort" (tal) är dragna, kontrolleras fördelningen bland dessa kort. Här jämför man antalet kort som kommit upp med minst antal och de som kommit med flest antal. Om ss är listan över de dragna talens fördelning är det sökta värdet alltså: min(ss)/max(ss), det som nedan kallas för min/max-förhållandet.

Vi behöver inte förutsätta något om hur stor gruppen är eller hur många kort en specifik deltagare införskaffar. Vi kommer senare se hur många fullständiga serier ett visst antal inköpta kort tenderar att generera, och man kan alltså anpassa antalet kort som (i medeltal) behöver köpas in för att få fullständiga serier.


Frågeställningen och hypotesen
Låt oss alltså se hur fördelningen mellan minimi-antalet kort och maximi-antalet kort utvecklas med det totala antal kort som inköpes.

Frågeställningen: Vad är förhållandet mellan min/max om det totalt köps in num.bought stycken kort av num.cards möjliga?

Hypotes: Om man slumpmässigt kommer fram till sådana min/max-förhållande på säg 1/10 eller något liknande har vi inget statistiskt stöd för E:s konspirationsteori.

Här följer R-koden som använts för simuleringen, som helt enkelt drar num.bought stycken tal ur intervallet 1..num.cards och returnerar fördelningen av de dragna talen (dvs hur många 1:or som dragits, hur många 2:or etc). Man kan här också notera hur enkelt denna simulering är. Det beror på att vi gjort det enkelt för oss och förutsatt att det fullständigt och fritt utbyte i detta isolerade nätverk.


collector.group.sim <- function(num.cards=100, num.bought=10000) {
ss <- rep(0,num.cards);
for (i in 1:num.bought) {
s <- sample(1:num.cards,1);
ss[s] <- ss[s] + 1;
}
ss
}


Exempel:
Om vi nu antar att det är 100 olika kort och 10 personer som samlar, samt att dessa vardera köper respektive 200 kort, inalles 10*200 = 2000 kort. En sådan simulering ser ut så här (sorterad lista eftersom vi inte behöver bry oss om de specifika talen/korten som dragits):


> ss<-collector.group.sim(100, 10*200);sort(ss);min(ss);max(ss);min(ss)/max(ss)
[1] 10 11 12 12 12 13 14 14 14 15 15 15 16 16 16 16 16 16 17 17 17 17 17 17 17
[26] 17 18 18 18 18 18 18 18 18 19 19 19 19 19 19 19 19 19 19 19 19 20 20 20 20
[51] 20 20 20 20 20 20 20 20 20 20 20 20 21 21 21 21 21 21 21 21 21 22 22 22 22
[76] 22 22 23 23 23 23 24 24 25 25 25 25 25 25 26 26 26 27 27 27 27 28 28 33 33
[1] 10
[1] 33
[1] 0.3030303
> 10*200
[1] 2000

Här kan vi alltså se att det minsta antalet dragna tal/kort är 10, dvs min(ss), och max är 33. Förhållandet mellan dessa min(ss)/max(ss) är 10/33 ~ 0.3. Redan enna enkla simulering (detta nätverk) ger en känsla av att vissa kort är ovanligare än varandra, och förhållandet mellan de ovanligaste och de vanligaste är 10 på 33.

Personligen tycker jag detta är emot intuitionen: efter en slumpmässig dragning har vi ett min/max-förhållande på så stort som 0.3.


Om vi istället säger att man tillsammans endast köper 519 kort (dvs så många som det i genomsnitt krävs för att en person ska få en komplett serie) får vi några intressanta resultat. Notera att även här är det endast en enda körning, för att få en känsla för datan.


> ss<-collector.group.sim(100, 519);sort(ss);min(ss);max(ss);min(ss)/max(ss)
[1] 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4
[26] 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5
[51] 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6
[76] 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 9 9 10 10 11 12 13
[1] 1
[1] 13
[1] 0.07692308

Här kan till exempel följande noteras:

* min/max-förhållandet är värre än E:s föreslags 1/10, nämligen 1/13 (0.077)

* det minsta talet är 1 vilket innebär att det finns kort för en fullständig serie. (Fullständiga serier kommer att studeras mer här nedan.)


Vi gör nu en mer statistisk korrekt simulering med 100 sådana här simuleringar och tar medelvärdet för min/max-förhållandet:

> mean(replicate(1000,{ss<-collector.group.sim(100, 519);min(ss)/max(ss)}))
[1] 0.05141527

min/max-talet 0.05 (~ 1/20) stödjer ovanstående känsla att det är värre min/max-förhålllande än E:s 1/10.

Men det är kanske inte så realistiskt att en grupp tillsammans köper endast 519 kort? Låt oss nu titta på hur min/max-förhållandet påverkas av antalet inköpta kort.


Tabell över (medelvärde) av min/max-förhållandet för olika antal kortinköp
Om vi nu studerar medelvärdet av min/max för olika antal kortinköp får man följande tabell.

Från 100 inköp till 3000

> sapply(1:30, function(n) rbind(n*100, mean(replicate(100,{ss<-collector.group.sim(100, n*100);min(ss)/max(ss)})) ))
[,1] [,2] [,3] [,4] [,5] [,6] [,7]
[1,] 100 200 300 400.00000000 500.00000000 600.00000000 700.0000000
[2,] 0 0 0 0.01154701 0.04447036 0.07848971 0.1029102

[,8] [,9] [,10] [,11] [,12]
[1,] 800.0000000 900.0000000 1000.0000000 1100.0000000 1200.0000000
[2,] 0.1298539 0.1475774 0.1695608 0.1864951 0.1996583

[,13] [,14] [,15] [,16] [,17]
[1,] 1300.0000000 1400.0000000 1500.0000000 1600.0000000 1700.0000000
[2,] 0.2132364 0.2434604 0.2501553 0.2677531 0.2798811

[,18] [,19] [,20] [,21] [,22]
[1,] 1800.0000000 1900.0000000 2000.0000000 2100.0000000 2200.0000000
[2,] 0.2819174 0.2909844 0.3101849 0.3119899 0.3260513

[,23] [,24] [,25] [,26] [,27]
[1,] 2300.0000000 2400.0000000 2500.0000000 2600.0000000 2700.0000000
[2,] 0.3373065 0.3520848 0.3504074 0.3622678 0.3721507

[,28] [,29] [,30]
[1,] 2800.0000000 2900.0000000 3000.00000
[2,] 0.3841707 0.3844286 0.38901

Här kan man se att gränsen för 1/10 i förhållande mellan min och max är cirka 700 inköp. Detta motsvarar en liten grupp på 7 personer som köper vardera 100 kort, eller 4 personer som köper 175 kort osv. Jag tycker att det låter rätt lite, men å andra sidan var E:s 1/10 taget ur luften.

Om vi tar lite större steg: mellan 1000 till 30000 inköp:

> sapply(1:30, function(n) rbind(n*1000, mean(replicate(100,{ss<-collect