[algorithm] O (nlogn) Algorithm-이진 문자열 내에서 균등 한 간격으로 3 개 찾기

어제 알고리즘 테스트 에서이 질문을 받았으며 답을 알 수 없습니다. 그것은 약 40 점의 가치가 있었기 때문에 나를 절대적으로 미치게합니다. 지난 24 시간 동안 해결책을 찾지 못했기 때문에 대부분의 수업이 올바르게 해결되지 않았다고 생각합니다.

길이가 n 인 임의의 이진 문자열이 주어지면 문자열 내에서 3 개의 균일 한 간격이있는 문자열을 찾으십시오. 이것을 O (n * log (n)) 시간 안에 해결하는 알고리즘을 작성하십시오.

따라서 이와 같은 문자열에는 “균등 간격”인 세 개의 문자열이 있습니다 : 11100000, 0100100100

편집 : 임의의 숫자이므로 모든 숫자에서 작동 할 수 있어야합니다. 내가 제공 한 예는 “균등 간격”속성을 설명하는 것이 었습니다. 따라서 1001011은 유효한 숫자입니다. 1, 4, 7은 균등 한 간격입니다.

답변

드디어! sdcvvc ‘s answer 에서 리드를 수행 하면 문제에 대한 O (n log n) 알고리즘이 있습니다! 이해 한 후에도 간단합니다. FFT를 추측 한 사람들이 옳았습니다.

문제 : S길이가 n 인 이진 문자열이 주어지고 그 안에 3 개의 고른 간격으로 1을 찾으려고합니다. 예를 들면, S일 수있다 110110010, 여기서, N = 9. 위치 2, 5 및 8에서 1을 균등하게 배치했습니다.

S왼쪽에서 오른쪽으로 스캔 하고 L1의 위치 목록 을 만듭니다. S=110110010위의 경우 L = [1, 2, 4, 5, 8] 목록이 있습니다. 이 단계는 O (n)입니다. 문제는 발견 지금 길이 3의 등차 수열 하여 L별개의 발견, 즉 A, B, C를 로 L되도록 BA = CB 또는 등가 A + C = 2B . 위의 예에서는 진행률 (2, 5, 8)을 찾고 싶습니다.
각 k in 에 대해 x ^k 항을 사용 하여 다항식 p 을 만듭니다 . 위의 예에서는 다항식 p (x) = (x + x ² + x ⁴ + x ⁵ + x ⁸ )로 만듭니다. 이 단계는 O (n)입니다.L
고속 푸리에 변환을 사용하여 다항식 q= p ^2를 찾습니다 . 위의 예에서, 우리는 다항식 q (x) = x ¹⁶ + 2x ¹³ + 2x ¹² + 3x ¹⁰ + 4x ⁹ + x ⁸ + 2x ⁷ + 4x ⁶ + 2x ⁵ + x ⁴ + 2x ³ + x ^2를 얻습니다 . 이 단계는 O (n log n)입니다.
일부 k in에 대해 x ^2k 에 해당하는 용어를 제외한 모든 항을 무시하십시오 . 위의 예에서 우리는 x ¹⁶ , 3x ¹⁰ , x ⁸ , x ⁴ , x ² 항을 얻습니다 . 이 단계는 O (n)입니다.L

여기서 중요한 점이다 : 임의의 계수 X에 ^2B 에 대한 B 의이 L있다 정확하게 쌍의 수 (a, c) 에 L되도록 A + C = 2B . [CLRS, 예. 30.1-7] 하나의 이러한 쌍은 (b, b) 는 항상 (계수는 적어도 1 정도)이지만 다른 쌍 존재하는 경우 (a, c)를 , 다음 계수로부터, 적어도 3 (a, C ) 및 (c, a) . 위의 예 에서 AP (2,5,8) 때문에 x ¹⁰ 의 계수는 정확하게 3입니다. (이 계수 x ^2b위의 이유로 항상 홀수입니다. q의 다른 모든 계수는 항상 짝수입니다.)

따라서 알고리즘은 이러한 항 x ^2b 의 계수를보고 그 중 하나가 1보다 큰지 확인합니다. 없으면 1이 고르지 않습니다. 이 경우 이다 B 의 L계수되는 X ^(2B)가 1보다 크면, 그때 우리는 어떤 쌍 있다는 것을 알고 (a, c) 이외 – (B, B)에 있는 – A + C = 2b는 . 실제 쌍을 찾으려면 각 a in L(해당 c 는 2b-a 일 것입니다)을 시도 하고 위치 2b-a 에서 1이 있는지 확인하십시오 S. 이 단계는 O (n)입니다.

그게 다야 사람들.

FFT를 사용해야합니까? beta ‘s , flybywire ‘s 및 rsp ‘ s 와 같은 많은 답변은 각 쌍의 1을 확인하고 “제 3″위치에 1이 있는지 확인하는 방법은 직관에 따라 O (n log n)에서 작동 할 수 있다고 제안합니다. 1이 너무 많으면 트리플이 쉽게 발견되고 1이 너무 적 으면 모든 쌍을 확인하는 데 시간이 거의 걸리지 않습니다. 불행하게도,이 직관은 정확하고 간단한 접근법 은 O (n ² ) 보다 낫지 만 , 크게 나아지지는 않습니다. 마찬가지로 sdcvvc의 대답 , 우리는 길이의 문자열 “세트 캔터 같은”취할 수 N = 3 ^케이삼항 표현이 0과 2 (1은 없음) 인 위치에 1이 있습니다. 이러한 문자열에는 2 ^k = n ^{(log 2) / (log 3)} ≈ n ^0.63이 있고 균등 한 간격이 1이 없으므로 모든 쌍을 확인하는 것은 1의 수의 제곱의 순서입니다. 불행히도 (n log n)보다 훨씬 더 큰 4 ^k ≈ n ^1.26 . 1953 년 레오 모서 : 사실, 최악의 경우는 더욱 심각하다 구성 (효과적으로)가 같은 문자열 N ^{1-C / √ (로그 n)을} 그들의 1S하지만 균등 1S, 어떤 의미 같은 문자열에서 단순 접근에는 Θ (n ^{2-2c / √ (log n)} )가 필요합니다.– 만 작은 더 이상의 비트 Θ (N ² ) , 놀랍게도!

길이의 문자열 1S의 최대 개수에 대한 N과 함께, 우리는 적어도 상기보고되었다 NO 3 균등 것들은 없다 ( N ^0.63 쉬운 칸토어 형 구조 및 상기 적어도에서 N ^{1-C / √ (로그 N)를} 가진 모저의 구성)-이것은 OEIS A003002 입니다. 또한 A065825 (k) ≤ n <A065825 (k + 1)가 되도록 OEIS A065825 에서 k로 직접 계산할 수도 있습니다 . 나는 이것을 찾기위한 프로그램을 작성했으며 욕심 많은 알고리즘이 그러한 문자열을 가장 길게 제공 하지 않는다는 것이 밝혀졌습니다 . 예를 들어, n = 9의 경우 5 1s (110100011)를 얻을 수 있지만 욕심쟁이는 n 에 대해 4 (110110000) 만 제공합니다.= 26 우리는 11 1s (11001010001000010110001101)를 얻을 수 있지만 욕심쟁이는 8 (11011000011011000000000000)을 제공하고 n = 74이면 22 1s (11000010110001000001011010001000000000000000010001011010000010001101000011)를 얻을 수 있지만 욕심쟁이는 16 (110110000110110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000110000000100000110110000000100,000) 그러나 그들은 50 세가 될 때까지 (예 : 38에서 50까지) 꽤 많은 곳에서 동의합니다. OEIS 참고 자료에 따르면 Jaroslaw Wroblewski는이 질문에 관심이있는 것으로 보이며 이러한 비 평균 세트 에 대한 웹 사이트를 유지 관리 합니다 . 정확한 숫자는 194까지만 알려져 있습니다.

답변

이 백서 (1999) 에서는 문제를 평균이라고합니다 .

문제 3SUM에서 이차 감소가있는 경우 문제는 3SUM-hard입니다. n 개의 정수 세트 A가 주어지면 A에 a + b + c = 0이되도록 요소 a, b, c가 있습니까? AVERAGE가 3SUM 하드인지는 알려져 있지 않습니다. 그러나 AVERAGE에서 3SUM으로의 간단한 선형 시간 단축이 있으며 그 설명은 생략합니다.

위키 백과 :

정수가 [-u … u] 범위에있을 때, S를 비트 벡터로 나타내고 FFT를 사용하여 컨볼 루션을 수행함으로써 3SUM은 시간 O (n + u lg u)에서 풀 수 있습니다.

이것은 문제를 해결하기에 충분합니다 :).

무엇 매우 중요한 것은 (N 로그 n)은 0과의 수로 복잡성이 O이고, 사람의하지 카운트 (같은 배열로 제공 될 수있다 [1,5,9,15]). 세트에 산술 진행이 있는지 확인하는 것은 1의 수라는 용어가 어렵고 1999 년 현재 그 논문에 따르면 O (n ² ) 보다 빠른 알고리즘 은 알려져 있지 않으며 존재하지 않는 것으로 추측됩니다. 이것을 고려하지 않은 모든 사람들은 공개 된 문제를 해결하려고합니다.

관련이없는 다른 흥미로운 정보 :

하한:

쉬운 하한은 캔터와 같은 세트 (3 진수 확장에 1을 포함하지 않는 1.1.3 ^ n-1의 숫자)입니다. 밀도는 n ^ (log_3 2)입니다 (0.631 경). 따라서 집합이 너무 크지 않은지 확인한 다음 모든 쌍을 확인하는 것만으로는 O (n log n)를 얻을 수 없습니다. 시퀀스를 더 똑똑하게 조사해야합니다. 더 나은 하한이 여기 에 인용 됩니다 -n ^{1-c / (log (n)) ^ (1/2)} 입니다. 이것은 캔터 세트가 최적 이 아님을 의미 합니다.

상한-내 오래된 알고리즘 :

큰 n의 경우, 산술 진행을 포함하지 않는 {1,2, …, n}의 서브 세트는 최대 n / (log n) ^ (1/20) 요소를 갖는 것으로 알려져 있습니다. 산술 진행의 트리플에서 종이 는 더 많은 것을 입증합니다. 세트는 n * 2 ²⁸ * (log log n / log n) ^1/2 요소를 초과 할 수 없습니다 . 따라서 해당 범위가 달성되었는지 확인하고 그렇지 않은 경우 순진하게 쌍을 확인하십시오. 이것은 O (n ² ) 보다 빠른 O (n ² * log log n / log n) 알고리즘 입니다. 불행히도 “On triples …”은 Springer에 있지만 첫 페이지를 볼 수 있으며 Ben Green의 설명은 28 페이지, 정리 24 페이지에서 볼 수 있습니다 .

그건 그렇고, 논문은 1999 년부터 처음 언급 한 것과 같은 해이므로 첫 번째 논문이 그 결과를 언급하지 않은 이유 일 것입니다.

답변

이것은 해결책이 아니라 Olexiy가 생각한 것과 비슷한 생각입니다.

나는 최대 수의 시퀀스를 생성하면서 놀고 있었고, 모두 매우 흥미 롭습니다. 최대 125 자리를 얻었으며 가능한 한 많은 ‘1’비트를 삽입하려고 시도한 첫 3 개의 숫자입니다.

11011000011011000000000000001101100001101100000000000000000000000000000000000000000000000110110000110110000000000000011011000011011
10110100010110100000000000010110100010110100000000000000000000000000000000000000000000000101101000101101000000000000101101000101101
10011001010011001000000000010011001010011001000000000000000000000000000000000000000000010011001010011001000000000010011001010011001

그것들은 모두 프랙탈입니다 (제한이 주어지면 너무 놀랍지 않습니다). 문자열이 특성을 가진 프랙탈 이 아닌 경우 거꾸로 생각하는 것이있을 수 있습니다 . 반복적 인 패턴이 있어야합니까?

이 숫자를 설명하는 더 나은 용어에 대한 베타 덕분입니다.

최신 정보:
아아, 그것은 충분히 큰 초기 문자열로 시작할 때 패턴이 무너지는 것처럼 보입니다 : 10000000000001 :

100000000000011
10000000000001101
100000000000011011
10000000000001101100001
100000000000011011000011
10000000000001101100001101
100000000000011011000011010000000001
100000000000011011000011010000000001001
1000000000000110110000110100000000010011
1000000000000110110000110100000000010011001
10000000000001101100001101000000000100110010000000001
10000000000001101100001101000000000100110010000000001000001
1000000000000110110000110100000000010011001000000000100000100000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011
1000000000000110110000110100000000010011001000000000100000100000000000001101
100000000000011011000011010000000001001100100000000010000010000000000000110100001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011001000000000000000000000010010000010000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001001000000000000000000000000000000000000110010000000000000000000000100100000100000011
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001000001000000110000000000001

답변

O (n ^ 2)처럼 보이는 간단한 접근 방식이 실제로 O (n ln (n))와 같이 더 나은 결과를 얻을 것으로 생각합니다. 테스트하는 데 가장 오래 걸리는 시퀀스 (주어진 n)는 트리오를 포함하지 않는 시퀀스이며 시퀀스에있을 수있는 1의 수에 심각한 제한을 둡니다.

나는 몇 가지 손짓하는 논쟁을 생각해 냈지만 깔끔한 증거를 찾지 못했습니다. 나는 어둠 속에서 찌를 것입니다. 그 대답은 교수가 너무 오랫동안 명백 해져 왔지만 학생들에게는 너무 어렵다는 것을 알고있는 매우 영리한 생각입니다. (그것을 다루거나 강의를 잤다.)

답변

개정 : 2009-10-17 23:00

나는 이것을 2 천만 개의 문자열과 같이 많은 수로 실행 했으며이 알고리즘은 O (n logn)이 아니라고 생각합니다. 그럼에도 불구하고, 그것은 충분히 멋진 구현이며 실제로 빠르게 실행되도록 많은 최적화를 포함합니다. 25 초 미만의 24 진수 이하의 이진 문자열 배열을 모두 평가합니다.

0 <= L < M < U <= X-1오늘 초의 관찰 내용 을 포함하도록 코드를 업데이트했습니다 .

실물

이것은 개념적으로 내가 대답 한 다른 질문 과 유사합니다 . 이 코드는 또한 일련의 세 가지 값을보고 삼중 항이 조건을 만족하는지 여부를 결정했습니다. 다음은 C # 코드입니다.

using System;
using System.Collections.Generic;

namespace StackOverflow1560523
{
    class Program
    {
        public struct Pair<T>
        {
            public T Low, High;
        }
        static bool FindCandidate(int candidate,
            List<int> arr,
            List<int> pool,
            Pair<int> pair,
            ref int iterations)
        {
            int lower = pair.Low, upper = pair.High;
            while ((lower >= 0) && (upper < pool.Count))
            {
                int lowRange = candidate - arr[pool[lower]];
                int highRange = arr[pool[upper]] - candidate;
                iterations++;
                if (lowRange < highRange)
                    lower -= 1;
                else if (lowRange > highRange)
                    upper += 1;
                else
                    return true;
            }
            return false;
        }
        static List<int> BuildOnesArray(string s)
        {
            List<int> arr = new List<int>();
            for (int i = 0; i < s.Length; i++)
                if (s[i] == '1')
                    arr.Add(i);
            return arr;
        }
        static void BuildIndexes(List<int> arr,
            ref List<int> even, ref List<int> odd,
            ref List<Pair<int>> evenIndex, ref List<Pair<int>> oddIndex)
        {
            for (int i = 0; i < arr.Count; i++)
            {
                bool isEven = (arr[i] & 1) == 0;
                if (isEven)
                {
                    evenIndex.Add(new Pair<int> {Low=even.Count-1, High=even.Count+1});
                    oddIndex.Add(new Pair<int> {Low=odd.Count-1, High=odd.Count});
                    even.Add(i);
                }
                else
                {
                    oddIndex.Add(new Pair<int> {Low=odd.Count-1, High=odd.Count+1});
                    evenIndex.Add(new Pair<int> {Low=even.Count-1, High=even.Count});
                    odd.Add(i);
                }
            }
        }

        static int FindSpacedOnes(string s)
        {
            // List of indexes of 1s in the string
            List<int> arr = BuildOnesArray(s);
            //if (s.Length < 3)
            //    return 0;

            //  List of indexes to odd indexes in arr
            List<int> odd = new List<int>(), even = new List<int>();

            //  evenIndex has indexes into arr to bracket even numbers
            //  oddIndex has indexes into arr to bracket odd numbers
            List<Pair<int>> evenIndex = new List<Pair<int>>(),
                oddIndex = new List<Pair<int>>();
            BuildIndexes(arr,
                ref even, ref odd,
                ref evenIndex, ref oddIndex);

            int iterations = 0;
            for (int i = 1; i < arr.Count-1; i++)
            {
                int target = arr[i];
                bool found = FindCandidate(target, arr, odd, oddIndex[i], ref iterations) ||
                    FindCandidate(target, arr, even, evenIndex[i], ref iterations);
                if (found)
                    return iterations;
            }
            return iterations;
        }
        static IEnumerable<string> PowerSet(int n)
        {
            for (long i = (1L << (n-1)); i < (1L << n); i++)
            {
                yield return Convert.ToString(i, 2).PadLeft(n, '0');
            }
        }
        static void Main(string[] args)
        {
            for (int i = 5; i < 64; i++)
            {
                int c = 0;
                string hardest_string = "";
                foreach (string s in PowerSet(i))
                {
                    int cost = find_spaced_ones(s);
                    if (cost > c)
                    {
                        hardest_string = s;
                        c = cost;
                        Console.Write("{0} {1} {2}\r", i, c, hardest_string);
                    }
                }
                Console.WriteLine("{0} {1} {2}", i, c, hardest_string);
            }
        }
    }
}

주요 차이점은 다음과 같습니다.

솔루션의 철저한 검색
이 코드는이 알고리즘에 대해 해결하기 가장 어려운 입력을 찾기 위해 강력한 데이터 세트를 생성합니다.
모든 솔루션과 가장 어려운 솔루션
이전 질문의 코드는 파이썬 생성기를 사용하여 모든 솔루션을 생성했습니다. 이 코드는 각 패턴 길이에 대해 가장 어려운 것을 표시합니다.
스코어링 알고리즘
이 코드는 중간 요소에서 왼쪽 및 오른쪽 가장자리까지의 거리를 확인합니다. 파이썬 코드는 합계가 0보다 크거나 작은 지 테스트했습니다.
후보에 대한 수렴
현재 코드는 후보를 찾기 위해 중간에서 가장자리로 작동합니다. 이전 문제의 코드는 가장자리에서 중간 방향으로 작동했습니다. 이 마지막 변경으로 성능이 크게 향상되었습니다.
짝수 및 홀수 풀 사용
이 기록이 끝날 때의 관측치에 따라 코드는 짝수의 짝수 쌍의 쌍을 검색하여 L과 U를 찾아 M을 고정시킵니다. 이렇게하면 사전 계산 정보로 검색 횟수가 줄어 듭니다. 따라서이 코드는 FindCandidate의 메인 루프에서 두 가지 수준의 간접 지향성을 사용하며 각 중간 요소에 대해 FindCandidate에 대해 두 번의 호출이 필요합니다. 짝수는 한 번, 홀수는 한 번입니다.

일반적인 아이디어는 데이터의 원시 표현이 아니라 인덱스 작업을하는 것입니다. 1이 나타나는 배열을 계산하면 알고리즘이 데이터 길이에 비례하는 시간이 아니라 데이터의 1 수에 비례하는 시간으로 실행됩니다. 이것은 표준 변환입니다. 문제를 동일하게 유지하면서 더 빠른 작업을 가능하게하는 데이터 구조를 만듭니다.

결과가 오래되었습니다. 제거되었습니다.

편집 : 2009-10-16 18:48

계산할 하드 데이터를 대표하는 다른 응답에서 약간의 신뢰를 얻은 yx의 데이터에서 이러한 결과를 얻었습니다 … 나는 이것을 제거했습니다. 오래되었습니다.

이 데이터가 내 알고리즘에 가장 어려운 것은 아니므로 yx의 프랙탈이 해결하기 가장 어렵다는 가정이 잘못되었다고 생각합니다. 특정 알고리즘에 대한 최악의 경우는 알고리즘 자체에 달려 있으며 다른 알고리즘에서 일관성이 없을 것입니다.

편집 : 2009-10-17 13:30

이것에 대한 추가 관찰.

먼저, 0과 1의 문자열을 1의 각 위치에 대한 인덱스 배열로 변환하십시오. 배열 A의 길이가 X라고 가정하면 목표는

0 <= L < M < U <= X-1

그런

A[M] - A[L] = A[U] - A[M]

또는

2*A[M] = A[L] + A[U]

A [L] 및 A [U]는 짝수로 계산되므로 (짝수, 홀수) 또는 (홀수, 짝수)가 될 수 없습니다. A []를 홀수 및 짝수 풀로 분할하고 홀수 및 짝수 후보 풀에서 A [M]에서 일치하는 항목을 차례로 검색하여 일치 검색을 개선 할 수 있습니다.

그러나 이것은 알고리즘 개선보다 성능 최적화에 가깝습니다. 비교 횟수는 줄어들어야하지만 알고리즘 순서는 동일해야합니다.

2009-10-18 00:45 수정

또 다른 최적화는 후보를 짝수와 홀수로 분리하는 것과 같은 맥락에서 발생합니다. 세 개의 인덱스는 3의 배수 (a, a + x, a + 2x-mod 3은 a, x에 관계없이 0)에 추가해야하므로 L, M 및 U를 mod 3 값으로 분리 할 수 있습니다 :

실제로, 이것을 짝수 / 홀수 관측 값과 결합하여 mod 6 값으로 분리 할 수 있습니다.

등등. 이것은 추가적인 성능 최적화를 제공하지만 알고리즘 속도 향상은 제공하지 않습니다.

답변

아직 해결책을 찾지 못했습니다 :(,하지만 몇 가지 아이디어가 있습니다.

우리가 역 문제에서 시작한다면 어떻게 될까요? 최대 개수 1과 균일 한 간격의 트리오없이 시퀀스를 구성하십시오. 최대 1의 개수가 o (n)임을 증명할 수 있으면 1의 목록 만 반복하여 추정치를 향상시킬 수 있습니다.

답변

도움이 될 수 있습니다 ….

이 문제는 다음과 같이 줄어 듭니다.

양의 정수의 시퀀스가 주어지면, 접두사와 접미사로 분할 된 연속 된 서브 시퀀스를 찾아서 서브 시퀀스의 접두사의 합이 서브 시퀀스의 접미사의 합과 같도록하십시오.

예를 들어, 일련의를 제공 [ 3, 5, 1, 3, 6, 5, 2, 2, 3, 5, 6, 4 ], 우리의 서브 찾을 것 [ 3, 6, 5, 2, 2]접두사와 [ 3, 6 ]접두사의 합 9과의 접미사 [ 5, 2, 2 ]의 접미사의 합을 9.

축소는 다음과 같습니다.

0과 1의 시퀀스가 주어지고 맨 왼쪽부터 시작하여 오른쪽으로 계속 이동하십시오. 다른 것이 발생할 때마다 이전의 움직임이 발생한 이후의 움직임 수를 기록하고 그 숫자를 결과 시퀀스에 추가하십시오.

예를 들어의 시퀀스가 주어진 [ 0, 1, 1, 0, 0, 1, 0, 0, 0, 1 0 ]경우 감소가 발견 [ 1, 3, 4]됩니다. 이 축소에서 연속 하위 시퀀스 [ 1, 3, 4], 접두사 [ 1, 3]와 합 4과 접미사 [ 4 ]와 합을 계산 4합니다.

이 축소는에서 계산 될 수 있습니다 O(n).

불행히도 여기서 어디로 가야할지 모르겠습니다.