주어진 제약 조건을 가진 가능한 암호의 수입니다.

Question

이 작업을 시작하기위한 아이디어가 필요합니다. 나는 숫자 0 사용 가능한 모든 암호의 수를 계산 C에서 프로그램 작성 해요 - 같은 다른 주어진 제약 조건과 함께 9 :

이

1) 왼쪽 자리는 맨 오른쪽 자리 같을 수 없습니다를

2) 아니오 두 자리 (123,242 유효하지 않은)

3)과 동일한 값 없음의 연속 디지트 (1,221 잘못)

4)

최소 길이 4 자리수 (PW)에 회 이상 나타날 수 없다

, 사용자는 명령 행 인수를 통해 암호의 길이와 숫자를 사용할 수없는 선택적 인수를 입력합니다.

그렇게하기위한 최선의 방법은 무엇입니까? 내 생각은 제약없이 모든 가능한 가능성의 큰 세트를 만들고 세트 내에서 제약 조건과 충돌하는 모든 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와 함께 또는 MPI와 함께 사용하는 것이 하나 더 팁입니다.

Answer 2

짐승 같은 힘으로는 계산할 수없는 큰 세트는 아닙니다. 모든 가능성을 검사 할 필요는 없으며 단지 '증가하는'자릿수의 암호 만 확인하십시오. 숫자 d은 d-1 숫자가 j<i 인 경우 i 위치에 올 수없는 비밀번호를 의미합니다. 길이 당 유효 자릿수 증가 암호 :

• 1 : 0,
• 2 : 01
• 3 : 010, 012,
• 4 : 0101, 0102, 0120, 0121, 0123.하나 증가 자리 암호 가입일

는 n 가능한 자리수이고, nPk 다른 암호를 생성 할 수 있고, k는 자리의 비밀번호를 증가 시키는데 사용 자릿수이다.

다음은이 접근 방식의 파이썬 구현입니다.

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