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

Question

Мне просто нужно несколько идей, чтобы начать с этого. Я написать программу в C, которая подсчитывает количество всех возможных паролей с помощью цифр 0 - 9 наряду с некоторыми другими данными ограничениями, такими как:

1) крайняя левая цифра не может быть такой же, как крайний правый разряд

2) Никакие две цифры не может появляться более чем в два раза в PW (123242 не действует)

3) нет последовательных цифр одного и того же значения (1221 не действует)

4) 4 цифры в длину минимальной

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

Каков наилучший подход к этому? Моя идея состояла в том, чтобы просто создать большой набор всех возможностей без ограничений и начать поиск в наборе для любого pw, который конфликтует с любым из этих запретов, удаляя их. После этого я подсчитываю элементы внутри набора. Я не знаю, насколько это эффективно.

Мой другой вопрос: для меня это совсем другое, чтобы создать это как программу mpi, а не просто последовательную программу.

Answer 1

Обычно для таких задач работает динамическое программирование. Хотя вы не указали специфику, поэтому неясно, будет ли DP работать и в вашем случае. В сущности, DP разрабатывает функцию и вычисляет ее значения с помощью запоминания. Функция будет выглядеть как F(n,d)=F(n-1,d1)+...+F(n-1,dK) или более сложная (больше переменных) в зависимости от вашей задачи. Здесь n - это текущая длина пароля, d - последняя цифра, а d1...dK - это предыдущие разряды.

Я дал несколько советов для вас:

1. Динамическое программирование
2. Запоминание
3. Глядя на последнюю цифру и возможные предшествующие цифры

Вы можете учиться больше на Wikipedia или более удобные для читателей учебники (TopCoder?)

EDIT: еще один совет - использовать GPGPU - CUDA или OpenCL - вместе с MPI или вместо него.

Answer 2

Это не такой большой набор, который нельзя считать грубой силой. Обратите внимание, что нет необходимости проверять все возможности, просто пароли с «увеличивающимися» цифрами. Это означает пароли, где цифра d не может быть в позиции i, если цифра d-1 не находится на некотором положении j<i. Допустимые увеличение цифры паролей в длину:

• 1: 0,
• 2: 01,
• 3: 010, 012,
• 4: 0101, 0102, 0120, 0121, 0123.

С одной увеличивающихся символьного пароля можно создать nPk различные пароли, где n это число возможных цифр, и k является количеством используемых цифр в увеличении значного пароля.

Вот реализация этого подхода на основе python.

import math 
import time 

_ps = {} 
def _P(n, k): 
    if (n, k) not in _ps: 
     _ps[(n, k)] = math.factorial(n) // math.factorial(n-k) 
    return _ps[(n, k)] 

def _cc(length, last_digit, largest_digit, digits_left, counts, max_digit, max_length): 
    counts[length] += _P(max_digit+1, largest_digit+1) 
    if length < max_length: 
     for d in xrange(largest_digit+1):    # Check digits 0-largest_digit 
      if d != last_digit and digits_left[d] > 0: 
       digits_left[d] -= 1 
       _cc(length+1, d, largest_digit, digits_left, counts, max_digit, max_length) 
       digits_left[d] += 1 
     if largest_digit < max_digit: 
      largest_digit += 1 
      digits_left[largest_digit] -= 1 
      _cc(length+1, largest_digit, largest_digit, digits_left, counts, max_digit, max_length) 
      digits_left[largest_digit] += 1 

def count_combs(max_digit, max_length, min_length=4): 
    time1 = time.time() 
    digits_left = [1] + [2] * max_digit # Max 2 same digits to use 
    counts = [0] * (max_length + 1) 
    _cc(1, 0, 0, digits_left, counts, max_digit, max_length) 
    s = 0 
    for d, count in enumerate(counts[min_length:]): 
     print d+min_length, count 
     s += count 
    print 'Sum', s 
    print 'Time: %0.3f ms' % ((time.time()-time1)*1000.0,) 

if __name__ == '__main__': 
    import sys 
    count_combs(int(sys.argv[1]), int(sys.argv[2])) 

Для крупного случая он работает ~ 11мин на моем ноутбуке. C будет намного быстрее. Использование является:

python <script> <max_digit> <max_password_length> 
python <script> 6 20 
python <script> 9 20 # The largest example 

Результат крупнейшего случае:

4 7290 
5 64800 
6 563040 
7 4742640 
8 38435040 
9 297410400 
10 2179668960 
11 14994201600 
12 95817708000 
13 561778761600 
14 2975712163200 
15 13959599875200 
16 56450035555200 
17 189212904115200 
18 494001259315200 
19 896042510496000 
20 851371260364800 
Sum 2504688393448170 
Time: 648185.829 ms