제한된 시퀀스-인덱스 매핑

StackOverflow https://stackoverflow.com/questions/369417

  •  21-08-2019
  •  | 
  •  

문제

일련의 시퀀스를 연속적인 정수에 매핑하는 방법에 대해 궁금합니다.

모든 시퀀스는 다음 규칙을 따릅니다.

A_0 = 1
A_n >= 1
A_n <= max(A_0 .. A_n-1) + 1

저는 그러한 시퀀스가 ​​주어지면 테이블 조회를 위해 정수를 계산하고 테이블에 인덱스가 주어지면 시퀀스를 생성할 수 있는 솔루션을 찾고 있습니다.

예:길이가 3인 경우 유효한 시퀀스는 5개입니다.다음 맵을 수행하는 빠른 기능(바람직하게는 양방향)이 좋은 솔루션이 될 것입니다.

1,1,1   0
1,1,2   1
1,2,1   2
1,2,2   3
1,2,3   4
  • 연습의 요점은 유효한 시퀀스와 셀 간의 1-1 매핑이 포함된 압축 테이블을 얻는 것입니다.
  • 세트의 크기는 가능한 고유 시퀀스 수에 의해서만 제한됩니다.
  • 지금은 시퀀스의 길이가 얼마나 될지 모르지만 미리 알려진 작은 <12 상수일 것입니다.
  • 조만간 이에 대해 다루겠지만, 그동안 커뮤니티가 "재미"를 가질 수 있도록 버릴 것입니다.

이것들은 다른 유효한 시퀀스입니다

1,1,2,3,2,1,4
1,1,2,3,1,2,4
1,2,3,4,5,6,7
1,1,1,1,2,3,2

이것들은 아니다

1,2,2,4
2,
1,1,2,3,5

와 연관되다 이것

도움이 되었습니까?

해결책

자연 시퀀스 인덱싱이 있지만 계산하기가 쉽지 않습니다.

A_0 = 1이므로 n>0에 대해 A_n을 찾아보겠습니다.

인덱싱은 2단계로 수행됩니다.

1 부:

A_n = max(A_0 ..A_n-1) + 1.이 장소에 전화하세요 단계.

  • 계단에는 연속된 숫자(2,3,4,5,...)가 있습니다.
  • 단계가 아닌 곳에서는 1부터 k보다 작은 인덱스를 가진 단계 수까지 숫자를 입력할 수 있습니다.

각 그룹은 1이 단계이고 0이 비단계인 이진 문자열로 표시될 수 있습니다.예:001001010은 112aa3b4c, a<=2, b<=3, c<=4인 그룹을 의미합니다.그룹은 이진수로 인덱싱되므로 그룹 인덱싱이 자연스럽습니다.0에서 2^길이 - 1.그룹 이진 표현의 값을 호출할 수 있습니다. 단체 주문.

2 부:

그룹 내부의 인덱스 시퀀스.그룹은 단계 위치를 정의하므로 단계가 아닌 위치의 숫자만 가변적이며 정의된 범위에서는 가변적입니다.이를 통해 가변 위치의 사전순 순서를 사용하여 해당 그룹 내에서 주어진 그룹의 순서를 쉽게 색인화할 수 있습니다.

한 그룹의 시퀀스 수를 계산하는 것은 쉽습니다.1^i_1 * 2^i_2 * 3^i_3 * ... 형식의 수입니다.

결합:

이는 두 부분으로 구성된 키를 제공합니다. <Steps, Group> 그런 다음 이를 정수에 매핑해야 합니다.그러기 위해서는 특정 값보다 작은 순서를 갖는 그룹에 몇 개의 시퀀스가 ​​있는지 찾아야 합니다.이를 위해 먼저 주어진 길이의 그룹에 몇 개의 시퀀스가 ​​있는지 찾아 보겠습니다.이는 모든 그룹을 통과하여 시퀀스 수를 합산하거나 반복과 유사하게 계산할 수 있습니다.T(l, n)을 길이가 l인 시퀀스의 개수(A_0은 생략함)라고 가정합니다. 여기서 첫 번째 요소의 최대값은 n+1일 수 있습니다.보유보다 :

T(l,n) = n*T(l-1,n) + T(l-1,n+1)
T(1,n) = n

왜냐하면 l + n <= sequence length + 1 ~가 있다sequence_length^2/2 쉽게 계산할 수 있는 T(l,n) 값.

다음은 주어진 값보다 작거나 같은 순서의 그룹에서 시퀀스 수를 계산하는 것입니다.이는 T(l,n) 값을 합산하여 수행할 수 있습니다.예:순서 <= 1001010 이진수인 그룹의 시퀀스 수는 다음과 같습니다.

T(7,1) +         # for 1000000
2^2 * T(4,2) +   # for 001000
2^2 * 3 * T(2,3) # for 010

최적화:

이렇게 하면 매핑이 제공되지만 핵심 부분을 결합하기 위한 직접 구현은 다음과 같습니다. >O(1) 기껏해야.반면, Steps 키 부분은 작으며 범위를 계산하여 Groups 각각 Steps 값, 조회 테이블은 이를 다음으로 줄일 수 있습니다. O(1).

위 공식에 대해 100% 확신할 수는 없지만 그와 비슷할 것입니다.

이러한 설명과 반복을 사용하면 함수 순서 -> 색인 및 색인 -> 순서를 만드는 것이 가능합니다.하지만 그렇게 사소한 것은 아닙니다 :-)

다른 팁

나는 정렬하지 않은 해시가 중요하다고 생각합니다.

A0은 항상 0으로 시작하므로 시퀀스를 12진수를 사용하는 숫자로 생각하고 10진수를 조회 키로 사용할 수 있다고 생각합니다.(아직도 이에 대해 확신하지 못합니다).

이것은 파일에 이러한 값이 저장되어 있고 해당 행을 함수에 전달한다고 가정하여 작업을 수행할 수 있는 Python 함수입니다.

def valid_lines(lines):
    for line in lines:
        line = line.split(",")
        if line[0] == 1 and line[-1] and line[-1] <= max(line)+1:
            yield line

lines = (line for line in open('/tmp/numbers.txt'))
for valid_line in valid_lines(lines):
    print valid_line

시퀀스가 주어지면 이를 정렬한 다음 정렬된 시퀀스의 해시를 테이블의 인덱스로 사용합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top