Utforsking i python med itertools

Det digitale verktøy og programmering gjør veldig enkelt, er å prøve veldig mange muligheter. For å danne alle mulige permutasjoner eller kombinasjoner kan itertools-pakken i python være veldig effektiv. Generelt er det praktisk for elever i vgs å forholde seg til så få pakker som mulig, men ved å bare bruke noen få iteratorer fra denne pakken slipper elevene å skrive kompliserte løkker. Da går det raskt å lage en tabell som utgangspunkt for videre utforsking og grunnlag for å finne en generell løsning.

itertools.permutations lar deg lage en løkke over alle mulige rekkefølger av elementene i en liste, du kan også spesifisere hvor stort utvalg du vil gjøre. Det er også en itertools.combinations, som gir deg uordnede kombinasjoner, med eller uten tilbakelegging.

Problem

På et av mine lokale vitensentre er denne oppgaven presentert: bruk sifrene fra 0 til 9 en gang hver og gjør differansen \(AB \cdot CDE – FG \cdot HIJ\) så liten som mulig. For eksempel blir \(90 \cdot 724 – 81\cdot 536 = 21744\)

Forenkle problemet

Det kan være enklere for hånd om du gjør problemet mindre, kanskje til produkt av et tosifret tall og et ensifret tall. Da blir for eksempel \(12\cdot 3 = 09\cdot 4\), og \(12\cdot 6 = 08\cdot 9\).

• Hva har dette med primtall å gjøre?
• Finnes det en løsning som bare bruker de seks første sifrene?
• Er det mulig å gjøre det slik uten at 0 er første siffer i et av tallene?
• Hvordan er fordelingen av odde- og partall?
• Hva skjer om 5 er siste siffer i et av tallene?

Alle løsninger med python

Det er \(10! = 3628800\) mulige måter å fordele sifrene, så det går ikke for hånd. Slik jeg har gjort det i python under, settes først listen med siffer i en ny rekkefølge. Så blir de tre første til et tresifret tall, de to neste til et tosifret tall osv. itertools.permutations går gjennom alle de mulige rekkefølgene, og med «bare» 3,6 millioner permutasjoner går det på få sekunder.

import itertools as it

siffer = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']

for k in it.permutations(siffer):
    s1 = int("".join(k[0:3]))
    s2 = int("".join(k[3:5]))
    s3 = int("".join(k[5:8]))
    s4 = int("".join(k[8:10]))
    
    if s1*s2 - (s3*s4) == 0:
        print(s1, s2, s3, s4)

Utvidelser

Selv når du har en mulighet for å lage alle løsningene, vil det være mer å utforske.

• Hvordan kan du få koden til å utelukke matematisk like løsninger? \(067\cdot 58 = 058\cdot 67\) for eksempel.
• Hva er det største og minste mulige produktet?
• Dersom et av de tresifrede tallene er et primtall, er det fremdeles mulig å få differanse 0?
• Er det ulike løsninger som gjenbruker samme tall?
• Hvilket tall forekommer oftest?
• Hva er sansynligheten for å treffe 0 om du legger brikkene tilfeldig?
• Hva er sannsynligheten for å komme innenfor 100? 1000? Hvordan vil grafen til sannsynlighetsfordelingen se ut?
• Hva skjer om du bytter ut sifrene, for eksempel tar bort 7 og legger til en ekstra 3? Eller om du bruker de fem første eller siste sifrene to ganger?
• Hva skjer om du gjør om multiplikasjonen til divisjon?