[컴][알고리즘] Backtracking

백트래킹 / 조합 / 순열 / combination / 알고리즘 /recursive / python

backtracking

Permutation

순열의 성질중 아래 같은 성질을 이용해서 코딩을 한다.

아래 성질을 말로 풀면, (n-1)개에 대한 조합들이 있고, 그 조합에서 1개를 그 사이에 집어넣을 수 있는데, 그 경우의 수가 n 개이다. 


def perms(elements):
    if len(elements) ==1:
        # yield elements
        return [elements]
    else:
        ret = []
        for perm in perms(elements[1:]):
            for i in range(len(elements)):
                # 한개를 정하고, 그 한개 이외의 값들을 permutation 을 하고, 
                # 그 한개의 위치만 바꾼다.

                # nb elements[0:1] works in both string and list contexts
                # yield perm[:i] + elements[0:1] + perm[i:]
                ret.append(perm[:i] + elements[0:1] + perm[i:])
        return perm

perms([1,2,3])

return of perms() perm elements i elements[0:1] perm[:i] + elements[0:1] + perm[i:]
[[3]] [3] [2,3] 0 [2] [2,3]
[[3]] [3] [2,3] 1 [2] [3,2]
[[2, 3], [3, 2]] [2,3] [1,2,3] 0 [1] [1,2,3]
[[2, 3], [3, 2]] [2,3] [1,2,3] 1 [1] [2,1,3]
[[2, 3], [3, 2]] [2,3] [1,2,3] 2 [1] [2,3,1]
[[2, 3], [3, 2]] [3,2] [1,2,3] 0 [1] [1,3,2]
[[2, 3], [3, 2]] [3,2] [1,2,3] 1 [1] [3,1,2]
[[2, 3], [3, 2]] [3,2] [1,2,3] 2 [1] [3,2,1]

Combinations

순착적으로만 선택하면 된다.

먼저 조합(combination)의 성질을 조금 알 필요가 있다. combination은 1,3 / 3,1 을 같은 선택으로 본다. 그렇기 때문에 만약 다음처럼 elements 가 있다고 한다면,
elements = [1,2,3]
우리가 앞에서 부터 순차적으로 선택한다면, 마지막 element 인 3을 선택한 이후에, 그 이전 element 를 선택할 필요가 없다. 즉, 1,3 을 선택했다면, 그 다음 2 를 선택해서, 1,3,2 를 선택할 필요가 없다. 왜냐하면, 이것은 1,2,3 에서 이미 만들어진 조합이기 때문이다.

여기서 명심할 것은 다음에 나오는 코드의 주 내용은 가능한 모든 combination 을 찾아주는 방법이지, combination 이 몇개인지를 나타내는 것이 아니다.

recursive version

nCr
ans = []
def backtracking(path, elements, r):
    if r == 0:
        ans.append(list(path)) # copy is needed
        return

    for index, num in enumerate(elements):
        path.append(num) # choose, 선택
        backtracking(path, elements[index + 1:], r - 1)
        path.pop()       # unchoose, 선택해제


backtracking([], [1,2,3], 2)


combinations_with_replacement

ref. 2에 combination python source 가 있다.

`i` 가 현재보고 있는 '자리'가 된다.
각 '자리'에 index 를 써놓는다.
가장 뒷 '자리' 부터 거꾸로 보는데,
그 '자리' 에 있는 index 가 마지막 index가 될 때까지, 보고있는 '자리'를 옮기지 않는다.
마지막 index 가 되면, 보고있는 '자리'를 한자리 앞으로 옮긴다.


'자리' 변경시
현재 보고 있는 '자리' 부터 뒷자리를, 현재 보고있는 '자리'의 index 값보다 +1 한 index 값으로 채운다.
1,1
1,2
1,3
2,1 ==> 1,2와 같다
2,2
2,3
이렇게 순서대로 가야 하는데, 이것은 조합(combination) 이라서 1,2 == 2,1 이 같다. 그래서 새로운 '자리'에 값을 증가 시킬때는 이미 지나온 '자리'에는 새로운 '자리'의 값보다 작은 값을 넣을 필요가 없다.

그래서 아래같은 code 를 사용한다.
indices[i:] = [indices[i] + 1] * (r - i)

def combinations_with_replacement(iterable, r):
    # combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC
    pool = tuple(iterable)
    n = len(pool)
    if not n and r:
        return
    ret = []
    indices = [0] * r
    # yield tuple(pool[i] for i in indices)
    ret.append(tuple(pool[i] for i in indices))
    while True:
        for i in reversed(range(r)):
            if indices[i] != n - 1:
                break
        else:
            return
        indices[i:] = [indices[i] + 1] * (r - i)
        # yield tuple(pool[i] for i in indices)
        ret.append(tuple(pool[i] for i in indices))

combinations_with_replacement([4,5,6,7], 3)

indices

indices r i r-i indices[i] n-1 indices[i:] [indices[i] + 1] * (r - i) return
[0, 0, 0] 3 i=2 1 0 3 [0] [1] [(4, 4, 4)]
[0, 0, 1] 3 i=2 1 1 3 [1] [2] [(4, 4, 4), (4, 4, 5)]
[0, 0, 2] 3 i=2 1 2 3 [2] [3] [(4, 4, 4), (4, 4, 5), (4, 4, 6)]
[0, 0, 3] 3 i=1 2 0 3 [0, 3] [1, 1] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7)]
[0, 1, 1] 3 i=2 1 1 3 [1] [2] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5)]
[0, 1, 2] 3 i=2 1 2 3 [2] [3] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6)]
[0, 1, 3] 3 i=1 2 1 3 [1, 3] [2, 2] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6), (4, 5, 7)]
[0, 2, 2] 3 i=2 1 2 3 [2] [3] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6), (4, 5, 7), (4, 6, 6)]
[0, 2, 3] 3 i=1 2 2 3 [2, 3] [3, 3] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6), (4, 5, 7), (4, 6, 6), (4, 6, 7)]
[0, 3, 3] 3 i=0 3 0 3 [0, 3, 3] [1, 1, 1] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6), (4, 5, 7), (4, 6, 6), (4, 6, 7), (4, 7, 7)]
[1, 1, 1] 3 i=2 1 1 3 [1] [2] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6), (4, 5, 7), (4, 6, 6), (4, 6, 7), (4, 7, 7), (5, 5, 5)]
[1, 1, 2] 3 i=2 1 2 3 [2] [3] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6), (4, 5, 7), (4, 6, 6), (4, 6, 7), (4, 7, 7), (5, 5, 5), (5, 5, 6)]
[1, 1, 3] 3 i=1 2 1 3 [1, 3] [2, 2] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6), (4, 5, 7), (4, 6, 6), (4, 6, 7), (4, 7, 7), (5, 5, 5), (5, 5, 6), (5, 5, 7)]
[1, 2, 2] 3 i=2 1 2 3 [2] [3] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6), (4, 5, 7), (4, 6, 6), (4, 6, 7), (4, 7, 7), (5, 5, 5), (5, 5, 6), (5, 5, 7), (5, 6, 6)]
[1, 2, 3] 3 i=1 2 2 3 [2, 3] [3, 3] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6), (4, 5, 7), (4, 6, 6), (4, 6, 7), (4, 7, 7), (5, 5, 5), (5, 5, 6), (5, 5, 7), (5, 6, 6), (5, 6, 7)]
[1, 3, 3] 3 i=0 3 1 3 [1, 3, 3] [2, 2, 2] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6), (4, 5, 7), (4, 6, 6), (4, 6, 7), (4, 7, 7), (5, 5, 5), (5, 5, 6), (5, 5, 7), (5, 6, 6), (5, 6, 7), (5, 7, 7)]
[2, 2, 2] 3 i=2 1 2 3 [2] [3] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6), (4, 5, 7), (4, 6, 6), (4, 6, 7), (4, 7, 7), (5, 5, 5), (5, 5, 6), (5, 5, 7), (5, 6, 6), (5, 6, 7), (5, 7, 7), (6, 6, 6)]
[2, 2, 3] 3 i=1 2 2 3 [2, 3] [3, 3] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6), (4, 5, 7), (4, 6, 6), (4, 6, 7), (4, 7, 7), (5, 5, 5), (5, 5, 6), (5, 5, 7), (5, 6, 6), (5, 6, 7), (5, 7, 7), (6, 6, 6), (6, 6, 7)]
[2, 3, 3] 3 i=0 3 2 3 [2, 3, 3] [3, 3, 3] [(4, 4, 4), (4, 4, 5), (4, 4, 6), (4, 4, 7), (4, 5, 5), (4, 5, 6), (4, 5, 7), (4, 6, 6), (4, 6, 7), (4, 7, 7), (5, 5, 5), (5, 5, 6), (5, 5, 7), (5, 6, 6), (5, 6, 7), (5, 7, 7), (6, 6, 6), (6, 6, 7), (6, 7, 7)]

See Also

Reference

  1. `python - How to generate all permutations of a list? - Stack Overflow
  2. itertools — Functions creating iterators for efficient looping — Python 3.8.3 documentation  
  3. https://makefortune2.tistory.com/227
  4. Combinations and Permutations with an Intro to Backtracking 
by koosal on
Tags: ,

댓글 없음:

댓글 쓰기

피드 구독하기: 댓글 (Atom)