반복을 건너 뛸 수있는 데카르트 곱을 구현합니다.

Question

세트의 반복 된 주어진 수의 데카르트 곱을 반환하는 함수를 구현하고 싶습니다. 예를

input: {a, b}, 2 
output: 
aa 
ab 
bb 
ba 

input: {a, b}, 3 
aaa 
aab 
aba 
baa 
bab 
bba 
bbb 

를 들어 내가 같은 세트를 추가, 그것은 먼저 다음 세트의 출력에서, 2 개 세트 ("AB", "AB)에 대한 cartesion 제품을하고 구현할 수있는 유일한 방법은. 여기 의사는하지만 -code는 :.

function product(A, B): 
    result = [] 
    for i in A: 
     for j in B: 
      result.append([i,j]) 
    return result 
function product1(chars, count): 
    result = product(chars, chars) 
    for i in range(2, count): 
     result = product(result, chars) 
    return result 

내가 원하는 것은 전에 모든 세트를 계산하지 않고, 직접 마지막 세트를 계산 시작하는 나에게 비슷한 결과를 줄 것이다이 가능, 또한 솔루션입니다, 그러나 그것은 아니다 데카르트 제품이 허용됩니다. 대부분의 범용 프로그래밍 언어를 읽는 데 문제가 없으므로 코드를 게시해야한다면 모든 언어로 할 수 있습니다. 편안한 느낌.

Answer 1

다음은 S^(n-1) "first"를 빌드하지 않고 S^n을 빌드하는 재귀 알고리즘입니다. 무한 k-ary 트리를 상상해보십시오. 여기서 | S | = k. 모든 부모를 k 개의 자식에 연결하는 각 모서리의 요소로 레이블을 지정합니다. S^m의 요소는 루트로부터 길이가 m 인 어떤 경로로 생각할 수 있습니다. 그러한 생각의 집합 S^m은 그러한 모든 경로의 집합입니다. 이제 S^n을 찾는 문제는 길이 n의 모든 경로를 열거하는 문제이며 가장자리 레이블의 순서를 처음부터 끝까지 고려하여 경로를 지정할 수 있습니다. 모든 S^(n-1)을 먼저 열거하지 않고 S^n을 직접 생성하기를 원하므로 깊이 n에서 모든 노드를 찾도록 수정 된 깊이 우선 탐색이 적절하게 보인다. 아래의 알고리즘이 작동하는 방법이 본질적으로 :

// collection to hold generated output 
members = [] 

// recursive function to explore product space 
Products(set[1...n], length, current[1...m]) 

    // if the product we're working on is of the 
    // desired length then record it and return 
    if m = length then 
     members.append(current) 
     return 

    // otherwise we add each possible value to the end 
    // and generate all products of the desired length 
    // with the new vector as a prefix 
    for i = 1 to n do 
     current.addLast(set[i]) 
     Products(set, length, current) 
     currents.removeLast() 

// reset the result collection and request the set be generated 
members = [] 
Products([a, b], 3, []) 

을 이제, 폭 우선 접근 방식은 깊이 우선 일보다 덜 효율적입니다, 그리고 당신이 그것에 대해 생각하는 경우에 당신이있어 정확히 다르지 없을 것 벌써하고있어. 실제로 S^n을 생성하는 접근법은 S^n에 대한 해에서 찾을 수 있기 때문에 S^(n-1)을 반드시 적어도 한번 생성해야한다.