Antal möjliga kominationer

Trädvy Permalänk
Medlem
Plats
Göteborg
Registrerad
Apr 2007

Antal möjliga kominationer

Hej alla nattfjärilar på sweclockers!

Jag undrar om någon skulle kunna ge mig en speciell formell för att räkna ut ur många möjliga kombinationer det finns av lösenord om man vet att lösenordet är 10 tecken långt och det finns 16 tecken att välja mellan och varje tecken endast får användas två ggr i varje lösenord.

Har själv försökt klura lite på det, men det tar för lång tid och mitt tålamod börjar ta slut.

Hjälp?

"Att betala för att icke-modulärt och klaga på det är korkat. Som att köpa en opel och klaga på att du inte fick en mercedes..."

Trädvy Permalänk
Medlem
Registrerad
Jul 2008
Skrivet av Axelander23:

Hej alla nattfjärilar på sweclockers!

Jag undrar om någon skulle kunna ge mig en speciell formell för att räkna ut ur många möjliga kombinationer det finns av lösenord om man vet att lösenordet är 10 tecken långt och det finns 16 tecken att välja mellan och varje tecken endast får användas två ggr i varje lösenord.

Har själv försökt klura lite på det, men det tar för lång tid och mitt tålamod börjar ta slut.

Hjälp?

16x16x15x15x14x14x13x13x12x12.
Kan det stämma? Osäker på om jag får med alla permutationer.

Citera för svar!

Trädvy Permalänk
Medlem
Plats
Västra Götaland
Registrerad
Jul 2008

Utan återanvändning:
C(16,10) = 16! / 10! (16 - 10)! = 8008
Fri återanvändning:
CR(16,10) = (16+10-1)! / 10! (16 - 1)! = 3268760

Så vi kan i alla fall begränsa oss till intervallet 8008-3268760.

http://www.calculatorsoup.com/calculators/discretemathematics...

Quad-quad core med kvävekylning och kokvattenreaktor.

Trädvy Permalänk
Medlem
Registrerad
Jul 2008
Skrivet av aniron:

Utan återanvändning:
C(16,10) = 16! / 10! (16 - 10)! = 8008
Fri återanvändning:
CR(16,10) = (16+10-1)! / 10! (16 - 1)! = 3268760

Så vi kan i alla fall begränsa oss till intervallet 8008-3268760.

http://www.calculatorsoup.com/calculators/discretemathematics...

8008 stämmer väl inte? Har du inte räknat att ordningen inte spelar roll? För det gör den ju när det kommer till lösenord.

Citera för svar!

Trädvy Permalänk
Medlem
Plats
Hässelby, Stockholm
Registrerad
Apr 2003

Antal lösenord om man hade fått återanvända siffrorna obegränsat = 16^10 = 1099511627776 =~ 1,09 biljoner kombinationer. Detta är en absolut övre gräns för antalet kombinationer, oavsett hur fel jag har i resten av uträkningen.

Vi måste dra ifrån de förbjudna kombinationerna. Jag får det till att det finns 120 olika sätt att placera ut samma siffra på tre platser i kombinationslåset. (Har glömt det mesta från matstaten men gjorde ett excelark där jag skrev in alla kombinationer.) Det finns 16 sådana förbjudna placeringar (en per siffra) och det finns 16^7 förbjudna kombinationer för varje "tre-placering". Den nedre gränsen för antalet kombinationer blir då 16^10-16*120*16^7 =~ 584 miljarder kombinationer. En del av dessa är emellertid "dubbelt förbjudna", så det verkliga antalet är högre.

Ungefär där kom jag på hur tråkigt det är med kombinatorik så jag tappade intresset. Du kan vara helt säker på att antalet kombinationer är ett mycket stort tal, men kan gå att knäcka med brute force om man tillåter en dator att göra många gissningar per sekund.

Är det inte Fingal Olsson som sitter där borta?

Trädvy Permalänk
Glömsk
Plats
Userland
Registrerad
Jul 2001

Jag får det till 752148633600 alltså ungefär 68% av de 16^10 möjligheter om dublettvilkoret inte fanns.

Algoritmen fungerar såhär:

1. Generera alla unika "alfabet" som kan användas för att skapa lösenorden. Vill säga alla strängar från {0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7} till {8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15}.
2. För varje alfabet räkna antalet unika (lexikografiska) permutationer. Det är helt enkelt (10!)/(d^2) där d är antalet dubletter i alfabetet.

Kod: http://pastebin.com/G2wMLjUX Kör på < 1 sekund på min gamla dator.

Edit: Den här algoritmen är ju skitkass. Finns en mycket bättre. Se om nån kan klura ut den

...man is not free unless government is limited. There's a clear cause and effect here that is as neat and predictable as a law of physics: As government expands, liberty contracts.

Trädvy Permalänk
Medlem
Plats
Umeå
Registrerad
Nov 2004
Skrivet av Psionicist:

Jag får det till 752148633600 alltså ungefär 68% av de 16^10 möjligheter om dublettvilkoret inte fanns.

Algoritmen fungerar såhär:

1. Generera alla unika "alfabet" som kan användas för att skapa lösenorden. Vill säga alla strängar från {0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7} till {8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15}.
2. För varje alfabet räkna antalet unika (lexikografiska) permutationer. Det är helt enkelt (10!)/(d^2) där d är antalet dubletter i alfabetet.

Kod: http://pastebin.com/G2wMLjUX Kör på < 1 sekund på min gamla dator.

Edit: Den här algoritmen är ju skitkass. Finns en mycket bättre. Se om nån kan klura ut den

Det är väl alfabeten {0, 0, 1, 1, 2, 2, 3, 3, 4, 4} till {11, 11, 12, 12, 13, 13, 14, 14, 15, 15} som gäller?

...och något snabbare fick jag det med lite rekursion (egentligen är det väl i princip samma algoritm, så när som på check())

#include <stdio.h> int cnt = 0; unsigned long long rec(int *a, int i) { int j, dup = 0; unsigned long long ret = 0; if(i == 10) { cnt++; for(j = 1; j < 10; j++) if(a[j] == a[j-1]) dup++; return 3628800 / (1 << dup); } for(a[i] = i ? a[i - 1] : i; a[i] < 16; a[i]++) if(i <= 1 || a[i] != a[i - 2]) ret += rec(a, i + 1); return ret; } int main() { int arr[10]; unsigned long long res = rec(arr, 0); printf("%d\n%llu\n", cnt, res); return 0; }

(Samma tidsåtgång ±.01 sek om de respektive programmen (modifieras och) kompileras som C eller C++)

$ g++ -O3 din_kod.cc && time ./a.out 996216 752148633600 ./a.out 0.06s user 0.00s system 98% cpu 0.060 total $ gcc -O3 min_kod.c && time ./a.out 996216 752148633600 ./a.out 0.02s user 0.00s system 96% cpu 0.017 total

Och resultatet verkar stämma med ren kombinatorik.
Om det är n dubletter så får vi välja n av 16 symboler, (16 välj n).
Dessa ska placerar ut på 2n av 10 möjliga platser, (16 välj n) * (10 välj 2n).
Dessa 2n platser kan permuteras på 2n! sätt, (16 välj n) * (10 välj 2n) * (2n)!
Varav 2^n är dubletter, (16 välj n) * (10 välj 2n) * (2n)! / 2^n
För varje sätt att välja n dubletter så kan vi välja 10 - 2n icke-dubletter ur 16 - n möjliga symboler, (16 välj n) * (10 välj 2n) * (2n)! / 2^n * (16-n välj 10 - 2n)
Och dessa kan permuteras på (10-2n)! sätt (16 välj n) * (10 välj 2n) * (2n)! / 2^n * (16-n välj 10 - 2n) * (10-2n)!

Att verifiera att Σ_(n=0)^5 (16 välj n) * (10 välj 2n) * (2n)! / 2^n * (16-n välj 10 - 2n) * (10-2n)! = 752148633600 lämnar jag som en övning för läsaren.

(Edit: klarogörande av testkörningar.)