Antal möjliga kominationer

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

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.

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.

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.)