스택 정렬식 순열

수학 및 컴퓨터 과학에서 스택 정렬 순열(트리 순열이라고도 함)^[1]은 내부 저장소가 단일 스택 데이터 구조로 제한된 알고리즘에 의해 요소를 정렬할 수 있는 순열이다.스택 정렬 가능한 순열은 순열 패턴 231을 포함하지 않는 순열이며, 이는 카탈루냐 숫자에 의해 계수되며, Dyck 경로와 이진 트리를 포함한 계수 기능이 동일한 많은 다른 결합 물체와 바이어싱될 수 있다.

스택으로 정렬

스택을 사용하여 입력 시퀀스를 정렬하는 문제는 Knuth(1968)에 의해 처음 제기되었다. Knuth는 다음과 같은 선형 시간 알고리즘을 제공했다(나중에 가장 가까운 모든 작은 값 문제에 대한 알고리즘과 밀접하게 관련됨).

• 빈 스택 초기화
• 각 입력 값 x에 대해:
  • 스택이 비어 있지 않고 x가 스택의 맨 위 항목보다 큰 경우 스택을 출력으로 이동하십시오.
  • 스택에 x 밀어넣기
• 스택이 비어 있지 않은 동안 해당 스택을 출력으로 이동하십시오.

크누스는 이 알고리즘이 일부 입력 시퀀스를 올바르게 정렬하고, 다른 입력 시퀀스를 정렬하지 못하는 것을 관찰했다.예를 들어, 순서 3,2,1은 정확하게 정렬된다: 세 원소는 모두 스택에 밀어넣은 다음, 1,2,3의 순서로 튀어진다.그러나 순서 2,3,1은 정확하게 정렬되지 않는다: 알고리즘이 먼저 2를 누르고, 더 큰 입력 값 3이 보이면 뻥튀기하여 2가 그 후가 아니라 1 이전으로 출력되게 한다.

이 알고리즘은 비교 정렬이기 때문에, 그 성패는 입력 시퀀스의 숫자 값에 따라 달라지는 것이 아니라 입력 순서의 상대적 순서에 따라서만 달라진다. 즉, 입력은 동일한 길이의 정렬된 시퀀스에서 입력을 형성하는 데 필요한 순열에 의해 설명될 수 있다.크누스는 이 알고리즘이 정확히 순열 패턴 231: 세 가지 요소 x, y, z를 포함하지 않는 순열로 분류하는 순열을 z < x < y>와 함께 입력에 나타나는 순열로 특징지었다.더욱이, 그는 알고리즘이 입력을 정렬하지 못하면 그 입력을 단일 스택으로 정렬할 수 없다고 보았다.

더 복잡한 스택 시스템과 관련 데이터 구조를 사용한 분류 작업에 대한 후속 연구를 고무할 뿐만 아니라,^[2] 크누스의 연구는 금지된 패턴에 의해 정의된 순열 패턴과 순열 클래스에 대한 연구를 시작했다.

반대 및 열거

크누스의 정렬 알고리즘이 스택 정렬형 순열을 Dyck 언어로 정렬하면서 수행하는 푸시 앤 팝의 순서는 푸시를 왼쪽 괄호로, 팝을 오른쪽 괄호로 재해석하면 균형 잡힌 괄호 문자열이 만들어진다.게다가 모든 다이크 문자열은 이런 식으로 스택 정렬 가능한 순열에서 유래하며, 각각의 다른 스택 정렬 순열은 서로 다른 다이크 문자열을 생산한다.이러한 이유로 길이 n의 스택 정렬 가능 순열 수는 길이 2n의 Dyck 문자열 수인 카탈루냐 숫자와 동일하다.

${\displaystyle C_{n}={\frac {1}{n+1}:{n+1}{\binom {2n}{n}}}.}$^[3]

스택 정렬 순열은 (라벨이 부착되지 않은) 이진수로 직접 번역될 수 있으며, 계산 기능이 카탈로니아 숫자의 순서인 또 다른 결합 등급이다.이진 트리는 노드를 왼쪽에서 오른쪽으로 번호를 매긴 다음, 이 숫자를 먼저 트리의 사전 순서 통과(루트 먼저, 왼쪽 하위 트리, 오른쪽 하위 트리)로 방문하여 각 하위 트리 내에서 반복적으로 반복적으로 반복하여 방문하는 순서로 변환할 수 있다.역방향에서 스택 정렬 가능한 순열은 나무의 첫 번째 값 x가 나무의 뿌리에 해당하는 트리로 해독할 수 있으며, 다음 x - 1 값은 반복적으로 해독하여 뿌리의 왼쪽 아이에게 주고, 나머지 값은 다시 반복적으로 해독하여 오른쪽 아이를 줄 수 있다.^[1]

몇 가지 다른 등급의 순열도 스택 정렬 순열과 편향될 수 있다.예를 들어, 패턴 132, 213 및 312를 피하는 순열은 순열을 역전시키거나 순열에서 각 값 x를 n + 1 - x로 교체하거나 두 가지 작업을 조합하여 스택 정렬(231-avi딩) 순열에서 각각 형성될 수 있다.312 회피 순열은 231 회피 순열의 역행이기도 하며, 스택에 대한 푸시-입력-팝-투-출력 연산의 순서에 의해 신분 순열에서 형성될 수 있는 순열이라 하여 스택 실현 가능한 순열이라고 불려왔다.^[4]크누스(1968)가 지적한 바와 같이 123-Avoiding과 321-Avoiding 순열도 스택 정렬 순열과 직접적인 관련이 적음에도 불구하고 같은 계수 기능을 가지고 있다.

랜덤 스택 정렬 순열

로템(1981)은 주어진 길이의 모든 순열 중에서 무작위로 선택한 스택 정렬 순열의 특성을 조사한다.이러한 순열에서 가장 긴 내림차순의 예상 길이는 ${\displaystyle \pi }$ n${\displaystyle }$- ${\displaystyle \mathrm{O}}$( 1${\displaystyle }$) ${\displaystyle {\sqrt{\pi$ n$}-O(1)}$이며$,$ 제한되지 않은 무작위 순열(예상 길이는 약 ${\displaystyle 2n\sqrt{}}$ ${\$ 2${\sqrt{n}}).$가장 긴 오름차순의 예상 길이는 제한되지 않은 순열(${\displaystyle \mathrm{n}}$+ ${\displaystyle 1)/2\mathrm{}}$ ${\displaystyle (n+1)/2}$과 훨씬 더 강하게 다르다$.$ 모든 이전 값보다 큰 순열 내의 예상 값 수는${\displaystyle 3}$ -${\displaystyle }6{\displaystyle \mathrm{}}$/ (${\displaystyle n}$ + ${\displaystyle 2}$)$${\$displaystyle 3-6/(n+2$)으로$,$ 로그보다 작다.제한되지 않은 순열에 대한 ithmic 값그리고 예상되는 반전 수는 $제한$되지 않은 순열에 대한$$ $value{\displaystyle \mathrm{}}$(${\displaystyle {n\mathrm{}}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$/ 2 )${\displaystyle \Teta (n^{3/2})$ 값과 대조적으로$$is${\displaystyle }$(${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ )${\displaystyle \Teta (n^{2})$이다.

추가 속성

모든 순열은 순열 그래프를 정의하며, 순열의 요소가 정점이고 순열에 의해 반전된 요소의 쌍을 연결하는 그래프.스택 정렬 가능한 순열의 순열 그래프는 아주 완벽하다.^[4]

순열 p의 각 요소 i에 대해, b를_i i보다 왼쪽에 있고 큰 다른 요소의 수로 정의한다.p는 모든 i에 대해 b_i - b b_{i + 1} 1일 경우에만 스택 정렬이 가능하다.^[1]

알고리즘

너트(1977)는 스택 정렬 가능한 순열과 이진 트리 사이의 편차를 사용하여 각 이진 트리에 대한 숫자 순위를 정의하고, 트리의 순위("순위")를 계산하고 지정된 순위("순위")로 트리를 계산하는 효율적인 알고리즘을 구축한다.

Micheli & Rossin(2006)은 순열 작업에 대한 두 가지 편집 작업을 정의했다: 삭제(순열 패턴을 만드는 것)와 그 역순이다.나무와 순열 사이에 동일한 대응성을 사용하여, 그들은 이러한 연산이 나무의 가장자리 수축과 그 반대편에 대응한다는 것을 관찰했다.트리에서의 거리 편집에 다항식 시간 동적 프로그래밍 알고리즘을 적용함으로써, 그들은 두 개의 스택 정렬 가능한 순열(따라서 가장 긴 공통 패턴) 사이의 편집 거리를 다항식 시간에서 찾을 수 있다는 것을 보여주었다.이 기술은 나중에 분리 가능한 순열의 가장 긴 공통 패턴을 찾기 위한 알고리즘으로 일반화되었다.^[5] 그러나 가장 긴 공통 패턴 문제는 임의 순열의 경우 NP-완전성이다.^[6]

메모들

참조

• Avis, David; Newborn, Monroe (1981), "On pop-stacks in series", Utilitas Mathematica, 19: 129–140, MR 0624050.
• Bóna, Miklós (2002), "A survey of stack-sorting disciplines", Electronic Journal of Combinatorics, 9 (2): A1, MR 2028290.
• Bouvel, Mathilde; Rossin, Dominique; Vialette, Stéphane (2007), "Longest common separable pattern among permutations", Combinatorial Pattern Matching (CPM 2007), Lecture Notes in Computer Science, vol. 4580, Springer, pp. 316–327, doi:10.1007/978-3-540-73437-6_32.
• Felsner, Stefan; Pergel, Martin (2008), "The complexity of sorting with networks of stacks and queues", Proc. 16th Eur. Symp. Algorithms, Karlsruhe, Germany, pp. 417–429, doi:10.1007/978-3-540-87744-8_35, ISBN 978-3-540-87743-1.
• Knott, Gary D. (February 1977), "A numbering system for binary trees", Communications of the ACM, 20 (2): 113–115, doi:10.1145/359423.359434.
• Knuth, Donald (1968), "Vol. 1: Fundamental Algorithms", The Art of Computer Programming, Reading, Mass.: Addison-Wesley.
• Micheli, Anne; Rossin, Dominique (2006), "Edit distance between unlabeled ordered trees", Theoretical Informatics and Applications, 40 (4): 593–609, arXiv:math/0506538, doi:10.1051/ita:2006043, MR 2277052.
• Rosenstiehl, Pierre; Tarjan, Robert E. (1984), "Gauss codes, planar Hamiltonian graphs, and stack-sortable permutations", Journal of Algorithms, 5 (3): 375–390, doi:10.1016/0196-6774(84)90018-X, MR 0756164
• Rotem, D. (1981), "Stack sortable permutations", Discrete Mathematics, 33 (2): 185–196, doi:10.1016/0012-365X(81)90165-5, MR 0599081.
• Tarjan, Robert (April 1972), "Sorting Using Networks of Queues and Stacks", Journal of the ACM, 19 (2): 341–346, doi:10.1145/321694.321704.