Python 모든 조합 구하기

완전 탐색 문제 같은 경우 조건에 맞는 모든 순열 혹은 조합을 모두 구해서 체크

 

1. itertools 모듈 사용

 

1) 하나의 리스트에서 모든 조합 구하기

 

 

from itertools import permutations
from itertools import combinations

a = []
b = []
items = [1,2,3,4,5]

# 모든 경우의 수 1,2 != 2,1
for i in list(permutations(items, 2)):
    a.append(i)

# 뽑기만 하는 경우 1,2 = 2,1
for i in list(combinations(items, 2)):
    b.append(i)

print(a)
print(b)

 

---------

[(1, 2), (1, 3), (1, 4), (1, 5), (2, 1), (2, 3), (2, 4), (2, 5), (3, 1), (3, 2), (3, 4), (3, 5), (4, 1), (4, 2), (4, 3), (4, 5), (5, 1), (5, 2), (5, 3), (5, 4)]
[(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]

---------

 

2) 두개 이상의 리스트의 모든 조합 구하기

 

from itertools import product

items = [[1,2,3],['a','b','c'], ['!','@', '#']]
a = list(product(*items))
print(a)

b = list(product(items[0],items[1]))
print(b)

c= list(product(items[0], repeat=2))
print(c)

 

--------

[(1, 'a', '!'), (1, 'a', '@'), (1, 'a', '#'), (1, 'b', '!'), (1, 'b', '@'), (1, 'b', '#'), (1, 'c', '!'), (1, 'c', '@'), (1, 'c', '#'), (2, 'a', '!'), (2, 'a', '@'), (2, 'a', '#'), (2, 'b', '!'), (2, 'b', '@'), (2, 'b', '#'), (2, 'c', '!'), (2, 'c', '@'), (2, 'c', '#'), (3, 'a', '!'), (3, 'a', '@'), (3, 'a', '#'), (3, 'b', '!'), (3, 'b', '@'), (3, 'b', '#'), (3, 'c', '!'), (3, 'c', '@'), (3, 'c', '#')]
[(1, 'a'), (1, 'b'), (1, 'c'), (2, 'a'), (2, 'b'), (2, 'c'), (3, 'a'), (3, 'b'), (3, 'c')]
[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]

--------

 

2. 재귀함수 활용

외부 모듈 사용하지 못하는 경우 활용

 

permutation([1,2,3,4],2) = ([1] + permutation([2,3,4],1)) and
([2] + permutation([1,3,4],1)) and ([3] + permutation([1,2,4],1)) and
([4] + permutation([1,2,3],1))

 

combination([1,2,3,4],2) = ([1] + combination([2,3,4],1)) and
([2] + combination([3,4],1)) and ([3] + combination([4],1))

 

 

def perm(lst, n):
    ret = []
    if n > len(lst):
        return ret

    if n == 1:
        for i in lst:
            ret.append([i])

    elif n > 1:
        for i in range(len(lst)):
            temp = [i for i in lst]
            temp.remove(lst[i])
            for p in perm(temp, n - 1):
                ret.append([lst[i]] + p)

    return ret

def comb(lst, n):
    ret = []
    if n > len(lst):
        return ret
   
    if n == 1:
        for i in lst:
            ret.append([i])
           
    elif n > 1:
        for i in range(len(lst)-n+1):
            for temp in comb(lst[i+1:], n-1):
                ret.append([lst[i]]+temp)
               
    return ret

 

 

------------

3. DFS or BFS 활용

 

def dfs_perm(lst, n):
    ret = []
    idx = [i for i in range(len(lst))]

    stack = []
    for i in idx:
        stack.append([i])

    while len(stack) != 0:
        cur = stack.pop()

        for i in idx:
            if i not in cur:
                temp = cur + [i]
                if len(temp) == n:
                    element = []
                    for i in temp:
                        element.append(lst[i])
                    ret.append(element)
                else:
                    stack.append(temp)
    return ret

def dfs_comb(lst, n):
    ret = []
    idx = [i for i in range(len(lst))]

    stack = []
    for i in idx[:len(lst) - n + 1]:
        stack.append([i])

    while len(stack) != 0:
        cur = stack.pop()

        for i in range(cur[-1] + 1, len(lst) - n + 1 + len(cur)):
            temp = cur + [i]
            if len(temp) == n:
                element = []
                for i in temp:
                    element.append(lst[i])
                ret.append(element)
            else:
                stack.append(temp)
    return ret

 

* 중복 순열, 조합 같은 경우 위의 과정에서 중복된 원소 빼주는 과정만 추가해주면 구현 가능