itertools.product를 다른 순서로 생성하십시오.

Question

일부 정렬/점수 목록 목록이 있습니다. 매개 변수 (직교 좌표 곱)의 가능한 조합을 생성하고 싶습니다. 그러나 매개 변수의 수가 많으면이 값 (매우 빠르게!)이 매우 커집니다. 기본적으로 저는 직교 제품을 원하지만 일찍 멈 춥니 다.

import itertools 
parameter_options = ['1234', 
        '123', 
        '1234'] 
for parameter_set in itertools.product(*parameter_options): 
    print ''.join(parameter_set) 

를 생성 :

111 
112 
113 
114 
121 
122 
123 
124 
131 
132 
133 
134 
... 

내가 생성하고 싶습니다 (유사하거나 뭔가를)

일찍 중지하면, 나는 적어도 몇 가지를 얻을 거라고 그래서

111 
112 
121 
211 
122 
212 
221 
222 
... 

"좋은"매개 변수 집합을 사용합니다. 매개 변수 집합은 대부분 목록에서 조기에 나타납니다. 이 특별한 순서는 괜찮지 만, "다음 순열"선택 순서를 변경하는 기술에 관심이 있습니다. 나는 초기 결과가 목록 앞에서 대부분의 항목을 가지고 생성하지만, 솔루션이 113 또는 122 먼저 생성하는지 여부 또는 211 또는 112 먼저 온다 상관하지 않는 것이 좋습니다.

내 계획은 몇 가지 순열이 생성 된 후 중지하는 것입니다 (아마도 10K 정도? 결과에 따라 다름). 따라서 컷오프보다 적 으면 궁극적으로 모든 것이 생성되어야합니다. 그리고 바람직하게는 각각 한 번만 생성됩니다.

Answer 1

이 솔루션은 모든 조합을 메모리에 잠깐 강제로 적용하기 때문에 가능하지 않을 수도 있지만 작동합니다. 대용량 데이터 세트의 경우 조금 시간이 걸릴 수 있습니다.

import itertools 
import random 
count = 100 # the (maximum) amount of results 
results = random.sample(list(itertools.product(*parameter_options)), count) 

for parameter_set in results: 
    print "".join(parameter_set) 

이렇게하면 임의의 순서로 제품 목록을 얻을 수 있습니다.

Answer 2

출력 공간을 가로 지르는 그래프 측면에서 출력을 생각하면 원하는 순서대로 결과를 얻을 수 있다고 생각합니다. 가장 가까운 우선 탐색을 원하지만 itertools.product 함수는 깊이 우선 탐색입니다. 이 같은

시도 뭔가 :

import heapq 

def nearest_first_product(*sequences): 
    start = (0,)*len(sequences) 
    queue = [(0, start)] 
    seen = set([start]) 
    while queue: 
     priority, indexes = heapq.heappop(queue) 
     yield tuple(seq[index] for seq, index in zip(sequences, indexes)) 
     for i in range(len(sequences)): 
      if indexes[i] < len(sequences[i]) - 1: 
       lst = list(indexes) 
       lst[i] += 1 
       new_indexes = tuple(lst) 
       if new_indexes not in seen: 
        new_priority = sum(index * index for index in new_indexes) 
        heapq.heappush(queue, (new_priority, new_indexes)) 
        seen.add(new_indexes) 

예 출력 :

for tup in nearest_first_product(range(1, 5), range(1, 4), range(1, 5)): 
    print(tup) 

(1, 1, 1) 
(1, 1, 2) 
(1, 2, 1) 
(2, 1, 1) 
(1, 2, 2) 
(2, 1, 2) 
(2, 2, 1) 
(2, 2, 2) 
(1, 1, 3) 
(1, 3, 1) 
(3, 1, 1) 
(1, 2, 3) 
(1, 3, 2) 
(2, 1, 3) 
(2, 3, 1) 
(3, 1, 2) 
(3, 2, 1) 
(2, 2, 3) 
(2, 3, 2) 
(3, 2, 2) 
(1, 3, 3) 
(3, 1, 3) 
(3, 3, 1) 
(1, 1, 4) 
(2, 3, 3) 
(3, 2, 3) 
(3, 3, 2) 
(4, 1, 1) 
(1, 2, 4) 
(2, 1, 4) 
(4, 1, 2) 
(4, 2, 1) 
(2, 2, 4) 
(4, 2, 2) 
(3, 3, 3) 
(1, 3, 4) 
(3, 1, 4) 
(4, 1, 3) 
(4, 3, 1) 
(2, 3, 4) 
(3, 2, 4) 
(4, 2, 3) 
(4, 3, 2) 
(3, 3, 4) 
(4, 3, 3) 
(4, 1, 4) 
(4, 2, 4) 
(4, 3, 4) 

당신은 코드에서 new_priority의 계산을 변경하여 약간 다른 주문의 무리를 얻을 수 있습니다. 현재 버전에서는 제곱 데카르트 거리를 우선 순위로 사용하지만 원할 경우 다른 값을 사용할 수도 있습니다 (예 : 인덱스뿐만 아니라 시퀀스의 값도 포함).

(둘 다 (1, 1, 2), (1, 2, 1) 및 (2, 1, 1) 후에 와서 너무 오래) 당신이 (1, 1, 3)이 (1, 2, 2) 앞에 오는 여부에 대해 너무 많이 걱정하지 않는 경우, 당신은 아마 폭 우선 탐색을 할 수있는 대신에 가까운 최초. 우선 순위 대기열이 아닌 일반 대기열 (예 : collections.deque)을 사용할 수 있기 때문에 조금 더 간단합니다.

이러한 종류의 그래프 통과에 사용되는 큐는이 코드가 일정량의 메모리를 사용한다는 것을 의미합니다. 그러나 결과를 순서대로 정리하기 전에 결과를 모두 만들어야하는 경우보다 메모리 양이 훨씬 적습니다. 사용 된 최대 메모리는 볼륨이 아닌 결과 공간의 표면적에 비례합니다.

Answer 3

귀하의 질문은 다소 모호하지만 귀하의 의견과 다른 답변을 읽으면서 깊이 검색 대신 폭 넓은 검색을 수행하는 데카르트 제품 구현이 필요합니다.

최근에 나는 같은 필요성을 가지고 있었지만 중간 결과를 메모리에 저장하지 않는다는 요구 사항도 가지고있었습니다. 많은 수의 매개 변수 (따라서 매우 큰 데카르트 제품)와 값을 저장하거나 재귀 호출을 수행하는 구현은 실행 불가능하기 때문에 이것은 매우 중요합니다. 귀하가 귀하의 질문에 진술 한대로 귀하의 주장도 마찬가지입니다. 나는이 요구 사항을 충족 답을 찾지 못했습니다으로

, 나는이 솔루션에 온 :

속도의 측면에서

def product(*sequences): 
    '''Breadth First Search Cartesian Product''' 
    # sequences = tuple(tuple(seq) for seqin sequences) 

    def partitions(n, k): 
     for c in combinations(range(n+k-1), k-1): 
      yield (b-a-1 for a, b in zip((-1,)+c, c+(n+k-1,))) 

    max_position = [len(i)-1 for i in sequences] 
    for i in range(sum(max_position)): 
     for positions in partitions(i, len(sequences)): 
      try: 
       yield tuple(map(lambda seq, pos: seq[pos], sequences, positions)) 
      except IndexError: 
       continue 
    yield tuple(map(lambda seq, pos: seq[pos], sequences, max_position)) 

,이 발전기는 처음에 잘 작동하지만 최신 결과에 느려 시작 . 따라서이 구현은 약간 느리지 만 메모리를 사용하지 않고 반복되는 값을 제공하지 않는 생성기로 작동합니다.

@Blckknght 답변에서 언급했듯이 여기의 매개 변수도 시퀀스 (subscriptable 및 length-defined iterables) 여야합니다. 그러나 첫 번째 줄의 주석 처리를 제거함으로써이 제한을 우회 할 수도 있습니다 (약간의 메모리를 희생 시키십시오). 생성자/반복자를 매개 변수로 사용하는 경우 유용 할 수 있습니다.

귀하의 도움이 되었으면 알려 드리겠습니다.