Sortera tal (Programmering/Övriga programmeringsspråk)

Hur menar du med att testa varje tal? Ett alternativ skulle kunna vara att splittra alla tal i sina sex individuella siffror, radera alla siffror som är dupletter, och sedan kontrollera att längden av varje tal fortfarande är sex karaktärer, men det innebär att man måste testa en del.

Menar du lägga i en viss ordning, eller bara sålla bort vissa? Sortera brukar betyda lägga i ordning, i programmeringssammanhang.

Man måste rimligen titta på varje tal för att se vad man ska göra med det, om listan inte redan från början är ordnad på något speciellt sätt.

dajamanté skrev:
Good morgon PA:re!
Finns det en smart sätt att sortera en lista av 6-siffriga tal, för att behålla alla som är byggda av olika siffror, utan att testa varje tal?

"... behålla alla som är byggda av olika siffror ...", menar du då att till exempel tal som

123456

123457

ska vara kvar eftersom varje tal har 6 unika siffror men att tal som

112345

912349

ska tas bort eftersom de innehåller sifferdubletter?

@Laguna och @Yngve:

Ja, jag menar att radera bort alla tal med dublettsiffror mellan två integers, till ex 123456 och 457812, utan att behöva titta individuellt på 123456, 123457, 123458...

Listan är i bra order.

@Smutstvätt: det är det jag vill undvika.

Nu förstår jag inte frågan längre. Kan du visa en lista med fem tal och visa vilka som ska bort?

- Tal utan siffer-dubbletter är effektivt representationer av permutationer (med viss modifikation för att hantera 0:or i mitten av tal) och det finns gott om effektiva algoritmer för att genera listor av permutationer (Jag tenderar att använda SJT-algoritmen om jag bara behöver fula ihop något snabbt). Jag tar upp detta eftersom det för stora antal siffror måste det rimligtvis vara snabbare att genera sina approximativt $n!$ permutationer snarare än att gå igenom approximativt $10^n$ och plocka bort stora merparten av alla tal.

Jag tar upp detta eftersom generering från grunden gör att man slipper inspektera talen då alla man får fram är korrekta från början. (Dessa algoritmer genererar en lista redan i sorterad form så behövs ingen efterhandssortering)

- När det kommer till att radera element ur en befintlig lista så har jag dock svårt att definitionsmässigt se hur radering som en operation kan göras utan inspektion av elementen. Även om

Det enda man kan sträva efter i mina ögon är att se till att ens

är_detta_ett_dubblett_tal(n)-funktion är så effektiv som möjligt när man väl gör en genomlöpning av alla element i listan.

Det är nog även bättre att se det som att man plockar ut de korrekta talen ut listan och skapar en ny "inga dubbletter-lista" snarare än raderar ur en befintlig då att ta bort element i mitten av en lista kan vara ganska beräkningstungt beroende på datastrukturen listan mostsvarar.

Här är en kass brute-force där man just kollar på alla tal en efter en och plockar ut de som stämmer:

https://colab.research.google.com/drive/1ZCiQhg5YMO7fouP1sMVWOlXEbGwkr7e_

Den följer alltså inte Dajamantes krav på att på något sätt inte kolla.

Filen är öppen för redigering så ni kan lägga till egna python lösningar side-by-side om ni vill jämföra lösningar och att kopiera in hir är jobbigt.

dajamanté skrev:
@Laguna och @Yngve:
Ja, jag menar att radera bort alla tal med dublettsiffror mellan två integers, till ex 123456 och 457812, utan att behöva titta individuellt på 123456, 123457, 123458...
Listan är i bra order.
@Smutstvätt: det är det jag vill undvika.

Hmmm. Är det så att du har en lista

list

och att du vet att alla tal mellan n och m ska raderas så att du helt enkellt vill gå från

list - > ny_list med element 1 till n och m till sista

Vad som är effektivaste viset för det kan vara ett programmeringsspråksspecifikt problem snarare än ett allmännt teoretiskt problem. I python kunde man fula det med

ny_list = list[:n + 1] + list[m:]

dvs skapa en ny lista genom konkatenering av två dellistor men huruvida detta är den effektivaste metoden är osagt. Som sagt av mig ovan är det ofta effektivare att bara plocka ut elementen och skapa en ny lista snarare än att modifiera en befintlig. Internt skapar datorn ändå generellt en ny lista när en gammal modifieras.

Tackar för alla svar, det hade kanske varit bättre för alla om jag har länkat frågan: Heir's dilemma.

Man får två tal, $M, N$ och måste testa alla tal mellan dessa två (men nu har ni frågan, så det är nog enklare att jag inte försöker omformulera :p)

Jag har en lösning men jag vill optimisera den för att inte behöva titta på varje tal mellan $M, N$ .

Fast jag tror faktiskt i så fall att den effektivaste metoden är att kolla på alla tal mellan M och N men att ha en kontroll-algoritm som avbryter sig själv så snabbt som möjligt dvs om den ska kontroller 123455 och läser från höger till vänster så abryter den sig själv direkt efter att ha stött på de två 5:orna utan att kolla på sista siffran eller vid läsning av 123457 avbryter sig själv i samma stund som den ser att talet inte är delbart med 7 och inte fortsätter längre i onödan.

Men en tillräckligt bra sådan algoritm kommer tiden det tar att kontrollera de flesta talen mellan M och N att vara försummbar runt 10-100 operationer och totala tiden blir låg ändå.

Modifierade koden ovan

https://colab.research.google.com/drive/1ZCiQhg5YMO7fouP1sMVWOlXEbGwkr7e_#scrollTo=_ValJrWE-RnU

genom att tillägga kravet att talet ska vara delbart med sina egna siffror och då tar der i colab-miljön runt 6 sekunder att kontrollera alla tal mellan 10^6 och 10^7 och som upppgiften förtäljer så är poängen att man delar upp detta intervall i flera mindre delar så att L och M ligger nära varandra (säg med 10^5 steg ifrån varandra) och så kommer söktiden att bli kortare och garanterat gå under 1.5 1s vilket var kravet för lösningen.

M = 200000 och N = 300000 levereras på 0.07 s även vid direkt genomsökning av alla tal däremellan men har vi något skäl att tro att det ska gå att göra snabbare?

(Sådana metoder är ju parallelliserbara vilket jag tycker antyds är poängen i uppgiften)

Jag testar om tallen innehåller nollor, och om den gör det, då kör jag continue. Då gör jag samma för att testa om alla tal är unika, och är dem inte det kör jag continue också. Och till slut testar jag om alla siffror dividerar talet, och får 0.13 s.

Parallelprogrammering har vi inte börjat med än, men jag ska komma ihåg det!

Varför har du n = n // 10?

Var kom tidsgränsen 1,5s ifrån?

Laguna skrev:
Var kom tidsgränsen 1,5s ifrån?

1 sekund stod det tydligen i rutan till höger. (1.5 var svårighetsgraden)

Varför har du n = n // 10?

Det är så jag löper igenom siffra för siffra genom att stegvis göra om talet så att siffrorna förskjuts till att vara entalssifrran.

1234 % 10 = 4

1234 // 10 = 123

123 % 10 = 3

123 // 10 = 12

12 % 10 = 2

12 // 10 = 1

1 % 10 = 1

1 // 10 = 0 (där bryter jag)

Kul uppgift. Här är en liten observation: om 5 är med måste den vara sist.

Aha jag menade vad är skillnaden mellan number = number /10 och number //10? är det en Python grej?

Jag gör modulo på den 6-siffriga tal och parkerar resten i array, och då number /= number för att få nästa.

Dubbeldivision är heltalsdivision och enkeldivision är flyttalsdivision. Då python inte är hårdtypat, dvs att om det är heltal eller flyttal bestäms från sammanhanget så behövs dubbeldivision för att programmet inte ska råka börja räkna på flyttal istället.

SeriousCephalopod skrev:
Dubbeldivision är heltalsdivision och enkeldivision är flyttalsdivision. Då python inte är hårdtypat, dvs att om det är heltal eller flyttal bestäms från sammanhanget så behövs dubbeldivision för att programmet inte ska råka börja räkna på flyttal istället.

I Python 3 är det på detta vis. I Python 2 fanns inte //, och / mellan två heltal trunkerade resultatet.

Mitt dumma brute force-program tar nu två sekunder för att hitta alla talen. Om jag behövde lösa uppgiften skulle jag skriva ett nytt program som redan har samtliga tal (för de är inte många) i en lista och sedan hitta minsta och största i det angivna intervallet, och räkna hur många det är däremellan. Men dum-programmet kanske går på under en sekund på deras snabbare dator.

Oh, nvm jag sökte tydligen ut 7-siffriga tal när jag sade att min algoritm tog 5 sekunder.

Brute-forcar jag på 6-siffriga så tar det 0,6 sekunder i google.colab-miljön.

Sedan tog jag och skrev en något snabbare algoritm (se andra stycker i samma fil som tidigare)

https://colab.research.google.com/drive/1ZCiQhg5YMO7fouP1sMVWOlXEbGwkr7e_#scrollTo=DOz0nwoaC7vN

Vilken genererar alla permutationer av {1,2,3,4,5,6,7,8,9} med 6 element och sedan stryker tal bland dem som inte är delbara med siffrorna vilket kräver 0.2 sekunder i samma miljö. Notera dock att denna metod kräver mycket mer minne.

Dock så skalar generering något bättre än brute-force-metoden

Bruteforce för tal med 6 siffror: 0.6 s

Permutationsgenerering för tal med 6 siffror: 0.2

Bruteforce för tal med 7 siffror: 6 s

Permutationsgenerering för tal med 7 siffror: 0.6 s

Bruteforce för tal med 8 siffror: 60

Permutationsgenerering för tal med 8 siffror: 1.2

Laguna skrev:
Mitt dumma brute force-program tar nu två sekunder för att hitta alla talen. Om jag behövde lösa uppgiften skulle jag skriva ett nytt program som redan har samtliga tal (för de är inte många) i en lista och sedan hitta minsta och största i det angivna intervallet, och räkna hur många det är däremellan. Men dum-programmet kanske går på under en sekund på deras snabbare dator.

Håller med om att ett sånt fuskprogram är den snabbaste lösningen ; ) .

Givet att tops-corande lösningar på kattis-sidan har körtider på 0.00 s så tänker jag anta att de hade den idén också. https://open.kattis.com/problems/heirsdilemma/statistics

Edit: jag läste inte ordentligt.

Finns det en permutation method i Collections eller något annat inbyggt metod?

Beror på vilket programmeringsspråk det gäller.

Annars finns det generellt något paket/bibliotek man kan importera ngåonstansifrån om man vill ha en snabb lösning. Det är en operation jag använder rätt sällan så jag har inte koll rent allmännt.

Jag kör i java. Och jag tar gärna den generella paket!

Grym tråd. Lärde mig mycket av denna.