Dinesman's multiple-dwelling problem och Haskell

Det är enkelt att testa. Skriv ett program som testar alla olika möjliga permutationer av ordning på villkoren.

Försök att fundera ut innan hur lång tid det kommer ta att köra.

Vad innebär det att ta alla permutationer av något? Vilken körtidskomplexitet? Hur många varv kommer din loop köra som max?
Hur många operationer klarar din dator av att göra på en sekund?
Hur många operationer tar det att göra abc(x-y), x < y osv?

Även om du sorterar villkoren på ett optimalt sätt kommer du då kunna lösa ett större problem? Vad är ditt mål?

Att lösa problemet på 5 minuter är långsamt.

På en modern processor skulla jag gissa att man löser det där på ~1 sekund. Nu kör du iofs på en rpi4 men 5 minuter är fortfarande väldigt lång tid. Mängden arbete som krävs för att testa villkoren i varje loop är inte speciellt stort. Visst kan en optimal sortering av villkoren göra att du sparar några % körtid men i ditt fall ligger antagligen den stora kostnaden i ineffektiv generering av permutationer i haskell.

Gör en snabb överslagsräkning hur mycket jobb du faktiskt måste göra och hur snabb din hårdvara är. Även om man gissar 5-10x fel så märker man om koden verkar vara 100-1000x långsammare än den borde, vilket inte är helt ovanligt idag.

Algoritmen testar alla permutationer. Att testa alla permutationer har komplexitet O(n!). 12! är ~ 500_000_000 varv i loopen som mest. Min processor (11800H) har en klockfrekvens på ~4_000_000_000. Mängden arbete som utförs i loopen är inte speciellt stort, next_permutation snittar på 3 jämförelser/1.5 swap, varje villkor är bara ett par instruktioner, villkoren uppfylls 2/3 in i loop osv. ~1 sekund känns som en rimlig siffra.

Vet du vad du faktiskt jämför och varför det blir skillnad?

Körtiden beror på hur långt in i loopen som villkoren uppfylls. Även om du ger villkoren i samma ordning kommer det skilja mellan språken. next_permutation i C++ genererar permutationer i lexikografisk ordning, det gör inte permutations i haskell. Antalet varv i loopen kommer alltså skilja sig åt även om villkoren testas i samma ordning beroende på språk. Du jämför alltså helt olika program. Titta istället på sämsta möjliga körtid. Hur lång tid tar det om det är den sista permutationen som uppfyller villkoren (eller villkoren inte uppfylls alls men alla permutationer måste testas).

Här mäter du helt andra saker än själva algoritmen. Du har 5 värden. Det innebär att det bara är 120 olika permutationer. Att körtiden mellan 5 och 7 hyresgäster bara fördubblas är ytterligare än indikation på att du mäter något helt annat än vad du tror. Skillnaden i arbete som krävs är 42 ggr mer.
5 hyresgäster = !5 permutation.
7 hyresgäster = !7 permutationer = 7 × 6 × !5 = 42 × !5
Skillnaden mellan 11 och 12 hyresgäster kräver 12 ggr mer arbete. 10->12 = 132ggr mer.

Det handlar om 5-12 heltal. Det är mindre än antalet register som finns i processorn

Jag förstår fortfarande inte vad du försöker testa eller komma fram till?