레머 코드

수학에서, 특히 조합에서, 레머 코드는 n개의 숫자 시퀀스의 각각의 가능한 순열을 인코딩하는 특별한 방법이다.이것은 번호 순열을 매기기 위한 계획의 한 예로서 반전 표의 예다.

레머 코드는 데릭 헨리 레머를 지칭하여 붙여진 이름이지만 적어도 1888년부터는 그 코드가 알려져 있었다.^[1][2]

코드

Lehmer 코드는 다음과 같은 사실을 이용한다.

$\displaystyle n!=n\datable (n-1)\cdots \cdots \cdots \cdatable 2\cd$

n개의 숫자의 순열만일 순열 σ이 1, …, n의 영상의 순서(sequence₁, …, σ_n)에 의해 지정된다면, 그것은 n개의 숫자의 순서에 의해 인코딩되지만, 모든 숫자가 한 번만 사용되어야 하기 때문에 그러한 순서가 모두 유효한 것은 아니다.대조적으로 여기서 고려되는 인코딩은 n개의 값 집합에서 첫 번째 숫자를 선택하고, n - 1의 고정된 값 집합에서 다음 숫자를 선택하고, 따라서 하나의 고정 값만 허용되는 마지막 숫자까지 가능성의 수를 감소시킨다. 이들 집합에서 선택한 숫자의 모든 순서는 단일 순열을 암호화한다.여러 인코딩을 정의할 수 있지만, Lehmer 코드는 몇 가지 유용한 속성을 추가로 가지고 있다; 그것은 시퀀스다.

${\displaystyle L(\sigma )=(L(\sigma )_{1},\ldots,L(\sigma )_{n}\quad{\where}\cext}}}\quad L(\sigma )_{i}=#\j}i:\j}}}$

즉, L(σ)이라는 _i용어는 σ_i 오른쪽의₁ (σ, …, σ_n)의 항 수를 0과 n - i 사이의 숫자로 계산하여 n + 1 - i가 서로 다른 값을 허용한다.

i < j와 σ_i >이_j 있는 지수(i,j)의 쌍을 σ의 반전이라고 하며, L(σ)_i은 i가 고정되고 다양한 j가 있는 역전수(i,j)를 카운트한다.L(σ)₁ + L(σ)₂ + L(() + L(σ)은 _nσ의 총 반전 횟수로서, 순열을 ID 순열로 변환하는 데 필요한 인접 전이의 수이기도 하다.그 레메르 코드의 다른 속성 − 나는 위치에서 나는 비슷한 리를 상징하는 것은 두개의 순열의 인코딩의 사전 편집 명령은 바로 그들의 순서(σ1,…, σn)로, 코드에서 어떤 값 0은 순열(즉, σi 이상 어떤 σj에 그 오른쪽)에서 오른쪽에서 왼쪽으로 최소를 나타내는 것으로, 값을 n 같은이 포함되어 있다.ght-to-left maximum, 그리고 σ의 Lehmer 코드는 사전순으로 n의 순열 목록에서 그 위치를 나타내는 요인 번호 시스템과 일치한다(0부터 시작하는 위치 번호).

이 인코딩의 변형은 고정 i가 아닌 고정 j에 대한 인버션(i,j)을 계산하거나, 인덱스 i가 작은 것이 아니라 고정 값 σ이_j 작은 인버전을 계산하거나, 인버젼이 아닌 비인버전을 계산하여 얻을 수 있다. 반면, 인코딩의 일부 속성은 근본적으로 다른 유형의 인코딩을 생성하지는 않는다.그에 상응하여 변하다특히 고정된 작은 값 σ의_j 역행은 perm의 역행표를 주는데, 역행렬의 레흐메르 코드라고 볼 수 있다.

인코딩 및 디코딩

n개 객체의 순열이 다르다는 것을 증명하는 일반적인 방법은 첫 번째 객체를 n개의 다른 방법으로, 다음 객체를 n - 1개의 다른 방법으로, 다음 객체를 n - 1개의 다른 방법으로 선택할 수 있다는 것을 관찰하는 것이다(첫 번째와 같은 숫자를 선택하는 것은 금지되기 때문에), 다음 2개의 다른 방법(현재 금지된 값이 두 개 있기 때문에).각 단계에서 이 선택의 자유를 숫자로 변환하면 주어진 순열의 레머 코드를 찾는 인코딩 알고리즘을 얻는다.개체가 숫자로 귀속된다고 가정할 필요는 없지만 개체는 개체 집합의 전체 순서가 필요하다.있는 그 점에서(그래서 그들은 위치보다 앞에 일어나지는 않는다 나는)지만, 개체 σi 실제로 선택보다 더 작다 이용할 수 있는 개체의 수.( 불가피하게도 전서구 등 특정 자세 j>에서;i,(i,j 나타나야 한다)이 될 것이다 inversion, 이래로 그 숫자 코드 0에서 시작하도록 해당 번호는 각 개체를 인코딩하기에 σi. 파악h는 이 숫자가 실제로 L(σ)임을 보여준다._i

각 개체를 인코딩하기 위한 이 숫자는 직접 카운팅(직접 역 카운팅 또는 지정된 개체보다 작은 개체 수, 집합의 0부터 시작하는 시퀀스 번호)을 위치에서 사용할 수 없는 개체로 수정하여 찾을 수 있다.실제로 더 효율적이지는 않지만 제자리에 있는 또 다른 방법은 언급된 시퀀스 번호로 각 개체를 나타냄으로써 얻은 {0, 1, … n - 1}의 순열로 시작하여 각 항목 x에 대해 왼쪽에서 오른쪽으로 순서대로 x보다 큰 모든 항목(여전히 f를 반영하기 위해)에서 1을 빼서 항목을 오른쪽으로 수정하는 것이다.x에 해당하는 객체를 더 이상 사용할 수 없는 행위).알파벳 순으로 정렬된 문자의 순열 B,F,A,G,D,E,C에 대한 Lehmer 코드는 먼저 1,5,0,6,3,4,2의 순열 번호 목록을 제공하며, 이는 연속적으로 변형된다.

${\displaystyle{\begin{행렬}\mathbf{1}&5&, 0&, 6&, 3&, 4&, 2\\1&,\mathbf{4}&0&, 5&, 2&, 3&, 1\\1&, 4&,\mathbf{0}&4&, 2&, 3&, 1\\1&, 4&, 0&,\mathbf{3}&1&, 2&, 0\\1&, 4&, 0&, 3&,\mathbf{1}&2&, 0\\1&, 4&, 0&, 3&, 1&,\mathbf{1}&0\\1&, 4&, 0&, 3&.앰프, 1&, 1&,\mathbf{0}\\\end{매트릭스}}}$

여기서 최종 라인은 Lehmer 코드(각 라인에서 볼드체 요소의 오른쪽에 있는 큰 항목에서 1을 빼서 다음 라인을 형성함)이다.

레머 코드를 주어진 집합의 순열로 디코딩하는 경우, 후자 절차는 역전될 수 있다: 각 항목 x에 대해 오른쪽에서 왼쪽으로 x보다 크거나 같은 모든 항목(현재)에 1을 추가하여 항목을 수정한다. 마지막으로 {0, 1, n - 1}의 순열 결과를 순서 번호로 해석한다(추가되는 양).{1, 2, …n}의 순열을 찾는 경우 각 항목마다 1개씩.또는 Lehmer 코드의 항목은 왼쪽에서 오른쪽으로 처리될 수 있으며, 위에 표시된 대로 요소의 다음 선택을 결정하는 숫자로 해석된다. 이 경우 선택한 각 요소가 제거되는 사용 가능한 요소의 목록을 유지관리해야 한다.In the example this would mean choosing element 1 from {A,B,C,D,E,F,G} (which is B) then element 4 from {A,C,D,E,F,G} (which is F), then element 0 from {A,C,D,E,G} (giving A) and so on, reconstructing the sequence B,F,A,G,D,E,C.

조합 및 확률에 대한 응용 프로그램

상대계급의 독립성

그 레메르 코드는 데카르트의 제품에[n]×[n− 1]×이[k]은 k-element 세트를 가리키⋯ ×[2]×[1]{\displaystyle[n]\times[n-1]\times \cdots \times[2]\times[1]},({\displaystyle\와 같이{0,1,\ldots ,k-1\}}. 그 결과의 대칭 군 Sn에서 bijection 이 전투복 아래 distri을 정의합니다.bution on S_n, 성분 L(component L)은 [_in - i]에 균일하게 분포된 랜덤 변수를 정의하며, 이러한 랜덤 변수는 데카르트 제품의 서로 다른 인자에 대한 투영이기 때문에 상호 독립적이다.

오른쪽에서 왼쪽으로 가는 미니마 수 및 최대값 수

정의 : 순서 u=(u_k)_1≤k≤n에서 u가_k i>k, 즉 그 오른쪽에 있는 각 요소 u보다_i 완전히 작을 경우(resp. maximum) 랭크 k에 좌우 최소(resp. maximum)가 있다.

B(k)를 놓아라.H(k)는 "등급 k에 좌우 최소(resp. maximum)" 이벤트인 경우, 즉, B(${\displaystyle k_{}}$)는 등급 k에서 좌우 최소(resp. maximum)를 나타내는$$$$S n {\$displaystyle$\scriptstyle \{\$mathfrak{S}$_{n$}}}}$ 순열 집합이다.우리는 분명히 가지고 있다.

${\displaystyle \{\omega \in B(k)\}\왼쪽 오른쪽 화살표 \{L(k,\omega )=0\}\quad {\\text{and}\\cH(k)\}\왼쪽 오른쪽 화살표 \{L(k,\omega)=k-1\}}}}$

따라서_b N(Ω) (resp)이라는 숫자가 된다.순열 Ω에 대한 좌우 최소값(resp. maximum)의_h N(Ω)은 각각 1/k의 파라미터를 갖는 독립 베르누이 랜덤 변수의 합으로 기록할 수 있다.

${\displaystyle N_{b}(\omega )=\sum _{1\leq k\leq n}\1\\\!1_{B(k)}\quad N_{b}(\text &and}})=\sum _{1\leq k\n}\!1_{H(k)}}}}}}}}}}}}}}}}}}}}}.$

실제로 L(${\displaystyle \mathrm{k}}$)이${\displaystyle }$[${\displaystyle }$1${\displaystyle }$, ${\displaystyle k}$ ${\displaystyle ]}$, ${\$,k$]\],}$에 대한 획일적인 법칙을 따르고 있기 때문에

${\displaystyle \mathb {P}(B(k)=\mathb {P}(L)=0)=\mathb {P}(H(k)=\mathb {P}(L(k)=k-1)={\tfrac {1}{k}.}$

베르누이 랜덤 변수 1 ${\displaystyle 1_{}}$ $){\$ 1$\\\!1_{B(k)}}}$의 생성 함수는 다음과$$ 같다.

${\displaystyle G_{k}={\frac {k-1+s}{k},}$

따라서 N의_b 생성함수는

${\displaystyle G(s)=\prod _{k=1}^{n}G_{k}\ =\\\frac {s^{\overline{n}}}{n!}}}$

(상승 요인 표기법 사용) 첫 번째 종류(부호화되지 않음)의 스털링 번호 생성 함수에 대한 제품 공식을 복구할 수 있다.

비서 문제

이는 최적의 정지 문제, 결정 이론, 통계 및 적용 확률의 고전으로서, 레머 코드의 첫 번째 요소를 통해 무작위 순열이 점차적으로 밝혀지고, and(k)=n과 같은 요소 k에서 정확히 정지하는 것이 목표인 반면, 이용 가능한 유일한 정보(레머 코드의 k 첫 값)는 다음과 같다.σ(k)를 계산하기에 충분하지 않다.

덜 수학적인 단어로: 일련의 n명의 지원자들이 차례로 면접을 본다.면접관은 최고의 지원자를 채용하되, 다음 지원자를 면접하지 않고 즉석에서 ("채용" 또는 "채용하지 않음") 결정을 내려야 한다.

따라서 면접관은 k^th 지원자의 순위를 알고 있으므로, 자신의 k^th 결정을 내리는 순간, 면접관은 르메르 코드의 k 첫 번째 요소만 알고 있을 뿐, 그 요소들을 모두 알아야 충분한 정보를 얻을 수 있다.최적의 전략(즉, 우승 확률을 극대화하는 전략)을 결정하기 위해서는 레머 코드의 통계적 특성이 중요하다.

보도에 따르면 요하네스 케플러는 결심을 굳히고 예비 신부 11명 중 1명을 제2의 아내로 뽑으려던 시기에 이 비서 문제를 친구의 친구에게 분명히 폭로했다고 한다.그의 첫 결혼은 자신이 상담받지 못한 채 성사된 불행한 결혼이었고, 따라서 그는 자신이 올바른 결정에 도달할 수 있을지에 대해 매우 염려하고 있었다.^[3][4]

유사개념

두 개의 유사한 벡터가 사용되고 있다.그 중 하나는 예를 들어 울프램 알파에 의해 역전 벡터라고 불리는 경우가 많다.또한 반전(구체 수학) § 반전 관련 벡터를 참조하십시오.

참조

참고 문헌 목록

• Mantaci, Roberto; Rakotondrajao, Fanja (2001), "A permutation representation that knows what "Eulerian" means", Discrete Mathematics and Theoretical Computer Science (4): 101–108, archived from the original on 2004-11-16
• Knuth, Don (1981), The art of computer programming, vol. 3, Reading: Addison-Wesley, pp. 12–13