이 패턴에는 어떤 우아한 해결책이 있습니까? 다중 레벨 검색

Question

우리는 정수 배열이 여러 개 있다고 가정합니다. 각 배열을 하나의 레벨로 간주 할 수 있습니다. 우리는 각 배열로부터 정확히 하나의 요소 인 요소들의 시퀀스를 찾고 동일한 술어를 가진 다음 배열로 진행하려고합니다. 예를 들어, 우리는 배열로 v1, v2, v3 있습니다

v1 | v2 | v3 
----------------- 
1 | 4 | 16 
2 | 5 | 81 
3 | 16 | 100 
4 | 64 | 121 

나는 조건이라고 말할 수 있습니다 : next_element == previous_element^2
위의 예에서 유효한 순서는 다음과 같습니다 사실 2 -> 4 -> 16
는,이 예에서는 또 다른이 없다 유효한 순서. 위의 예에서 짐작할 수있는 루프를 세 개 쓸 수 있습니다. 그러나 배열 수가 가변적 인 경우 일 수는 있지만 물론 순서를 알고 있으면이 문제를 어떻게 해결할 수 있습니까?

힌트 또는 디자인 패턴에 대한 언급은 매우 감사하겠습니다. 나는 C++로 그것을 할 것이지만, 나는 그 아이디어가 필요하다. 당신이 사전에 배열을 주문하는 경우

덕분에,

Answer 1

검색이 훨씬 더 빠르게 수행 할 수 있습니다. 작은 배열에서부터 시작하여 각각에 대해 예상되는 숫자를 2 진 검색 할 수 있습니다. 이것은 O (n k logM) 일 수 있습니다. n은 가장 작은 배열의 크기이고, k는 배열의 수이며, M은 더 큰 배열의 크기입니다.

대신 해시 맵을 사용하면 더 빨리 수행 할 수 있습니다. 배열의. 그러면 O (n * k)에서 검색 할 수 있습니다.

역방향 함수를 사용하여 (이전 배열 검색시) 옵션이 아닌 경우 첫 번째 배열에서 시작하고 n = 첫 번째 배열 크기로 시작해야합니다. 편의상

, 나는 순서가 존재하는지 알고 당신은 아마 널 (null) 검사를하고 거기에 약간의 논리 값을 추가 할 수 있습니다

//note the 1-based arrays 
for (i : 1 until allArrays[1].size()) { 
    baseNumber = allArrays[1][i]; 
    for (j: 2 until allArrays.size()) { 
    expectedNumber = function(baseNumber); 
    if (!find(expectedNumber, allArrays[j])) 
     break; 
    baseNumber = expectedNumber; 
    } 
} 

첫 번째 배열에서 시작 여부를

이

Answer 2

당신은을 생성 할 수 있습니다 한 배열의 인덱스를 다른 배열의 인덱스에 매핑하는 별도의 인덱스입니다. 색인에서 솔루션이 존재하는지 여부를 신속하게 확인할 수 있습니다.

색인 생성에는 무차별 대항 방법이 필요하지만 그 중 하나만 수행하면됩니다. 배열 검색을 향상 시키려면보다 적절한 데이터 구조를 사용하여 빠른 검색 (예 : 배열 대신 빨간색 검정색 트리)을 허용하는 것이 좋습니다.

Answer 3

모든 벡터를 heaps으로 유지하므로 요소를 검색 할 때 O(log n)의 복잡성을 가질 수 있습니다. 당신은에 따라 O(k * log n)

Answer 4

(디자인 패턴은 코드 품질을 개선하기 위해 클래스와 API 디자인에 적용, 그러나 계산 문제를 해결하기위한 것이 아닙니다.)

같은 복잡성을 얻을 것이다 k 벡터의 총 그래서 사례 :

1. 배열이 무작위 순서로 나오고 유한 공간 요구 사항이있는 경우 무차별 공격 만이 유일한 해결책입니다. O (N ^k) 시간 (k = 3), O (1) 공간.
2. 술어가 반전 가능하지 않은 경우 (예 :SHA1(next_elem) xor SHA1(prev_elem) == 0x1234), brute force 또한 유일한 해결책입니다.
3. 공간을 낭비 할 수있는 경우 v2 및 v3에 대한 해시 세트를 생성하여 조건자를 만족하는 다음 요소를 빠르게 찾을 수 있습니다. O (N + b ^k) 시간, O (kN) 공간. (b = prev_elem이 주어지면 술어를 만족하는 next_elem의 최대 수)
4. 배열이 정렬되고 경계가 있으면 해시 테이블 대신 이진 검색을 사용하여 공간 사용을 피할 수 있습니다. O (N (logN) ^k-1 + b ^k) 시간, O (1) 공간.

(공간 수의 모든 의한 재귀 사용을 스택을 고려하지 않습니다.)

O 최대 소비 일반적인 방법 (Nb를가 ^K) 공간으로 솔루션을 구축하는 것입니다 연속 필터링, 예. 술어가 배열의 순서를 유지하는 경우 (값이 모두 음수를 보장하는 경우 예를 들어, 귀하의 예제와 함께)

solutions = [[1], [2], ... [N]] 

filterSolution (Predicate, curSols, nextElems) { 
    nextSols = [] 
    for each curSol in curSols: 
     find elem in nextElems that satisfy the Predicate 
     append elem into a copy of curSol, then push into nextSols 
    return nextSols 
} 

for each levels: 
    solutions = filterSolution(Predicate, solutions, all elems in this level) 
return solutions 

Answer 5

, 당신은 병합 알고리즘을 적용 할 수있다. 각 배열의 최종 값 (모든 배열에 대해 필요한만큼 여러 번 술어를 적용한 후 얻는 값)을 고려하십시오.

술어가 순서를 유지하지 않거나 배열의 시작 순서가 지정되지 않은 경우 먼저 끝 값을 기준으로 정렬 할 수 있지만 그렇게해야 할 경우 다른 접근 방법이 더 좋을 수도 있습니다 (예 : 다른 곳에서 제안 된 해시 테이블).

기본적으로 다음 종료 값이 모든 배열에서 동일한 지 확인하십시오. 그렇지 않은 경우 가장 낮은 단계 (한 배열에서만)로 단계를 반복하십시오. 3 개 모두가 동등하다면, 그것은 (가능한) 해결책입니다 - 다음을 검색하기 전에 3 개 모두를 수행하십시오.

점검이 필요할 수 있으므로 "가능한"솔루션 - 술어 기능이 둘 이상의 입력 값을 동일한 출력 값에 맵핑 할 수있는 경우, 일부 어레이에서 발견 된 값 첫 번째 또는 마지막)가 잘못되었습니다.

EDIT - 술어가 각 입력을 고유 한 출력으로 매핑하지 않을 때 더 큰 문제가 발생할 수 있습니다 - 지금은 생각할 수 없습니다. 기본적으로 병합 접근법은 잘 작동 할 수 있지만 특정 종류의 술어 기능에서만 가능합니다.