Wszystkie możliwe wariacje Opcje

[KR2615]

Hej. Mam zagwostkę natury programistycznej. Zapomniałem dość długiego i skomplikowanego hasła do szyfrowania dysku (Luks w Linuxie). Przypominam je sobie ale nie mam pewności czy:
1. Na pierwszej pozycji stoi A czy a.
2. Na drugiej znajduje się b, B lub &
3. Co do trzeciej mam pewność, że jest to cyferka 3.
4. Na czwartej pozycji może znajdować sie małe lub dużer D.
5. Piąta to na pewno znak dolara.
itd, itp.

Stworzyłem taki kod:

[PHP] pobierz, plaintext 
<?php
$char[1] = array('a', 'A');
$char[2] = array('b', 'B', "&");
$char[3] = array('3');
$char[4] = array('d', 'D');
$char[5] = array('$');
 
for() {	
		?
}
?>
[PHP] pobierz, plaintext 

Niestety przyszłła zaćma i nie mam pojęcia jak za pomocą PHP lub dowolnego innego języka wygenerować wszystkie możliwe wariacje (nie krzyczcie, jeśli użyłem złego matematycznego określenia).
Z góry dzięki za podpowiedzi!

[gino]

Najpierw trochę liczenia, żebyś wiedział z czym się mierzysz.

Kod

$chars = array
    (    
        array('A','X'),
        array('B','C')
);

Dla takiej tablicy ilość kombinacji haseł (zakładając, że w każdej tablicy jesteśmy pewni ilość znaków jakie mogą wystąpić to 2) wynosi 2^2 czyli niewiele bo 4 hasła.
Załóżmy jednak, że następna tablica zawiera 3 znaki, które mogą wystąpić:

Kod

$chars = array
    (    
        array('A','X'),
        array('B','C'),
                array('D','E','F')
);

Policzmy 2^2*3^1 = 12, to też niewiele, mówimy jednak o hasłach krótkich 3 literowych.

Policzmy trochę więcej liter, czyli dla pierwszego znaku mogą to być 2 litery, dla 2 - 2, dla 3 - 3 i dla 4 też 3:

Kod

$chars = array
    (    
        array('A','X'),
        array('B','C'),
        array('D','E','F'),
        array('G','H','I'),
        array('J','K')
);

3^2*2^3=72
tyle możliwych haseł dla 5 literowego hasła po warunkiem jaki uczyniliśmy.

Idźmy dalej:

Kod

$chars = array
    (
        array('A','X'),
        array('B','C'),
        array('D','E','F'),
        array('G','H','I'),
        array('J','K'),
        array('L','M','N'),
        array('O','P','R'),
        array('S','T','U','W'),
        array('X')
);

Dla 9 literowego hasła w warunkach jakie założyliśmy, czyli taka a nie inna litera może być miejscach od 1 do 9 mamy:

4^1*3^4*2^3*1^1 = 2592

Tyle masz haseł do sprawdzenia dla hasła 9 literowego. Myślę, że nie ma sensu liczyć dalej i już wiesz o co chodzi.

Jeśli to tylko zagwostka programistyczna to jako ciekawostka w PHP można to zrobić prostą funkcja rekurencyjną, która wyświetli złożone hasła:

Kod

function show($str, $arr, $i)
    {
        if ($i < count($arr)){
                foreach ($arr[$i] as $value)
                show($str.$value, $arr, $i + 1);
            
        }
        else
        {
            echo $str.'<br>';
        }
    }

$chars = array
    (
        array('A','X'),
        array('B','C'),
        array('D','E','F'),
        array('G','H','I'),
        array('J','K'),
        array('L','M','N'),
        array('O','P','R'),
        array('S','T','U','W'),
        array('X')
);

show('', $chars, 0);

Ale to do haseł w miarę krótkich i przy założeniu, że jesteśmy pewni 2-3 znaków. Możesz policzyć ile będzie kombinacji haseł jeśli w każdej tablicy będziesz pewien 4,5 czy 6 znaków. Php jest ograniczone czasem wykonywania skryptu i wielkości złożonych danych, w związku z czym dla obciążenia takiej funkcji większą ilością danych (a dokładniej ilością tablic z możliwymi literami hasła, dosyć długiego jak piszesz) na pewno php się do tego nie nadaje i zacznie sypać błędami czy to przekroczeniem czau wykonania czy rozmiarem wyplutych danych.
Przeniesienie tego na język C/C++ czy inny nie powinno być raczej problemem.
Nie stawiam tego jako rozwiązanie problemu, raczej jako ciekawostkę i liczbę haseł do ewentualnego sprawdzenia przy ograniczonych warunkach.

[KR2615]

Tyle masz haseł do sprawdzenia dla hasła 9 literowego. Myślę, że nie ma sensu liczyć dalej i już wiesz o co chodzi.

Wiem, o złożoność obliczeniową problemu. Zastanowiłem się nad tym za nim jeszcze usiadłem do problemu. Tak się szczęśliwie składa, że większości znaków jestem pewien. Kilkanaście to dwie możliwości, kilka - 3. W sumie nieco ponad 40k możliwości hasła. Udało mi się je wszystkie wygenerować. Teraz sprawdzam.

Zastanawiam się tylko co jeśli mój błąd nie polega na zamianie małej literki z dużą ale na przestawieniu, np. ACBD zamiast ABCD. Ale to pieść przyszłości. Jeśli nic nie wyjdzie z tych 40k będę się zastanawiał, jak to zagadnienie programistyczne rozpracować.