Python: product, permutations

https://docs.python.org/ko/3/library/itertools.html

itertools — Functions creating iterators for efficient looping

 

Product (생산, 과정에 의한 산물)

itertools.product(*iterables, repeat=1)

입력 이터러블들(iterables)의 데카르트 곱. 대략 제너레이터 표현식에서의 중첩된 for-루프와 동등합니다. 예를 들어, product(A, B)는 ((x,y) for x in A for y in B)와 같은 것을 반환합니다. 중첩된 루프는 매 이터레이션마다 가장 오른쪽 요소가 진행되는 주행 거리계처럼 순환합니다. 이 패턴은 사전식 순서를 만들어서 입력의 이터러블들이 정렬되어 있다면, 곱(product) 튜플이 정렬된 순서로 방출됩니다. 이터러블의 자신과의 곱을 계산하려면, 선택적 repeat 키워드 인자를 사용하여 반복 횟수를 지정하십시오. 예를 들어, product(A, repeat=4)는 product(A, A, A, A)와 같은 것을 뜻합니다. 이 함수는 실제 구현이 메모리에 중간 결과를 쌓지 않는다는 점을 제외하고

다음 코드와 대략 동등합니다:

def product(*args, repeat=1):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = [tuple(pool) for pool in args] * repeat
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

[product()](<https://docs.python.org/ko/3/library/itertools.html#itertools.product>)가 실행되기 전에, 입력 이터러블을 완전히 소비하여, 곱을 생성하기 위해 값의 풀(pool)을 메모리에 유지합니다. 따라서, 유한 입력에만 유용합니다.

알고리즘 문제: 타겟 넘버

"""
문제 설명
n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 
예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 
타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항
주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
각 숫자는 1 이상 50 이하인 자연수입니다.
타겟 넘버는 1 이상 1000 이하인 자연수입니다.

"""

from itertools import product

def solution(numbers, target):
    def dfs(index, total):
        if index == len(numbers):
            if total == target:
                return 1
            return 0
        return dfs(index + 1, total + numbers[index]) + dfs(
            index + 1, total - numbers[index]
        )

    return dfs(0, 0)

numbers = [1, 1, 1, 1, 1]
target = 3
print(solution(numbers, target))  # 출력: 5

def solution3(numbers, target):
    l = [(x, -x) for x in numbers]
    print(l)  # [(1, -1), (2, -2), (3, -3), (4, -4), (5, -5)]
    s = list(map(sum, product(*l)))  # *l -> 튜플 언팩킹
    print(s)
    # [15, 5, 7, -3, 9, -1, 1, -9, 11, 1, 3, -7, 5, -5, -3, -13, 13, 3, 5, -5, 7, -3, -1, -11, 9, -1, 1, -9, 3, -7, -5, -15]
    return s.count(target)  # s 안에서 target 과 같은 숫자를 가진 인자를 카운트

numbers = [1, 2, 3, 4, 5]
target = 3
print(solution3(numbers, target))  # 출력: 4

알고리즘문제: 모음사전

"""
문제 설명
사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는,
길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 
그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.

단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 
return 하도록 solution 함수를 완성해주세요.

제한사항
word의 길이는 1 이상 5 이하입니다.
word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.
입출력 예
word	result
"AAAAE"	6
"AAAE"	10
"I"	1563
"EIO"	1189
입출력 예 설명
입출력 예 #1

사전에서 첫 번째 단어는 "A"이고, 
그 다음은 "AA", "AAA", "AAAA", "AAAAA", "AAAAE", ... 와 같습니다.
"AAAAE"는 사전에서 6번째 단어입니다.

입출력 예 #2

"AAAE"는 "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAE", "AAAAI", "AAAAO", "AAAAU"의 다음인 10번째 단어입니다.

입출력 예 #3

"I"는 1563번째 단어입니다.

입출력 예 #4

"EIO"는 1189번째 단어입니다.
"""

from itertools import product

def solution(word):
    answer = 0

    total_dict = []
    for i in range(1, 6):
        dictionary = list(map("".join, product(["A", "E", "I", "O", "U"], repeat=i)))
        # 모든 경우의 수를 구해서
        total_dict.extend(dictionary)
        # total_dict 에 합쳐둔다

    total_dict.sort()
    # 한번씩써서 돌린 것부터 5번씩 써서 돌린 것 까지 합친 걸 사전 배열로 정리
    # total_dict ['A', 'E', 'I', 'O', 'U', 'AA', 'AE', 'AI', 'AO', 'AU' .... 'UUUUI', 'UUUUO', 'UUUUU']
    for i in range(len(total_dict)):
        if total_dict[i] == word:
            answer = i + 1
            # 그 중 값이 일치하는 인덱스에 1을 더해서 출력
    return answer

print(solution("AAAAE"))  # 6

print(solution("AAAE"))  # 10

print(solution("I"))  # 1563

 

 

Permutations (순열, 치환)

서로 다른 n 개의 원소에서 r 개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것

itertools.permutations(iterable, r=None)

itertools.permutations(iterable, r)

iterable에서 요소의 연속된 길이 r 순열을 반환합니다. r이 지정되지 않았거나 None이면, r의 기본값은 iterable의 길이이며 가능한 모든 최대 길이 순열이 생성됩니다. The permutation tuples are emitted in lexicographic order according to the order of the input iterable. So, if the input iterable is sorted, the output tuples will be produced in sorted order. Elements are treated as unique based on their position, not on their value. So if the input elements are unique, there will be no repeated values within a permutation. 대략 다음과 동등합니다:

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

import itertools

# 리스트 [1, 2, 3]에 대한 순열을 생성합니다.
result = list(itertools.permutations([1, 2, 3]))
print(result)
# 출력: [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]