Количество возможных последовательностей из 16 символов есть с некоторыми ограничениями

Question

Сколько возможных последовательностей можно сформировать, подчиняющихся следующим правилам:

1. Каждая последовательность формируется из символов 0-9a-f.

2. Каждая последовательность состоит ровно из 16 символов.

   0123456789abcdef    ok
   0123456789abcde     XXX
   0123456789abcdeff   XXX
   

3. Символы могут повторяться, но не более 4 раз.

   00abcdefabcdef00    ok
   00abcde0abcdef00    XXX
   

4. Символ не может появляться три раза подряд.

   00abcdefabcdef12    ok
   000bcdefabcdef12    XXX
   

5. Может быть не более двух пар.

   00abcdefabcdef11    ok
   00abcde88edcba11    XXX
   

Кроме того, сколько времени потребуется, чтобы сгенерировать их все?

Answer 1

Эта программа насчитывает 16 390 235 567 479 693 920 паролей.

#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>


enum { RLength = 16 };  //  Required length of password.
enum { NChars = 16 };   //  Number of characters in alphabet.


typedef struct
{
    /*  N[i] counts how many instances of i are left to use, as constrained
        by rule 3.
    */
    unsigned N[NChars];

    /*  NPairs counts how many more pairs are allowed, as constrained by
        rule 5.
    */
    unsigned NPairs;

    /*  Used counts how many characters have been distinguished by choosing
        them as a represenative.  Symmetry remains unbroken for NChars - Used
        characters.
    */
    unsigned Used;
} Supply;


/*  Count the number of passwords that can be formed starting with a string
    (in String) of length Length, with state S.
*/
static uint64_t Count(int Length, Supply *S, char *String)
{
    /*  If we filled the string, we have one password that obeys the rules.
        Return that.  Otherwise, consider suffixing more characters.
    */
    if (Length == RLength)
        return 1;

    //  Initialize a count of the number of passwords beginning with String.
    uint64_t C = 0;

    //  Consider suffixing each character distinguished so far.
    for (unsigned Char = 0; Char < S->Used; ++Char)
    {
        /*  If it would violate rule 3, limiting how many times the character
            is used, do not suffix this character.
        */
        if (S->N[Char] == 0) continue;

        //  Does the new character form a pair with the previous character?
        unsigned IsPair = String[Length-1] == Char;

        if (IsPair)
        {
            /*  If it would violate rule 4, a character may not appear three
                times in a row, do not suffix this character.
            */
            if (String[Length-2] == Char) continue;

            /*  If it would violate rule 5, limiting how many times pairs may
                appear, do not suffix this character.
            */
            if (S->NPairs == 0) continue;

            /*  If it forms a pair, and our limit is not reached, count the
                pair.
            */
            --S->NPairs;
        }

        //  Count the character.
        --S->N[Char];

        //  Suffix the character.
        String[Length] = Char;

        //  Add as many passwords as we can form by suffixing more characters.
        C += Count(Length+1, S, String);

        //  Undo our changes to S.
        ++S->N[Char];
        S->NPairs += IsPair;
    }

    /*  Besides all the distinguished characters, select a representative from
        the pool (we use the next unused character in numerical order), count
        the passwords we can form from it, and multiply by the number of
        characters that were in the pool.
    */
    if (S->Used < NChars)
    {
        /*  A new character cannot violate rule 3 (has not been used 4 times
            yet, rule 4 (has not appeared three times in a row), or rule 5
            (does not form a pair that could pass the pair limit).  So we know,
            without any tests, that we can suffix it.
        */

        //  Use the next unused character as a representative.
        unsigned Char = S->Used;

        /*  By symmetry, we could use any of the remaining NChars - S->Used
            characters here, so the total number of passwords that can be
            formed from the current state is that number times the number that
            can be formed by suffixing this particular representative.
        */
        unsigned Multiplier = NChars - S->Used;

        //  Record another character is being distinguished.
        ++S->Used;

        //  Decrement the count for this character and suffix it to the string.
        --S->N[Char];
        String[Length] = Char;

        //  Add as many passwords as can be formed by suffixing a new character.
        C += Multiplier * Count(Length+1, S, String);

        //  Undo our changes to S.
        ++S->N[Char];
        --S->Used;
    }

    //  Return the computed count.
    return C;
}


int main(void)
{
    /*  Initialize our "supply" of characters.  There are no distinguished
        characters, two pairs may be used, and each character may be used at
        most 4 times.
    */
    Supply S = { .Used = 0, .NPairs = 2 };
    for (unsigned Char = 0; Char < NChars; ++Char)
        S.N[Char] = 4;

    /*  Prepare space for string of RLength characters preceded by a sentinel
        (-1).  The sentinel permits us to test for a repeated character without
        worrying about whether the indexing goes outside array bounds.
    */
    char String[RLength+1] = { -1 };

    printf("There are %" PRIu64 " possible passwords.\n",
        Count(0, &S, String+1));
}

Answer 2

В комбинаторике подсчет обычно довольно прост и может быть выполнен гораздо быстрее, чем исчерпывающая генерация каждой альтернативы (или, что еще хуже, исчерпывающая генерация надмножества возможностей для их фильтрации). Один из распространенных методов - свести данную проблему к комбинациям небольшого (i sh) количества непересекающихся подзадач, где можно увидеть, сколько раз каждая подзадача вносит вклад в общую сумму. Такой вид анализа часто может приводить к динамическим c программным решениям или, как показано ниже, к мемоизированным рекурсивным решениям.

Поскольку комбинаторные c результаты обычно огромны, генерация всех возможных даже если это можно сделать очень быстро для каждой последовательности, это непрактично во всех случаях, кроме самых тривиальных. Например, для этого конкретного вопроса я сделал приблизительную оценку в комментарии (после удаления):

Существует 18446744073709551616 возможных 64-битных (16 hex-di git) чисел, что очень много, около 18 миллиардов миллиардов. Так что, если бы я мог генерировать и тестировать один из них в секунду, это заняло бы у меня 18 миллиардов секунд, или около 571 года. Таким образом, имея доступ к кластеру из 1000 96-ядерных серверов, я мог бы сделать все это примерно за 54 часа, то есть чуть более чем за два дня. Amazon продаст мне один 96-ядерный сервер чуть менее чем за доллар в час (спотовые цены), так что тысяча серверов на 54 часа будет стоить чуть меньше 50 000 долларов США. Возможно, это в пределах разумного. (Но это только для генерации.)

Несомненно, исходный вопрос является частью исследования возможности попробовать каждую возможную последовательность путем взлома пароля, и на самом деле нет необходимости создавать точный подсчет количества возможных паролей, чтобы продемонстрировать непрактичность этого подхода (или его практичность для организаций, у которых есть бюджет, достаточный для оплаты необходимых вычислительных ресурсов). Как показывает приведенная выше оценка, пароль с 64-битной энтропией на самом деле не так безопасен, если то, что он защищает, достаточно ценно. Примите это во внимание при создании пароля для вещей, которые вы цените.

Тем не менее, может быть интересно вычислить точные комбинаторы c отсчетов, если только по какой-либо причине, кроме интеллектуальной проблемы.

Следующее - в основном доказательство концепции; Я написал его в Python, потому что Python предлагает некоторые возможности, воспроизведение и отладка которых в C: ha sh таблицах с ключами кортежа и целочисленными арифметическими числами произвольной точности c потребовали бы много времени. Его можно было бы переписать на C (или, что проще, на C ++), и код Python наверняка можно было бы улучшить, но, учитывая, что для вычисления запроса на подсчет в исходном вопросе требуется всего 70 миллисекунд, усилия кажется ненужным.

Эта программа тщательно группирует возможные последовательности по разным разделам и кэширует результаты в таблице памяти. В случае последовательностей длиной 16, как и в OP, кеш заканчивается 2540 записями, что означает, что основные вычисления выполняются только 2540 раз:

# The basis of the categorization are symbol usage vectors, which count the
# number of symbols used (that is, present in a prefix of the sequence)
# `i` times, for `i` ranging from 1 to the maximum number of symbol uses
# (4 in the case of this question). I tried to generalise the code for different
# parameters (length of the sequence, number of distinct symbols, maximum
# use count, maximum number of pairs). Increasing any of these parameters will,
# of course, increase the number of cases that need to be checked and thus slow
# the program down, but it seems to work for some quite large values. 

# Because constantly adjusting the index was driving me crazy, I ended up
# using 1-based indexing for the usage vectors; the element with index 0 always
# has the value 0. This creates several inefficiencies but the practical
# consequences are insignificant.

### Functions to manipulate usage vectors

def noprev(used, prevcnt):
    """Decrements the use count of the previous symbol"""
    return used[:prevcnt] + (used[prevcnt] - 1,) + used[prevcnt + 1:]
def bump1(used, count):
    """Registers that one symbol (with supplied count) is used once more."""
    return ( used[:count]
           + (used[count] - 1, used[count + 1] + 1)
           + used[count + 2:]
           )
def bump2(used, count):
    """Registers that one symbol (with supplied count) is used twice more."""
    return ( used[:count]
           + (used[count] - 1, used[count + 1], used[count + 2] + 1)
           + used[count + 3:]
           )
def add1(used):
    """Registers a new symbol used once."""
    return (0, used[1] + 1) + used[2:]
def add2(used):
    """Registers a new symbol used twice."""
    return (0, used[1], used[2] + 1) + used[3:]

def count(NSlots, NSyms, MaxUses, MaxPairs):
    """Counts the number of sequences of length NSlots over an alphabet
       of NSyms symbols where no symbol is used more than MaxUses times,
       no symbol appears three times in a row, and there are no more than 
       MaxPairs pairs of symbols.
    """
    cache = {}

    # Canonical description of the problem, used as a cache key
    #   pairs: the number of pairs in the prefix
    #   prevcnt: the use count of the last symbol in the prefix
    #   used: for i in [1, NSyms], the number of symbols used i times
    #         Note: used[0] is always 0. This problem is naturally 1-based
    def helper(pairs, prevcnt, used):
        key = (pairs, prevcnt, used)
        if key not in cache:
            # avail_slots: Number of remaining slots.
            avail_slots = NSlots - sum(i * count for i, count in enumerate(used))
            if avail_slots == 0:
                total = 1
            else:
                # avail_syms:  Number of unused symbols.
                avail_syms = NSyms - sum(used)
                # We can't use the previous symbol (which means we need
                # to decrease the number of symbols with prevcnt uses).
                adjusted = noprev(used, prevcnt)[:-1]
                # First, add single repeats of already used symbols
                total = sum(count * helper(pairs, i + 1, bump1(used, i))
                            for i, count in enumerate(adjusted)
                            if count)
                # Then, a single instance of a new symbol
                if avail_syms:
                    total += avail_syms * helper(pairs, 1, add1(used))

                # If we can add pairs, add the already not-too-used symbols
                if pairs and avail_slots > 1:
                    total += sum(count * helper(pairs - 1, i + 2, bump2(used, i))
                                 for i, count in enumerate(adjusted[:-1])
                                 if count)
                    # And a pair of a new symbol
                    if avail_syms:
                        total += avail_syms * helper(pairs - 1, 2, add2(used))
            cache[key] = total
        return cache[key]

    rv = helper(MaxPairs, MaxUses, (0,)*(MaxUses + 1))
    #   print("Cache size: ", len(cache))
    return rv

# From the command line, run this with the command:
# python3 SLOTS SYMBOLS USE_MAX PAIR_MAX
# There are defaults for all four argument.
if __name__ == "__main__":
    from sys import argv
    NSlots, NSyms, MaxUses, MaxPairs = 16, 16, 4, 2
    if len(argv) > 1: NSlots   = int(argv[1])
    if len(argv) > 2: NSyms    = int(argv[2])
    if len(argv) > 3: MaxUses  = int(argv[3])
    if len(argv) > 4: MaxPairs = int(argv[4])
    print (NSlots, NSyms, MaxUses, MaxPairs,
           count(NSlots, NSyms, MaxUses, MaxPairs))

Вот результат использования этой программы для вычисления количества всех допустимых последовательностей (поскольку последовательность длиннее 64 невозможна с учетом ограничений), всего за 11 секунд:

$ time for i in $(seq 1 65); do python3 -m count $i 16 4; done
1 16 4 2 16
2 16 4 2 256
3 16 4 2 4080
4 16 4 2 65040
5 16 4 2 1036800
6 16 4 2 16524000
7 16 4 2 263239200
8 16 4 2 4190907600
9 16 4 2 66663777600
10 16 4 2 1059231378240
11 16 4 2 16807277588640
12 16 4 2 266248909553760
13 16 4 2 4209520662285120
14 16 4 2 66404063202640800
15 16 4 2 1044790948722393600
16 16 4 2 16390235567479693920
17 16 4 2 256273126082439298560
18 16 4 2 3992239682632407024000
19 16 4 2 61937222586063601795200
20 16 4 2 956591119531904748877440
21 16 4 2 14701107045788393912922240
22 16 4 2 224710650516510785696509440
23 16 4 2 3414592455661342007436384000
24 16 4 2 51555824538229409502827923200
25 16 4 2 773058043102197617863741843200
26 16 4 2 11505435580713064249590793862400
27 16 4 2 169863574496121086821681298457600
28 16 4 2 2486228772352331019060452730124800
29 16 4 2 36053699633157440642183732148192000
30 16 4 2 517650511567565591598163978874476800
31 16 4 2 7353538304042081751756339918288153600
32 16 4 2 103277843408210067510518893242552998400
33 16 4 2 1432943471827935940003777587852746035200
34 16 4 2 19624658467616639408457675812975159808000
35 16 4 2 265060115658802288611235565334010714521600
36 16 4 2 3527358829586230228770473319879741669580800
37 16 4 2 46204536626522631728453996238126656113459200
38 16 4 2 595094456544732751483475986076977832633088000
39 16 4 2 7527596027223722410480884495557694054538752000
40 16 4 2 93402951052248340658328049006200193398898022400
41 16 4 2 1135325942092947647158944525526875233118233702400
42 16 4 2 13499233156243746249781875272736634831519281254400
43 16 4 2 156762894800798673690487714464110515978059412992000
44 16 4 2 1774908625866508837753023260462716016827409668608000
45 16 4 2 19556269668280714729769444926596793510048970792448000
46 16 4 2 209250137714454234944952304185555699000268936613376000
47 16 4 2 2169234173368534856955926000562793170629056490849280000
48 16 4 2 21730999613085754709596718971411286413365188258316288000
49 16 4 2 209756078324313353775088590268126891517374425535395840000
50 16 4 2 1944321975918071063760157244341119456021429461885104128000
51 16 4 2 17242033559634684233385212588199122289377881249323872256000
52 16 4 2 145634772367323301463634877324516598329621152347129008128000
53 16 4 2 1165639372591494145461717861856832014651221024450263064576000
54 16 4 2 8786993110693628054377356115257445564685015517718871715840000
55 16 4 2 61931677369820445021334706794916410630936084274106426433536000
56 16 4 2 404473662028342481432803610109490421866960104314699801413632000
57 16 4 2 2420518371006088374060249179329765722052271121139667645435904000
58 16 4 2 13083579933158945327317577444119759305888865127012932088217600000
59 16 4 2 62671365871027968962625027691561817997506140958876900738150400000
60 16 4 2 259105543035583039429766038662433668998456660566416258886520832000
61 16 4 2 889428267668414961089138119575550372014240808053275769482575872000
62 16 4 2 2382172342138755521077314116848435721862984634708789861244239872000
63 16 4 2 4437213293644311557816587990199342976125765663655136187709235200000
64 16 4 2 4325017367677880742663367673632369189388101830634256108595793920000
65 16 4 2 0

real    0m10.924s
user    0m10.538s
sys     0m0.388s

Answer 3

Количество возможных вариантов фиксировано. Вы можете либо придумать алгоритм для генерации действительных комбинаций, либо вы можете просто перебрать все проблемное пространство и проверить каждую комбинацию с помощью простой функции, которая проверяет правильность комбинации.

Сколько времени это займет , зависит от компьютера и производительности. Вы можете легко сделать его многопоточным приложением.