prosource

여러 목록의 데카르트 곱을 가져오는 방법

probook 2023. 4. 28. 21:07
반응형

여러 목록의 데카르트 곱을 가져오는 방법

목록 그룹에서 데카르트 곱(가능한 모든 값 조합)을 가져오려면 어떻게 해야 합니까?

예를 들어, 주어진

somelists = [
   [1, 2, 3],
   ['a', 'b'],
   [4, 5]
]

이거 어떻게 받아요?

[(1, 'a', 4), (1, 'a', 5), (1, 'b', 4), (1, 'b', 5), (2, 'a', 4), (2, 'a', 5), ...]

이 기법의 일반적인 응용 프로그램 중 하나는 깊게 중첩된 루프를 피하는 것입니다.더 구체적인 복제에 대한 루프의 중첩 방지를 참조하십시오.마찬가지로 이 기법은 목록 값을 가진 사전을 "탐색"하는 데 사용될 수 있습니다. Python Dictionary 순열을 사전 목록에 결합을 참조하십시오.

만약 당신이 같은 목록의 데카르트 제품을 여러 번 원한다면,itertools.product우아하게 처리할 수 있습니다.목록의 모든 요소 쌍에 대한 작업 또는 목록에서 "반복이 있는 순열"을 가져오는 방법을 참조하십시오(목록 자체의 데카르트 곱).

에 알고 있는 많은 이 있습니다.itertools.product예를 들어 목록 목록이 아닌 각 입력 시퀀스에 대해 별도의 인수를 기대한다는 사실로 인해 어려움을 겪습니다.승인된 답변은 이 문제를 처리하는 방법을 보여줍니다.* 그나사, 은용의의 *여기서 인수를 풀면 함수 호출에 사용되는 다른 시간과 근본적으로 다르지 않습니다.이 항목에 대한 인수로 튜플 확장을 참조하십시오(해당하는 경우 중복 질문을 닫는 데 사용).

Python 2.6부터 사용할 수 있습니다.

import itertools

somelists = [
   [1, 2, 3],
   ['a', 'b'],
   [4, 5]
]
for element in itertools.product(*somelists):
    print(element)

이는 다음과 같습니다.

for element in itertools.product([1, 2, 3], ['a', 'b'], [4, 5]):
    print(element)

import itertools
>>> for i in itertools.product([1,2,3],['a','b'],[4,5]):
...         print i
...
(1, 'a', 4)
(1, 'a', 5)
(1, 'b', 4)
(1, 'b', 5)
(2, 'a', 4)
(2, 'a', 5)
(2, 'b', 4)
(2, 'b', 5)
(3, 'a', 4)
(3, 'a', 5)
(3, 'b', 4)
(3, 'b', 5)
>>>

Python 2.5 이상 버전의 경우:

>>> [(a, b, c) for a in [1,2,3] for b in ['a','b'] for c in [4,5]]
[(1, 'a', 4), (1, 'a', 5), (1, 'b', 4), (1, 'b', 5), (2, 'a', 4), 
 (2, 'a', 5), (2, 'b', 4), (2, 'b', 5), (3, 'a', 4), (3, 'a', 5), 
 (3, 'b', 4), (3, 'b', 5)]

▁of다▁의 재귀 버전입니다.product()일 뿐그림일 뿐입니다):

def product(*args):
    if not args:
        return iter(((),)) # yield tuple()
    return (items + (item,) 
            for items in product(*args[:-1]) for item in args[-1])

예:

>>> list(product([1,2,3], ['a','b'], [4,5])) 
[(1, 'a', 4), (1, 'a', 5), (1, 'b', 4), (1, 'b', 5), (2, 'a', 4), 
 (2, 'a', 5), (2, 'b', 4), (2, 'b', 5), (3, 'a', 4), (3, 'a', 5), 
 (3, 'b', 4), (3, 'b', 5)]
>>> list(product([1,2,3]))
[(1,), (2,), (3,)]
>>> list(product([]))
[]
>>> list(product())
[()]

저는 목록 이해력을 사용할 것입니다.

somelists = [
   [1, 2, 3],
   ['a', 'b'],
   [4, 5]
]

cart_prod = [(a,b,c) for a in somelists[0] for b in somelists[1] for c in somelists[2]]

iter tools.product 사용 시:

import itertools
result = list(itertools.product(*somelists))

다음은 임시 목록을 저장하지 않는 재귀 생성기입니다.

def product(ar_list):
    if not ar_list:
        yield ()
    else:
        for a in ar_list[0]:
            for prod in product(ar_list[1:]):
                yield (a,)+prod

print list(product([[1,2],[3,4],[5,6]]))

출력:

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

Python 2.6 이상에서는 'itertools.product'를 사용할 수 있습니다.이전 버전의 Python에서는 최소한 시작점으로 설명서의 다음 코드(거의 -- 설명서 참조)를 사용할 수 있습니다.

def product(*args, **kwds):
    # 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 = map(tuple, args) * kwds.get('repeat', 1)
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

두 가지 결과 모두 반복기이므로 추가 처리를 위해 목록이 필요한 경우 다음을 사용합니다.list(result).

이미 많은 답변이 있지만, 저는 다음과 같은 몇 가지 생각을 공유하고 싶습니다.

반복 접근법

def cartesian_iterative(pools):
  result = [[]]
  for pool in pools:
    result = [x+[y] for x in result for y in pool]
  return result

재귀적 접근법

def cartesian_recursive(pools):
  if len(pools) > 2:
    pools[0] = product(pools[0], pools[1])
    del pools[1]
    return cartesian_recursive(pools)
  else:
    pools[0] = product(pools[0], pools[1])
    del pools[1]
    return pools
def product(x, y):
  return [xx + [yy] if isinstance(xx, list) else [xx] + [yy] for xx in x for yy in y]

람다 접근법

def cartesian_reduct(pools):
  return reduce(lambda x,y: product(x,y) , pools)

재귀적 접근 방식:

def rec_cart(start, array, partial, results):
  if len(partial) == len(array):
    results.append(partial)
    return 

  for element in array[start]:
    rec_cart(start+1, array, partial+[element], results)

rec_res = []
some_lists = [[1, 2, 3], ['a', 'b'], [4, 5]]  
rec_cart(0, some_lists, [], rec_res)
print(rec_res)

반복적인 접근 방식:

def itr_cart(array):
  results = [[]]
  for i in range(len(array)):
    temp = []
    for res in results:
      for element in array[i]:
        temp.append(res+[element])
    results = temp

  return results

some_lists = [[1, 2, 3], ['a', 'b'], [4, 5]]  
itr_res = itr_cart(some_lists)
print(itr_res)

변수 맛에서 위의 재귀 생성기 솔루션에 대한 약간의 수정:

def product_args(*args):
    if args:
        for a in args[0]:
            for prod in product_args(*args[1:]) if args[1:] else ((),):
                yield (a,) + prod

물론 이 솔루션과 정확히 동일하게 작동하는 포장지입니다.

def product2(ar_list):
    """
    >>> list(product(()))
    [()]
    >>> list(product2(()))
    []
    """
    return product_args(*ar_list)

한 번의 트레이드오프: 각 외부 루프에서 재귀가 발생해야 하는지 여부를 확인하고, 한 번의 이득: 빈 호출에 대한 수익이 없습니다.product(())의미론적으로 더 정확할 것 같습니다(의사 테스트 참조).

리스트 이해와 관련하여: 수학적 정의는 임의의 수의 인수에 적용되는 반면 리스트 이해는 알려진 수의 인수만 처리할 수 있습니다.

목록 이해는 간단하고 깨끗합니다.

import itertools

somelists = [
   [1, 2, 3],
   ['a', 'b'],
   [4, 5]
]
lst = [i for i in itertools.product(*somelists)]

이미 말한 것에 조금 더 덧붙이자면, 만약 당신이 SymPy를 사용한다면, 당신은 그것들을 수학적으로 유용하게 만드는 문자열 대신에 기호를 사용할 수 있습니다.

import itertools
import sympy

x, y = sympy.symbols('x y')

somelist = [[x,y], [1,2,3], [4,5]]
somelist2 = [[1,2], [1,2,3], [4,5]]

for element in itertools.product(*somelist):
  print element

SymPy에 대해서요.

이 작업은 다음과 같이 수행할 수 있습니다.

[(x, y) for x in range(10) for y in range(10)]

또 다른 변수?문제 없음:

[(x, y, z) for x in range(10) for y in range(10) for z in range(10)]

99%의 경우 iter tools.product를 사용해야 합니다.그것은 효율적인 C 코드로 작성되어 있기 때문에 아마도 어떤 맞춤형 구현보다 더 나을 것입니다.

파이썬 전용 알고리즘이 필요한 경우(예를 들어 어떻게든 수정해야 하는 경우)의 1%에서 아래 코드를 사용할 수 있습니다.

def product(*args, repeat=1):
    """Find the Cartesian product of the arguments.

    The interface is identical to itertools.product.
    """
    # Initialize data structures and handle bad input
    if len(args) == 0:
        yield () # Match behavior of itertools.product
        return
    gears = [tuple(arg) for arg in args] * repeat
    for gear in gears:
        if len(gear) == 0:
            return
    tooth_numbers = [0] * len(gears)
    result = [gear[0] for gear in gears]

    # Rotate through all gears
    last_gear_number = len(gears) - 1
    finished = False
    while not finished:
        yield tuple(result)

        # Get next result
        gear_number = last_gear_number
        while gear_number >= 0:
            gear = gears[gear_number]
            tooth_number = tooth_numbers[gear_number] + 1
            if tooth_number < len(gear):
                # No gear change is necessary, so exit the loop
                result[gear_number] = gear[tooth_number]
                tooth_numbers[gear_number] = tooth_number
                break
            result[gear_number] = gear[0]
            tooth_numbers[gear_number] = 0
            gear_number -= 1
        else:
            # We changed all the gears, so we are back at the beginning
            finished = True

인터페이스는 itertools.product의 경우와 동일합니다.예:

>>> list(product((1, 2), "ab"))
[(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b')]

이 알고리즘은 이 페이지의 다른 Python 전용 솔루션에 비해 다음과 같은 이점이 있습니다.

  • 메모리에 중간 결과가 쌓이지 않아 메모리 설치 공간을 작게 유지합니다.
  • 재귀 대신 반복을 사용하므로 "최대 재귀 깊이 초과" 오류가 발생하지 않습니다.
  • 반복 가능한 입력 항목 수에 관계없이 사용할 수 있으므로 루프에 중첩된 항목을 사용하는 것보다 유연합니다.

이 코드는 MIT 라이센스로 릴리스된 PyPy의 itertools.product 알고리즘을 기반으로 합니다.

사용할 수 있습니다.itertools.product표준 라이브러리에서 데카르트 제품을 가져옵니다.에 있는 다른.itertools포하다를 permutations,combinations,그리고.combinations_with_replacement다음은 아래 스니펫에 대한 Python CodePen 링크입니다.

from itertools import product

somelists = [
   [1, 2, 3],
   ['a', 'b'],
   [4, 5]
]

result = list(product(*somelists))
print(result)

직접 다시 구현하려는 경우 재귀를 시도할 수 있습니다.다음과 같은 간단한 것:

def product(cats, prefix = ()):
  if not cats:
    yield prefix
  else:
    head, *tail = cats
    for cat in head:
      yield from product(tail, prefix + (cat,))

작업 시작입니다.

재귀 깊이는 범주 목록의 개수입니다.

효과가 있다고 생각합니다.

def cartesian_product(L):  
   if L:
       return {(a,) + b for a in L[0] 
                        for b in cartesian_product(L[1:])}
   else:
       return {()}

다음 코드는 NumPy를 사용하여 두 배열의 모든 조합 배열을 구축한 것입니다. 모든 크레딧이 여기에 있습니다!이것은 오직 NumPy에만 있기 때문에 훨씬 빠르다고 합니다.

import numpy as np

def cartesian(arrays, dtype=None, out=None):
    arrays = [np.asarray(x) for x in arrays]
    if dtype is None:
        dtype = arrays[0].dtype
    n = np.prod([x.size for x in arrays])
    if out is None:
        out = np.zeros([n, len(arrays)], dtype=dtype)

    m = int(n / arrays[0].size)
    out[:,0] = np.repeat(arrays[0], m)
    if arrays[1:]:
        cartesian(arrays[1:], out=out[0:m, 1:])
        for j in range(1, arrays[0].size):
            out[j*m:(j+1)*m, 1:] = out[0:m, 1:]
    return out

모든 항목에 대해 첫 번째 항목에서 dtype을 사용하지 않으려면 dtype을 매개 변수로 정의해야 합니다.항목으로 문자와 숫자가 있는 경우 type = 'object'를 사용합니다.테스트:

somelists = [
   [1, 2, 3],
   ['a', 'b'],
   [4, 5]
]

[tuple(x) for x in cartesian(somelists, 'object')]

외부:

[(1, 'a', 4),
 (1, 'a', 5),
 (1, 'b', 4),
 (1, 'b', 5),
 (2, 'a', 4),
 (2, 'a', 5),
 (2, 'b', 4),
 (2, 'b', 5),
 (3, 'a', 4),
 (3, 'a', 5),
 (3, 'b', 4),
 (3, 'b', 5)]

언급URL : https://stackoverflow.com/questions/533905/how-to-get-the-cartesian-product-of-multiple-lists

반응형

'prosource' 카테고리의 다른 글

AAD에 Azure 응용 프로그램이 등록되지 않았습니다.  (0) 2023.04.28
키를 기준으로 사전 정렬  (0) 2023.04.28
angular2에서 fong-disabled의 대안이 있습니까?  (0) 2023.04.28
Git으로 분기점을 찾으십니까?  (0) 2023.04.23
iOS Simulator 배포 대상은 7.0으로 설정되었지만 이 플랫폼에서 지원되는 배포 대상 버전은 8.0에서 12.1입니다.  (0) 2023.04.23

'prosource'의 다른글

  • 현재글여러 목록의 데카르트 곱을 가져오는 방법

관련글

댓글

티스토리툴바