algorithm - 함수 - 순열에서 유효한 블록 수를 계산하는 알고리즘




파이썬 순열 알고리즘 (5)

가능한 중복 :
순열에서 정렬 된 하위 시퀀스 찾기

1,2, ..., n의 순열을 보유하는 배열 A가 주어진다. 서브 블록 A [i..j]
배열 A의 모든 숫자가 A [i..j]에 나타나는 경우 유효한 블록이라고 부릅니다.
연속적인 숫자입니다 (순서가 맞지 않을 수도 있음).

주어진 어레이 A = [7 3 4 1 2 6 5 8] 유효한 블록은 [3 4], [1,2], [6,5],
[3 4 1 2 6 5], [7 3 4 1 2 6 5], [7 3 4 1 2 6 5 8]

위 permutation에 대한 카운트는 7입니다.

유효한 블록 수를 계산하는 O (n log n) 알고리즘을 제공하십시오.


(이것은 N.log (N) 최악의 경우를 수행하려는 시도입니다. 불행히도 잘못된 것입니다. 때로는 적게 계산됩니다. 더 작은 유효 블록 만 인접한 쌍으로 보면 모든 블록을 찾을 수 있다고 잘못 가정합니다. 모든 더 큰 블록을 얻으려면 삼중 항, 네 쌍 등을 살펴보십시오.)

하위 블록을 나타내는 구조체와 하위 블록의 큐를 사용하면됩니다.

  struct
c_subblock
{
  int           index   ;  /* index into original array, head of subblock */
  int           width   ;  /* width of subblock > 0 */
  int           lo_value;
  c_subblock *  p_above ;  /* null or subblock above with same index */
};

원래 배열과 동일한 크기의 서브 블록 배열을 할당하고 각 서브 블록을 초기화하여 정확히 하나의 항목을 갖습니다. 이동 중에 대기열에 추가하십시오. 배열 [7 3 4 1 2 6 5 8]로 시작하면 다음과 같은 대기열로 끝납니다 :

큐 : ([7,7] [3,3] [4,4] [1,1] [2,2] [6,6] [5,5] [8,8])

서브 블록 [7,7]에 대한 {index, width, lo_value, p_above} 값은 {0, 1, 7, null}입니다.

이제는 쉽습니다. C-ish 의사 코드를 용서하십시오.

loop {
  c_subblock * const p_left      = Pop subblock from queue.
  int          const right_index = p_left.index + p_left.width;
  if ( right_index < length original array ) {
    // Find adjacent subblock on the right.
    // To do this you'll need the original array of length-1 subblocks.
    c_subblock const * p_right = array_basic_subblocks[ right_index ];
    do {
      Check the left/right subblocks to see if the two merged are also a subblock.
        If they are add a new merged subblock to the end of the queue.
      p_right = p_right.p_above;
    }
    while ( p_right );
  }
}

이것은 내가 생각하는 모든 것을 발견 할 것이다. 일반적으로 O (N log (N))이지만 완전히 정렬되거나 반올림되지 않은 목록의 경우 O (N ^ 2)가됩니다. 제 생각에는 거기에 대한 해답이 있다고 생각합니다. 원래의 서브 블록 배열을 만들 때 정렬 된 배열과 반올림되지 않은 시퀀스를 찾고이를 기본 레벨의 서브 블록으로 추가합니다. 카운트를 유지하는 경우에는 기본 레벨에 대해 (width * (width + 1)) / 2만큼 증가시킵니다. 그러면 모든 1 길이 서브 블록을 포함한 카운트가 제공됩니다.

그런 다음 위의 루프를 사용하여 대기열을 터벅 터벅으로 밀면됩니다. 계산하는 경우 왼쪽 및 오른쪽 서브 블록 모두에 승수가 있어야하며 증분을 계산하기 위해 이들을 곱하십시오. 승수는 가장 왼쪽 (p_left의 경우) 또는 가장 오른쪽 (p_right의 경우) 기본 레벨 서브 블록의 너비입니다.

이것이 분명하고 너무 버그가 없다는 것을 희망하십시오. 나는 그걸 부딪쳐서 잘못되었을 수도 있습니다. [나중에 메모. 이것은 결국 작동하지 않습니다. 아래 주 참조.]


그냥 몇 가지 생각 :

언뜻보기에는 이것이 불가능한 것처럼 들립니다. 완전히 정렬 된 배열은 O (n 2 ) 개의 유효 하위 블록을가집니다.

따라서 한 번에 하나 이상의 유효한 하위 블록을 세어야합니다. 하위 블록의 유효성을 검사하는 것은 O (n) 입니다. 하위 블록이 완전히 정렬되었는지 확인하는 것은 O (n) 입니다. 완전히 정렬 된 하위 블록에는 n * (n - 1) / 2 개의 유효한 하위 블록이 포함되어 있으며이 하위 블록을 더 이상 깨지 않고 계산할 수 있습니다.

이제 전체 배열이 항상 유효합니다. Divide-and-Conquer 접근법을 위해, 이것을 깨뜨릴 필요가 있습니다. 가장 높은 요소의 위치와 가장 낮은 요소의 위치라는 두 가지 중요한 단점이 있습니다. 두 번째 -> 극단적 인 요소가 포함 된 부분의 극값을 포함하여이 지점 중 하나에서 배열을 두 개로 나누면 유효한 하위 블록이이 중단 점을 지나칠 수 없습니다.

항상 균등 분할을 생성하는 극한값을 선택함으로써, 이것은 "무작위"배열에 대해 아주 잘 작동합니다 (평균 O (n log n) ). 그러나, 당신의 입력이 (1 5 2 6 3 7 4 8) 과 같을 때 나는 O (n 2 ) 행동을 보이는 것처럼 보이는 문제를 볼 수 있습니다. (1 4 7 2 5 8 3 6 9) 비슷한 것입니다 (나는 당신이 패턴을 보길 바랍니다). 나는 현재 이런 종류의 더 나쁜 경우를 잡으려고 아무런 트릭도 보지 못하지만, 다른 분할 기법이 필요해 보인다.


다른 모든 사람들과 마찬가지로, 나는 이것을 꺼내고 있습니다 ... 아래의 단일 예제에서 작동하지만 YMMV!

아이디어는 불법적 인 하위 블록의 수를 세고 가능한 총 수에서 빼는 것입니다. 우리는 각 배열 요소를 차례로 검사하고 그 요소를 포함하지만 그 전임자 나 후계자를 포함하지 않는 하위 블록을 배제함으로써 불법 복제를 계산합니다.

  1. Foreach i in [1, N]은 B [A [i]] = i를 계산합니다.

  2. Let Count = 길이가 1보다 큰 N-choose-2 (시작 및 끝 인덱스의 가능한 조합 각각에 대해 하나) 인 서브 블록의 총 수입니다.

  3. Foreach i, A [i]를 생각해보십시오. 엣지 케이스를 무시하고, x = A [i] -1로하고, y = A [i] +1로한다. A [i]는 x 또는 y를 포함하지 않는 하위 블록에 참여할 수 없습니다. iX = B [x] 및 iY = B [y]라고하자. 여기서는 독립적으로 치료해야 할 몇 가지 사례가 있습니다. 일반적인 경우는 iX<i<iY<i 입니다. 이 경우, 서브 블록 A [iX + 1 .. iY-1] 및 i를 포함하는 모든 개재 블록을 제거 할 수있다. 이러한 하위 블록이 (i-iX + 1) * (iY-i + 1)이므로이 번호를 제거하십시오. (그 밖의 경우는 리더의 연습 문제로 남겨 두었습니다.) Set Count = Count - Eliminated.

  4. 반환 횟수.

총 비용은 N * (2 단계 비용) = O (N) 인 것으로 보입니다.

WRINKLE : 2 단계에서 각 하위 간격을 두 번 이상 제거하지 않도록주의해야합니다. 우리는 위치 i의 오른쪽에 전체 또는 부분적으로 속하는 하위 간격 만 제거하여이를 수행 할 수 있습니다.

예:
A = [1, 3, 2, 4] B = [1, 3, 2, 4]

초기 카운트 = (4 * 3) / 2 = 6

i = 1 : A [i] = 1이므로 서브 블록에 2가 있어야합니다. 우리는 배려에서 [1,3]을 제거 할 수 있습니다. 제거됨 = 1, 조사 -> 5.

i = 2 : A [i] = 3이므로 2 ~ 4 개의 서브 블록이 필요합니다. 이것은 [1,3]을 배제하지만 i = 1에서 바로 볼 때 이미 그것을 설명했습니다. 제거됨 = 0.

i = 3 : A [i] = 2이므로 하위 블록에 [1] 또는 [3]이 필요합니다. 우리는 배려에서 [2,4]를 제거 할 수 있습니다. 제거됨 = 1, 조사 -> 4.

i = 4 : A [i] = 4, 그래서 우리는 그 안에 [3]을 가진 하위 블록이 필요합니다. 이 규칙은 배제되어 있지만, 우리는 이미 i = 3에서 보았을 때 이미 그것을 설명했습니다. 제거됨 = 0.

최종 개수 = 4, 하위 블록 [1,3,2,4], [1,3,2], [3,2,4] 및 [3,2]에 해당합니다.


원래 배열에는 중복이 없으므로 연속적인 블록이어야합니다. 이 블록 (1 ~ n)을 호출 할 수 있습니다. 첫 번째 요소가 1인지 또는 O (1)인지 확인하여 블록 (2 ~ n)이 연속적인지 여부를 테스트 할 수 있습니다. 마찬가지로 마지막 요소가 1 또는 n인지 확인하여 블록 (1 ~ n-1)을 테스트 할 수 있습니다.

나는 이것을 작동시킬 수있는 해결책으로 만들 수는 없지만 누군가를 도울 것입니다 ...


좋아, 나는 200의 현상금을 관련 질문에 두었 기 때문에 1 명의 담당자에게 내려 갔다 . 순열로 정렬 된 하위 시퀀스를 찾아 잠시 동안 코멘트를 남길 수 없다.

1) 모든 순열 그룹을 찾습니다. 그들은 (78), (34), (12), (65)입니다. 그룹 이론과는 달리, 그들의 순서와 위치, 그리고 그들이 인접한 문제인지 여부. 따라서 그룹 (78)은 구조 (7, 8, false) 로 표현 될 수있는 반면, (34)는 (3,4,true) 가 될 수 있습니다. 튜플에 파이썬의 표기법을 사용하고 있지만 실제로 그룹 전체 클래스를 사용하는 것이 좋습니다. 여기에서 true 또는 false는 연속적인지 여부를 의미합니다. (max(gp1) == min(gp2) + 1 or max(gp2) == min(gp1) + 1) and contigous(gp1) and contiguos(gp2) 두 그룹은 "인접"합니다. 이것은 (14)(23) 합쳐서 (14) 멋지게 결합되기 때문에 union(gp1, gp2) 이 인접하기위한 유일한 조건은 아닙니다. 이것은 고등학생 수업 숙제에 대한 중대한 질문이지만 면접을위한 끔찍한 질문입니다. 숙제라고 생각합니다.





permutation