d014 패스워드 테스트를 위한, 중복문자를 허용하는 Partial Permutation 구하기

Permutation쓸 일이 없던데요

Permutation은 가끔 유닛테스트할 때 사용해야할 경우가 발생합니다. 예를 들면, 패스워드에서 사용할 수 있는 문자가 다음과 같습니다.

$available_chars = "abcdefghijklmn`.\!@#$%^&*()_+|"

하지만 추가적인 제약이 있어서, 사용할 수 있는 문자의 수는 8자 이상, 12자까지라는 제약이 있습니다.

기획하는 분들로 부터 이런 주문이 오면, 리드 엔지니어는 다음과 같은 선택을 할 수 있습니다.

신뢰하는 다른 엔지니어에게 테스트에 대해 아무런 언급도 하지 않고 맡긴다. 유닛테스트를 하건 안하건 에러없으면 역시 나의 판단이 옳았음. 나는 그를 믿었는데 에러나면 그가 나의 신뢰를 져버린 것임. 럴수 럴수 이럴수가. 나는 Innocent한 피해자. ㅎ
개발하기에도 시간이 없으니 유닛테스트 작성 없이 몇 번 테스트해보고 이상이 없는 것 같으면 커밋. 결합테스트에서 에러가 발견되면 고친다. Production에서 에러가 나면, QA가 잘못한 것임. (feat. QA가 왜 있는데?)
그래도 유닛테스트는 해야지. 유닛테스트 안하는 엔지니어는 엔지니어도 아님. $available_chars 에서 Random으로 8~12 자의 문자열을 만들어서 테스트하게 한다.
랜덤으로 하면 완벽하게 테스트 할 수 없잖아. Escape처리가 잘 안되는 경우가 테스트에서 빠지면 어떻게 하지? Permutation을 이용해서 모든 경우를 테스트하자. 단 #long 태그를 붙여둘까? (그런데 맡길 사람이 없네?)

…

리드엔지니어의 역할에 대한 포스트는 나중에 다시 언급할 기회가 있을 거라고 생각합니다.

각설하고, 원래 Permutation에 대한 기본적인 접근방법을 살펴보면,

Hacky Way

ruby나 scala, groovy처럼 준비되어 있는 permutation 함수를 직접 쓸 수 있는 경우도 있습니다.

ruby

1
"abcde".chars.permutation

scala

1
List(1, 2, 3).permutations.foreach(println)

groovy

1
def makePermutations = { l -> l.permutations() }

또, python이라면 itertools.permutations를 사용할 수도 있고,

python

1
2
3
import itertools
for values in itertools.permutations([1,2,3]):
    print (values)

csharp이라면 Lambda와 Recursive Linq를 사용할 수도 있고,

csharp

1
2
3
4
5
6
public static IEnumerable<IEnumerable<T>> Permutations<T>(this IEnumerable<T> values)
{
     if (values.Count() == 1)
         return new [] {values};
     return values.SelectMany(v => Permutations(values.Where(x=> x != v)),(v, p) => p.Prepend(v));    
}

Powershell은 이러한 함수가 없습니다. 힘들게 로직을 통해서 구해야합니다.

Permutation을 살펴보면

Permutation의 구현은 이미 선구자들이 여러가지 알고리즘을 구현해 두었는데, 위키디아의 https://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations 를 보면

Lexicographic ordering;
Steinhaus–Johnson–Trotter algorithm
Heap’s algorithm
Ehrlich’s star-transposition algorithm, Knuth의 책 The Art of Computer Programming에 나온다고 합니다.
Zaks’ prefix reversal algorithm
Sawada-Williams’ algorithm
Corbett’s algorithm
Single-track ordering
Single-track Gray code

등이 있다고 소개하고 있습니다.
각각의 구해지는 순서는 다음과 같다고 합니다.

이 솔루션의 Permutation은 배열을 나누고, 더하고, 요소를 앞에 붙이고 하는 것이 핵심입니다. 그래서 기본 패키지에 배열 처리 기능이 많이 내장되어 있는 python이 이런 문제에 접근하기 좋습니다.

또 Swap을 이를 요소의 삽입으로 접근하는 방법도 있고, 치환으로 접근하는 방법도 있을 수 있습니다.

Python 솔루션

1번 Lexicographic ordering 알고리즘을 Python으로 구하면, 이런 느낌입니다.

1
2
3
4
5
6
7
8
9
def permutations(items):
    if len(items) == 1:
        yield items
    for x, xitem in enumerate(items):
        for yitems in permutations(items[:x] + items[x+1:]):
            yield [xitem] + yitems

numbers = [1, 2, 3, 4]
print(list(permutations(numbers)))

여기에서는 swap을 사용하지 않고, 새 array를 구하여 사용하였습니다.

재귀함수의 파라메터에 인덱스나, 결과값을 저장하는 컨테이너도 넣지 않고 처리가 깔끔하게 됩니다. 이것은 Python이니까 가능한 것입니다.

결과

C:\Users\Administrator>python
Python 3.7.4 (default, Aug  9 2019, 18:34:13) [MSC v.1915 64 bit (AMD64)] :: Anaconda, Inc. on win32

Warning:
This Python interpreter is in a conda environment, but the environment has
not been activated.  Libraries may fail to load.  To activate this environment
please see https://conda.io/activation

Type "help", "copyright", "credits" or "license" for more information.
>>> def permutations(items):
...     if len(items) == 1:
...         yield items
...     for x, xitem in enumerate(items):
...         for yitems in permutations(items[:x] + items[x+1:]):
...             yield [xitem] + yitems
...
>>> numbers = [1, 2, 3, 4]
>>> print(list(permutations(numbers)))
[[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 2, 3], [1, 4, 3, 2], [2, 1, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1], [3, 1, 2, 4], [3, 1, 4, 2], [3, 2, 1, 4], [3, 2, 4, 1], [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]]
>>>

Python으로는 이것이 가능하지만, 대부분의 다른 언어로는

글로벌한 곳에 index와 결과값을 저장하는 컨테이너를 선언하거나,
포인터로 파라메터로 함께 끌고 다니는 것
이 일반적입니다.

다행히도 Powershell은 function안에 function을 정의하는 것이 가능하므로, 이런 식의 구성이 가능합니다.

Powershell이라면

다음은 인터넷에서 구한 3번 Heap’s algorithm 솔루션입니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Function Get-Permutations ($array) {
    Function Generate($n, $array, $A) {
        if($n -eq 1) {
            $array[$A] -join ' '
        }
        else{
            for( $i = 0; $i -lt ($n - 1); $i++) {
                Generate ($n - 1) $array $A
                if($n % 2 -eq 0){
                    $i1, $i2 = $i, ($n-1)
                    $A[$i1], $A[$i2] = $A[$i2], $A[$i1]
                }
                else{
                    $i1, $i2 = 0, ($n-1)
                    $A[$i1], $A[$i2] = $A[$i2], $A[$i1]
                }
            }
            Generate ($n - 1) $array $A
        }
    }
    $n = $array.Count
    if($n -gt 0) {
        (Generate $n $array (0..($n-1)))
    } else {$array}
}

$available_chars = "abcdefghijklmn`.\!@#$%^&*()_+|"
$available_chars = "abcde"
$arr = $available_chars.ToCharArray()
Get-Permutations $numbers

Unique Combination

컴비네이션은 또 다른 문제입니다. 반복을 허용하는 경우와 반복을 허용하지 않는 경우가 있는데, 처음에 든 패스워드 문제는 반복을 하용할 수 있습니다.

부분조합도 허용하고, 반복문자를 허용하지 않는 경우의 Combination은 다음과 같이 구합니다.

Powershell이라면

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Function Get-Combinations{
    Param(
        $theInput
    )
    $theInput | ForEach-Object{

        $element = $_
        $sansElement = ($theInput | Where-Object{$_ -ne $element})

        If($sansElement.Count -gt 1){
            # Build a collection of permutations using the remaining elements that were not isolated in this pass.
            # Use the single element since it is a valid permutation 
            $perms = ,$element
            For($elementIndex = 0;$elementIndex -le ($sansElement.Count - 1);$elementIndex++){
              $perms += ,@(,$element + $sansElement[0..$elementIndex] | sort-object)
            }

            # For loop does not send to output properly so that is the purpose of collecting the results of this pass in $perms
            $perms

            # If there are more than 2 elements in $sansElement then we need to be sure they are accounted for 
            If($sansElement -gt 2){Get-Permutations $sansElement}
        } 

    }
}

Get-Combinations B,C,D,E | %{$_ -join ","} | Sort-Object -Unique

그래서 Python이라면?

이건 어떨까요?

1
2
3
4
5
6
7
from itertools import product
 
available_chars = "abcdefghijklmn`.\!@#$%^&*()_+|"
for i in range(8, 13):
    for x in product(available_chars, repeat=i):
        w = ''.join(x)
        print( w )

이 경우 가능한 경우의 수는 어떻게 될까요?

전부 다 테스트 하려면 긴 시간이 걸립니다. 각오하셔야 합니다.

기타

ruby라면 더 간단히 되는 군요.

1
2
3
4
5
rp = [1,2,3].repeated_permutation(2) # an enumerator (generator)
p rp.to_a #=>[[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]]
 
#yield permutations until their sum happens to exceed 4, then quit:
p rp.take_while{|(a, b)| a + b < 5}  #=>[[1, 1], [1, 2], [1, 3], [2, 1], [2, 2]]