카디 전 곱을 반복적으로 계산하려면 어떻게해야합니까?

Question

This question은 주어진 수의 벡터의 데카르트 곱을 계산하는 방법을 묻습니다. 벡터의 수는 미리 알려지고 비교적 작기 때문에 중첩 된 for 루프를 사용하면 쉽게 솔루션을 얻을 수 있습니다.

이제 (등, 또는 목록의 목록 또는 세트 세트), 선택의 여지가 귀하의 언어로, 벡터의 벡터를 주어진 것으로 가정합니다

l = [ [1,2,3], [4,5], [6,7], [8,9,10], [11,12], [13] ] 

내가 계산하도록 요청 된 경우는

[ [1,4,6,8,11,13], [1,4,6,8,12,13], [1,4,6,9,11,13], [1,4,6,9,12,13], ... ] 

나는 재귀를 진행할 것이다. 예를 들어, 빠른 & 더러운 파이썬에서,

def cartesianProduct(aListOfLists): 
    if not aListOfLists: 
     yield [] 
    else: 
     for item in aListOfLists[0]: 
      for product in cartesianProduct(aListOfLists[1:]): 
       yield [item] + product 

는 반복적으로 계산하는 쉬운 방법이 있나요?

(참고 : 대답은 파이썬에있을 필요가없고, 어쨌든 내가 파이썬 itertools에 this question 같이 작업 잘한다는 것을 알고 있어요.)

Answer 1

1) 인덱스의리스트로 만들기

indexes = [0,0,0,0,0,0] 

2) 각 목록 (이 경우 첫 번째 항목)에서 적절한 요소를 얻습니다.

3) 마지막 색인을 1 씩 늘립니다.

4) 마지막 색인이 마지막 목록의 길이와 같으면이를 0으로 재설정하고 하나를 옮깁니다. 운반이 없을 때까지 이것을 반복하십시오. 인덱스 다시 [0,0,0,0,0,0]

그것은 유사에 포장까지 각 숫자가 다를 수 있습니다에 대한 기본을 제외하고, 작품을 계산하는 방법을

5) 2 단계로 돌아갑니다 .

def cartesian_product(aListOfList): 
    i = 0 
    while True: 
     result = [] 
     j = i 
     for l in aListOfList: 
      result.append(l[j % len(l)]) 
      j /= len(l) 
     if j > 0: return 
     yield result 
     i += 1 

참고이이를 출력 :

def cartesian_product(aListOfList): 
    indexes = [0] * len(aListOfList) 
    while True: 
     yield [l[i] for l,i in zip(aListOfList, indexes)] 
     j = len(indexes) - 1 
     while True: 
      indexes[j] += 1 
      if indexes[j] < len(aListOfList[j]): break 
      indexes[j] = 0 
      j -= 1 
      if j < 0: return 

다음

---

이 모듈 트릭을 사용하여 구현하는 또 다른 방법은 다음과 같습니다

---

는 파이썬에서 위의 알고리즘의 구현이다 귀하의 예와 약간 다른 순서로 결과가 나타납니다. 역순으로 목록을 반복하여 해결할 수 있습니다.

Answer 2

모두 i에 대해 0에서 \Pi a_i_length까지 반복합니다.

for (int i = 0; i < product; i++) { 
    // N is the number of lists 
    int now = i; 
    for (int j = 0; j < N; j++) { 
     // This is actually the index, you can get the value easily. 
     current_list[j] = now % master_list[j].length; 

     // shifts digit (integer division) 
     now /= master_list[j].length; 
    } 
} 

동일한 작업을 두 번 할 필요가 없도록 몇 가지 사소한 방법이 있습니다.

Answer 3

스택을 수동으로 관리하면됩니다. 기본적으로, 재귀가 스스로 수행하는 작업을 수행하십시오.

Let L[i] = elements in vector i 
k = 0; 
st[] = a pseudo-stack initialized with 0 
N = number of vectors 
while (k > -1) 
{ 
    if (k == N) // solution, print st and --k 

    if (st[k] < L[k].count) 
    { 
    ++st[k] 
    ++k 
    } 
    else 
    { 
    st[k] = 0; 
    --k; 
    } 
} 

테스트하지,하지만 아이디어는 작동합니다 재귀가 스택에 각 재귀 호출에 대한 데이터를두고 있기 때문에, 당신은 단지 동일한 작업을 수행. 바라기를 나는 아무것도 놓치지 않았다.

편집 : 음, 너무 늦은 것 같습니다. 이것은 기본적으로 카운팅과 동일하며이를 보는 또 다른 방법입니다.

Answer 4

언어에 구애받지 않는 솔루션을 요청한 사람은 여기 bash에 있지만, 우리는 이것을 반복적으로 재귀 적으로 부를 수 있습니까? 단지 표기법입니다 :

echo {1,2,3},{4,5},{6,7},{8,9,10},{11,12},13 

아마도 충분히 흥미 롭습니다.

1,4,6,8,11,13 1,4,6,8,12,13 1,4,6,9,11,13 1,4,6,9,12,13 1,4,6,10,11,13 ...