Permutation

Original article: w:Permutation

For other uses, see Permutation (disambiguation).

"nPr" redirects here. For other uses, see NPR (disambiguation).

Each of the six rows is a different permutation of three distinct balls

수학(mathematics)에서, 집합(set)의 순열(permutation)은, 대략 말해서, 수열(sequence) 또는 선형 순서(linear order)로 그의 구성원의 배열, 또는, 만약 집합이 이미 순서화되었으면, 그의 원소의 재정렬입니다. 단어 "순열"은 역시 순서화 집합의 선형 순서를 변경하는 동작 또는 과정을 참조합니다.

순열은, 순서에 관계없이 집합의 일부 구성원을 선택하는 조합(combination)과 다릅니다. 예를 들어, 튜플(tuple)로 쓰일 때, 집합 {1,2,3}의 여섯 순열: 즉, (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), 및 (3,2,1)이 있습니다. 이것들은 이들 세-원소 집합의 가능한 순서의 모두입니다. 그의 글자가 다른 단어의 애너그램(anagram)은 역시 순열입니다: 문자가 이미 원래 단어로 정렬되어 있고, 애너그램은 문자를 다시 정렬한 것입니다. 유한 집합(finite set)의 순열의 연구는 조합론(combinatorics)과 그룹 이론(group theory)의 분야에서 중요한 주제입니다.

순열은 수학의 거의 모든 각 가지, 및 과학의 많은 다른 분야에서 연구됩니다. 컴퓨터 과학(computer science)에서, 그것들은 정렬 알고리듬(sorting algorithm)을 분석; 양자 물리학(quantum physics)에서, 입자의 상태를 묘사, 및 생물학에서, RNA 수열을 묘사하는 것에 대해 사용됩니다.

n 구별되는 대상의 순열의 숫자는 n 팩토리얼(factorial)이며, 보통 n!으로 쓰이며, 이것은 n 보다 작거나 같은 모든 양의 정수의 곱을 의미합니다.

기술적으로, 집합(set) S의 순열은 S에서 그 자신으로의 전단사(bijection)로 정의됩니다. 즉, 그것은, 모든 각 원소가 이미지(image) 값으로 정확히 한 번 발생하는, S에서 S로의 함수(function)입니다. 이것은, 각 원소 s가 대응하는 f(s)에 의해 대체되는, S의 원소의 재배열과 관련됩니다. 예를 들어, 위에서 언급한 순열 (3,1,2)는 다음으로 정의된 함수 $\alpha$에 의해 묘사됩니다:

$\alpha (1)=3,\quad \alpha (2)=1,\quad \alpha (3)=2$.

집합의 모든 순열의 모음은 집합의 대칭 그룹(symmetric group)으로 불리는 그룹(group)을 형성합니다. 그룹 연산은 합성(composition) (두 개의 주어진 재배열을 연속으로 수행함)이며, 이것은 또 다른 재배열의 결과입니다. 순열의 속성은 집합 원소의 본성에 의존하지 않기 때문에, 그것은 종종 순열 연구에 고려되는 집합 $\{1,2,\ldots ,n\}$의 순열입니다.

기초 조합론에서, k-순열, 또는 부분 순열(partial permutation)은 집합으로부터 선택된 k 구별되는 원소의 순서화 배열입니다. k가 집합의 크기와 같을 때, 이것들은 집합의 순열입니다.

In the popular puzzle Rubik's cube invented in 1974 by Ernő Rubik, each turn of the puzzle faces creates a permutation of the surface colors.

History

알-감디(Al-Khalil) (717–786), 아랍의 수학자(Arab mathematician)이자 암호-해독가(cryptographer)는 Book of Cryptographic Messages를 썼습니다. 그것은 모음이 있거나 없는 모든 가능한 아랍어(Arabic) 단어를 나열하기 위해 순열과 조합(permutations and combinations)을 처음 사용을 포함하고 있습니다.

n 대상의 순열의 숫자를 결정하기 위한 규칙은 인도 문화에서 적어도 1150년 경부터 알려져 있었습니다: 인도의 수학자 바스카라(Bhaskara II)에 의해 릴라바티(Lilavati)는 다음으로 번역되는 절을 포함합니다:

단위에 의해 시작하고 증가하는 및 자릿수의 숫자에 계속되는 산술적 급수의 곱셈의 곱은 특정 그림과 함께 숫자의 변화일 것입니다.

1677년에 페이비언 스테드먼(Fabian Stedman)은 벨소리 변경(change ringing)에서 벨의 순열의 숫자를 설명할 때 팩토리얼을 묘사했습니다. 두 벨로부터 시작하여: "먼저, 두 가지는 두 방법으로 변하게 되는 것으로 수용되어야 합니다": 그는 1 2와 2 1을 보여줌으로써 묘사합니다. 그는, 그런-다음, 3벨과 함께 그것을 설명합니다: "세 개에서 생성되는 두 그림의 세 배"가 있으며 이것을 다시 묘사됩니다. 그의 설명은 "3을 버리고, 1 2가 남을 것이고; 2를 버리고, 1 3이 남을 것이고; 1을 버리고 2 3이 남을 것"을 포함합니다. 그는, 그런-다음, 4벨로 이동하고 세 개의 네 개의 서로 다른 집합이 있음을 보여주는 버리는 인수를 반복합니다. 효과적으로 이것은 재귀 프로세스입니다. 그는 "버리는(casting away)" 방법을 사용하여 다섯 벨과 함께 계속하고 결과로써 생기는 120 조합을 표로 만듭니다. 이 시점에서 그는 포기하고 다음을 말합니다:

이제 이들 방법의 본질은 하나의 숫자에 대한 변화가 모든 더 적은 숫자에 대한 변화를 이해한다는 그런 것, ... 하나의 숫자에 대한 변화의 완전한 울림은 모든 더 작은 숫자에서 완전한 울림을 하나의 전체 몸체로 결합함으로써 형성되는 것처럼 보이는 정도까지입니다;

스테드먼은 순열에 대한 고려를 넓혔습니다; 그는 알파벳과 문자 및 20의 마구간으로부터 말의 순열의 숫자를 고려하는 것으로 나아갔습니다.

겉으로 보기에 관계가 없는 수학적 질문에서 첫 번째 경우는, 조제프 루이 라그랑주(Joseph Louis Lagrange)가, 다항 방정식의 연구에서, 방정식의 근(roots)의 순열의 속성이 그것을 해결하기 위한 가능성과 관련되었다는 것을 관찰할 때, 1770년경 발생된 순열의 도움과 함께 연구되었습니다. 연구의 줄은 궁극적으로 결과로써 생기는데, 에바리스트 갈루아(Évariste Galois)의 연구를 통해, 갈루아 이론(Galois theory)에서, 이것은 제곱근에 의해 (하나의 미지수에서) 다항 방정식을 푸는 것에 관한 무엇이 가능하고 불가능지에 대한 완전한 설명을 제공합니다. 현대 수학에서, 문제를 이해하는 것이 그것과 관련된 특정 순열을 연구하는 것을 요구하는 많은 비슷한 상황이 있습니다.

Permutations without repetitions

순열의 가장 간단한 예제는 n 항목을 n 장소로 배열하는 가능한 방법의 숫자를 고려하는 반복없이 순열입니다. 팩토리얼(factorial)은 반복을 포함하지 않는 집합에서 순열의 숫자를 정의하는 데 특별한 응용을 가집니다. 숫자 n!은 "n 팩토리얼"이라고 읽히며, 정확하게 n 항목을 새로운 순서로 재배열할 수 있는 방법의 숫자입니다. 예를 들어, 오렌지, 사과, 배의 세 가지 과일을 가지면, 언급된 순서대로 먹거나 그것들을 (예를 들어, 사과, 배, 그다음에 오렌지) 변경할 수 있습니다. 순열의 정확한 숫자는 그때에 $3!=1\cdot 2\cdot 3=6$입니다. 그 숫자는 항목 (n)의 숫자가 증가할수록 극단적으로 커집니다.

유사한 방식에서, n 대상에서 r 항목의 배열의 숫자는 부분 순열(partial permutation)로 고려됩니다. 그것은 $nPr$로 쓰이고 ("n 순열 r"로 읽음), 숫자 $n(n-1)\cdots (n-r+1)$와 같습니다 (역시 $n!/(n-r)!$로 쓰입니다).

Definition

수학 텍스트에서, 소문자 그리스 문자를 사용하여 순열을 나타내는 것이 관례적입니다. 공통적으로 $\alpha$ 및 $\beta$, 또는 $\sigma ,\tau$ 및 $\pi$가 사용됩니다.

순열은 집합 S에서 자체 위로의 일대일-대응으로 정의될 수 있습니다. n 원소를 갖는 집합의 모든 순열은 $S_{n}$로 표시되는 대칭 그룹(symmetric group)을 형성하며, 여기서 그룹 연산(group operation)은 함수 합성(function composition)입니다. 따라서 그룹 $S_{n}$에서 두 순열 $\pi$ 및 $\sigma$에 대해, 네 개의 그룹 공리가 유지됩니다:

1. 클로저(Closure): 만약 $\pi$와 $\sigma$가 $S_{n}$ 안에 있으면 $\pi \sigma$도 마찬가지입니다.
2. 결합성(Associativity): 임의의 세 순열 $\pi ,\sigma ,\tau \in S_{n}$에 대해, $(\pi \sigma )\tau =\pi (\sigma \tau )$입니다.
3. 항등원(Identity): 항등 순열이 있고, $\mathrm {id}$로 나타내고 모든 $x\in S$에 대해 $\mathrm {id} (x)=x$에 의해 정의됩니다. 임의의 $\sigma \in S_{n}$에 대해, $\operatorname {id} \sigma =\sigma \operatorname {id} =\sigma$입니다.
4. 역-가능성(Invertibility): 모든 각 순열 $\pi \in S_{n}$에 대해, $\pi \pi ^{-1}=\pi ^{-1}\pi =\operatorname {id}$가 되도록 $\pi ^{-1}\in S_{n}$이 존재합니다.

일반적으로 두 순열의 합성은 교환적(commutative)이지 않습니다, 즉, $\pi \sigma \neq \sigma \pi$입니다.

이 관점에서, 순열은 집합의 재배열을 수행하는 함수이고 재배열 그 자체는 아니라는 점을 강조합니다. 더 오래되고 보다 기본적인 관점은 순열이 재배열임을 유지합니다. 때때로 이들 두 관점을 구별하기 위해, 단어 능동(active) 및 수동(passive) 형식, 또는 더 오래된 용어 치환(substitutions) 및 순열(permutations)이 사용됩니다.

순열은 하나 이상의 서로소 순환(cycles), 즉, 일부 원소에 대한 순열의 적용을 반복적으로 추적함으로써 발견되는, 궤도(orbits)로 분해될 수 있습니다. 예를 들어 $\sigma (7)=7$에 의해 정의된 순열 $\sigma$은 1-순환, $(\,7\,)$을 가지지만, $\pi (2)=3$ 및 $\pi (3)=2$에 의해 정의된 순열 $\pi$는 2-순환, $(\,2\,3\,)$을 가집니다 (구문에 대한 자세한 것에 대해 아래의 순환 표기법(Cycle notation) 섹션을 참조하십시오). 일반적으로, 길이 k, 즉 k 원소로 구성되는 순환은 k-순환이라고 불립니다.

1-순환 $(\,x\,)$에서 원소는 순열의 고정된 점(fixed point)으로 불립니다. 고정된 점을 갖지 않은 순열은 교란(derangement)으로 불립니다. 2-순환은 전치(transpositions)로 불립니다; 그러한 순열은 단지 두 원소의 자리를 바꾸며, 나머지는 고정된 채로 남겨집니다.

Notations

순열을 원소별, 즉, 조각별(piecewise) 함수로 쓰는 것이 번거롭기 때문에, 여러 표기법이 그들을 보다 간결하게 표현하기 위해 개발되어 왔습니다. 순환 표기법(Cycle notation)은 그의 간결성 및 그것이 순열의 구조를 투명하게 만드는 사실에 기인하여 많은 수학자에 대해 대중적인 선택입니다. 달리 명시되지 않은 한, 이 기사에서 사용된 표기법이지만, 다른 표기법이 특히 응용 분야에서 여전히 널리 사용되고 있습니다.

Two-line notation

코시(Cauchy)의 두-줄 표기법(two-line notation)에서, 우리는 첫 번째 행에서 S의 원소를 나열하고, 각각의 하나에 대해 그의 이미지는 두 번째 행에서 그것 아래에 나열합니다. 예를 들어, 집합 S = {1,2,3,4,5}의 특정 순열은 다음과 같이 쓸 수 있습니다:

$\sigma ={\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}};$

이것은 σ가 σ(1) = 2, σ(2) = 5, σ(3) = 4, σ(4) = 3, 및 σ(5) = 1을 만족한다는 것을 의미합니다. S의 원소는 첫 번째 행에서 임의의 순서에서 나타날 것입니다. 이 순열은 다음으로 역시 쓸 수 있습니다:

$\sigma ={\begin{pmatrix}3&2&5&1&4\\4&5&1&2&3\end{pmatrix}},$

또는

$\sigma ={\begin{pmatrix}5&1&4&3&2\\1&2&3&4&5\end{pmatrix}}.$

One-line notation

만약 S의 원소에 대해 "자연스러운" 순서가 있으면, 말하자면 $x_{1},x_{2},\ldots ,x_{n}$, 두-줄 표기법의 첫 번째 행에 대해 이것을 사용합니다:

$\sigma ={\begin{pmatrix}x_{1}&x_{2}&x_{3}&\cdots &x_{n}\\\sigma (x_{1})&\sigma (x_{2})&\sigma (x_{3})&\cdots &\sigma (x_{n})\end{pmatrix}}.$

이 가정 아래에서, 우리는 첫 번째 행을 생략하고 순열을 다음으로 한-줄 표기법(one-line notation)으로 쓸 수 있을 것입니다:

$(\sigma (x_{1})\;\sigma (x_{2})\;\sigma (x_{3})\;\cdots \;\sigma (x_{n}))$,

즉, S의 순서화 배열입니다. 주의는 한-줄 표기법과 아래에 설명된 순환 표기법(cycle notation)을 구분하기 위해 기울어져야 합니다. 수학 문헌에서, 공통적인 사용법은 한-줄 표기법에 대해 괄호를 생략하는 것이지만, 사이클 표기법에 대해 괄호를 사용하는 것입니다. 한-줄 표기법은 순열의 단어(word) 표현으로 역시 불립니다. 위의 예제는 그런-다음 2 5 4 3 1이 되는데 왜냐하면 자연스러운 순서 1 2 3 4 5가 첫 번째 행에 대해 가정될 것이기 때문입니다. (만약 일부가 두 개 이상의 자릿수를 가지면 오직 이들 엔터디를 분리하기 쉼표를 사용하는 것이 전형적입니다.) 이 형식은 보다 간결하고, 기초 조합론(combinatorics) 및 컴퓨터 과학(computer science)에서 공통입니다. 그것은 응용에서 특히 유용하며 여기서 S의 원소 또는 순열이 더 크거나 더 작게 비교되는 것입니다.

Cycle notation

순환 표기법은 집합의 원소에 대한 순열을 반복적으로 적용하는 효과를 설명합니다. 그것은 순열을 순환(cycles)의 곱으로 표현합니다; 왜냐하면 구별되는 순환은 서로소이기 때문이며, 이것은 "서로소(disjoint) 순환으로의 분해"로 참조됩니다.

순환 표기법에서 순열 $\sigma$을 적기 위해, 우리는 다음처럼 진행합니다:

1. 여는 괄호를 쓴 다음 $S$의 임의의 원소 x를 선택하고 그것을 뒤에 적습니다: $(\,x$
2. 그런-다음 $x$의 궤도를 추적하고, 즉, $\sigma$의 연속적인 적용 아래에 그의 값을 뒤에 적습니다:$(\,x\,\sigma (x)\,\sigma (\sigma (x))\,\ldots$
3. 값이 x로 돌아갈 때까지 반복하고 x 대신에 닫는 괄호를 적습니다: $(\,x\,\sigma (x)\,\sigma (\sigma (x))\,\ldots \,)$
4. 이제 S의 원소 y를 계속하십시오. 여전히 뒤에 쓰는 것이 아니라, 같은 방법에서 진행하십시오: $(\,x\,\sigma (x)\,\sigma (\sigma (x))\,\ldots \,)(\,y\,\ldots \,)$
5. S의 모든 원소가 순환에 쓰일 때까지 반복하십시오.

모든 각 새로운 순환에 대해 시작하는 점은 다른 방법에서 선택될 수 있으므로, 일반적으로 같은 순열에 대해 많은 다른 순환 표기법이 있습니다; 위의 예제에 대해 우리는 다음을 가집니다:

${\begin{pmatrix}1&2&3&4&5\\2&5&4&3&1\end{pmatrix}}={\begin{pmatrix}1&2&5\end{pmatrix}}{\begin{pmatrix}3&4\end{pmatrix}}={\begin{pmatrix}3&4\end{pmatrix}}{\begin{pmatrix}1&2&5\end{pmatrix}}={\begin{pmatrix}3&4\end{pmatrix}}{\begin{pmatrix}5&1&2\end{pmatrix}}.$

1-순환은 순환 표기법에서 종종 생략되는데, 문맥이 명확하게 제공되어야 합니다; 임의의 사이클에서 나타나지 않는 S 안의 임의의 원소 x에 대해, 우리는 암시적으로 $\sigma (x)=x$를 가정합니다. 오직 1-순환로 구성되는, 항등 순열(identity permutation)은 단일 1-cycle (x), 숫자 1, 또는 id에 의해 나타내어질 수 있습니다.

순환 표기법의 편리한 특징은 우리가 순열의 순환에서 원소의 순서를 단순히 뒤집음으로써 순열의 역을 찾을 수 있다는 것입니다. 예를 들어,

$[(\,1\,2\,5\,)(\,3\,4\,)]^{-1}=(\,5\,2\,1\,)(\,4\,3\,)$

Canonical cycle notation (a.k.a. standard form)

일부 조합론적 문맥에서, 순환 및 (서로소) 순환 자체의 원소에 대해 특정 순서를 고정하는 것에 유용합니다. 미클로즈 보나(Miklós Bóna)는 다음 순서화 선택을 정식의 순환 표기법(canonical cycle notation)으로 부릅니다:

• 각 순환에서 가장-큰 원소가 첫 번째로 나열됩니다
• 순환은 그들 첫 번째 원소의 증가하는 순서에서 정렬됩니다

예를 들어, (312)(54)(8)(976)은 정식의 순환 표기법에서 순열입니다. 정식의 순환 표기법은 일-순환을 생략하지 않습니다.

리처드 피터 스탠리(Richard P. Stanley)는 순열의 "표준 표현(standard representation)"으로 표현의 같은 선택을 부릅니다. 그리고 마틴 아이그너(Martin Aigner)는 같은 개념에 대해 용어 "표준 형식(standard form)"을 사용합니다. 세르게이 커테에프(Sergey Kitaev)는 역시 "표준 형식" 용어를 사용하지만, 두 가지 선택을 모두 뒤집습니다; 즉, 각각의 순환은 그 최소 원소를 첫 번째에 나열하고 순환은 그들의 가장 작은, 즉, 첫 번째 원소의 감소하는 순서로 정렬됩니다.

Composition of permutations

두 순열의 합성을 나타내기 위한 두 가지 방법이 있습니다. $\sigma \cdot \pi$는 집합의 임의의 원소 x를 $\sigma (\pi (x))$로 매핑하는 함수입니다. 가장 오른쪽 순열이 첫 번째 인수에 적용되는 것에 주목하십시오, 왜냐하면 함수 적용이 쓰이는 방법이기 때문입니다.

함수 합성(function composition)이 결합적(associative)이므로, 순열에 대한 합성 연산도 그렇습니다: $(\sigma \pi )\tau =\sigma (\pi \tau )$입니다. 그러므로, 둘 보다 많은 순열의 곱은 그룹화를 표현하기 위해 괄호 추가없이 보통 쓰입니다; 그들은 역시 합성을 나타내기 위해 점 또는 다른 기호없이 보통 쓰입니다.

일부 저자는 첫 번째 작용하는 가장 왼쪽 인수를 선호하지만, 해당 끝에 대한 순열은 그들의 인수의 오른쪽에, 종종 지수로서 반드시 쓰여야 하며, 여기서 x에 작용하는 σ는 x^σ로 쓰입니다; 그런-다음 곱은 x^σ·π = (x^σ)^π에 의해 정의됩니다. 어쨌든, 이것은 순열을 곱하는 다른 규칙을 제공합니다; 이 기사는 가장 오른쪽 순열이 첫 번째로 적용되는 정의를 사용합니다.

Other uses of the term permutation

순서화 배열로 순열의 개념은 순열은 아니지만 문헌에서 순열(permutations)로 불려 왔던 여러 일반화를 인정합니다.

k-permutations of n

기초 조합론 교과서에서 때때로 사용되는, 용어 순열(permutation)의 더 약한 의미는 어떤 원소도 두 번 이상 나오지 않지만, 주어진 집합으로부터 모든 원소를 사용하는 요구-사항없이, 순서화 배열을 지정합니다. 이들은 특별한 경우를 제외하고 순열이 아니지만, 순서화 배열 개념의 자연스러운 일반화입니다. 사실, 이 사용은 크기 n의 주어진 집합으로부터 취해진 원소의 고정된 길이 k의 배열을 고려하는 것을 종종 포함합니다. 다른 말로, 이들 n의 k-순열은 n-집합의 k-원소 부분집합의 다른 순서화 배열입니다 (때때로 오래된 문헌에서 변형(variations)으로 불립니다). 이들 대상은 부분 순열(partial permutations) 또는 반복없는 수열(sequences without repetition)으로 역시 알려져 있고, "순열"을 의미하는, 보다 공통적인, 다른 대상과의 혼란을 피하는 용어입니다. 그러한 $n$의 $k$-순열의 숫자는 $P_{k}^{n}$, $_{n}P_{k}$, $^{n}P_{k}$, $P_{n,k}$, 또는 $P(n,k)$으로 그러한 기호에 의해 다양하게 나타내고, 그의 값은 곱에 의해 주어집니다

$P(n,k)=\underbrace {n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)} _{k\ \mathrm {factors} }$,

여기서 k > n일 때 0이고, 그렇지 않으면 다음과 같습니다:

${\frac {n!}{(n-k)!}}.$

그 곱은 $n$이 비-음의 정수라는 가정없이 잘 정의되어 있고 마찬가지로 조합론 밖에서 중요성이 있습니다: 그것은 포흐하머 기호(Pochhammer symbol) $(n)_{k}$ 또는 $n$의 $k$-번째 떨어지는 팩토리얼 거듭제곱 $n^{\underline {k}}$으로 알려져 있습니다.

용어 순열(permutation)의 이러한 사용은 용어 조합(combination)과 밀접하게 관련됩니다. n-집합 S의 k-원소 조합은 S의 k 원소 부분집합이며, 이것의 원소는 순서화되지 않습니다. S의 모든 k 원소 부분집합을 취하고 모든 가능한 방법에서 그들 각각을 순서화함으로써, 우리는 S의 모든 k-순열을 얻습니다. n-집합의 k-조합의 숫자, C(n,k)는, 따라서 다음에 의해 n의 k-순열의 숫자와 관련됩니다:

$C(n,k)={\frac {P(n,k)}{P(k,k)}}={\frac {\tfrac {n!}{(n-k)!}}{\tfrac {k!}{0!}}}={\frac {n!}{(n-k)!\,k!}}.$

이들 숫자는 이항 계수(binomial coefficient)로 역시 알려져 있고 ${\binom {n}{k}}$에 의해 표시됩니다.

Permutations with repetition

반복이 허용되는 길이 n의 집합 S의 원소의 순서화 배열은 n-튜플(n-tuples)로 불리지만, 비록 그것이 일반적으로 순열이 아닐지라도, 반복을 갖는 순열(permutations with repetition:중복순열)로 때때로 참조되어 왔습니다. 그들은 일부 문맥에서 알파벳 S에 걸쳐 단어(words)로 역시 불립니다. 만약 집합 S가 k 원소를 가지면, S에 걸쳐 n-튜플의 숫자는 다음입니다:

$k^{n}.$

원소가 n-튜플에서 얼마나 자주 나타날 수 있는지에 대한 제한은 없지만, 만약 원소가 얼마나 자주 나타날 수 있는지에 대한 제한이 정해지면, 이 공식은 더 이상 유효하지 않습니다.

Permutations of multisets

Permutations of multisets

만약 M이 유한 중복집합(multiset)이면, 중복집합 순열(multiset permutation)은 각 원소가 M에서 중복도만큼 정확히 나타나는 M의 원소의 순서화 배열입니다. 일부 반복된 문자를 가지는 단어의 애너그램(anagram)은 중복집합 순열의 예제입니다. 만약 (일부 순서에서 취해진) M의 원소의 중복도가 $m_{1}$, $m_{2}$, …, $m_{l}$이고 그들의 합 (즉, M의 크기)이 n이면, M의 중복집합 순열의 숫자는 다항 계수(multinomial coefficient)에 의해 주어집니다:

${n \choose m_{1},m_{2},\ldots ,m_{l}}={\frac {n!}{m_{1}!\,m_{2}!\,\cdots \,m_{l}!}}={\frac {(\sum _{i=1}^{l}{m_{i}})!}{\prod _{i=1}^{l}{m_{i}!}}}.$

예를 들어, 단어 MISSISSIPPI의 구별되는 애너그램의 숫자는 다음입니다:

${\frac {11!}{1!\,4!\,4!\,2!}}=34650$.

중복집합 M의 k-순열은 각 원소는 M 회 (원소의 중복 숫자)에서 최대 그의 중복도를 나타내는 M의 원소의 길이 k의 수열입니다.

Circular permutations

순열은, 배열로 고려될 때, 때때로 선형적 순서화 배열로 참조됩니다. 이들 배열에서, 첫 번째 원소, 두 번째 원소, 등이 있습니다. 만약, 어쨌든, 대상이 원형의 방식으로 배열되면, 이들 구별되는 순서화가 더 이상 존재하지 않는데, 즉, 배열에서 "첫 번째 원소"가 없으며, 임의의 원소가 배열의 시작으로 고려될 수 있습니다. 원형의 방식에서 대상의 배열은 원형의 순열(circular permutations)로 불립니다. 이들은, 선형 배열의 마지막 원소를 그의 제일 앞쪽으로 이동함으로써 생성되는 등가 관계(Equivalence relation)에 대해, 대상의 보통 순열의 등가 클래스(Equivalence class)로 공식적으로 정의될 수 있습니다.

두 원형 순열은 만약 하나가 다른 것에 대한 회전된 것이면 (즉, 원소의 상대 위치를 변경하지 않고 순환되면) 동등합니다. 네 문자에 대한 다음 두 원형 순열은 같은 것으로 고려됩니다.

                           1                             4
                        4     3                       2     1
                           2                             3

원형 배열은 반-시계-방향으로 읽어야 하므로, 다음 두 개는 동등한 것이 아닌데 왜냐하면 회전이 하나에서 다른 것으로 가져올 수 없기 때문입니다.

                           1                             1
                        4     3                       3     4
                           2                             2

원소 n을 가진 집합 S의 원형 순열의 숫자는 (n - 1)!입니다.

Properties

n 구별되는 대상의 순열의 숫자는 n!입니다.

k 서로소 순환을 갖는 n-순열의 숫자는 c(n, k)로 표시되는 부호없는 첫 번째 종류의 스털링 숫자(Stirling number of the first kind)입니다.

Permutation type

순열의 순환은 집합 $S_{n}$를 분할하므로 순열 $\sigma$의 순환의 길이는 $\sigma$의 순환 유형(cycle type)으로 불리는 n의 분할(partition)을 형성합니다. σ의 모든 각 고정된 점에 대해 순환 유형 "1", 모든 각 전치에 대해 "2", 등이 있습니다. $\beta =(\,1\,2\,5\,)(\,3\,4\,)(6\,8\,)(\,7\,)$의 순환 유형은 (3,2,2,1)이며 이것은 때때로 [1¹2²3¹]으로 보다 간결한 형식에서 쓰입니다.

일반적인 형식은 $[1^{\alpha _{1}}2^{\alpha _{2}}\dotsm n^{\alpha _{n}}]$이며, 여기서 $\alpha _{1},\ldots ,\alpha _{n}$는 각 길이의 순환의 숫자입니다. 특정 유형의 분할의 숫자는 그런-다음 다음에 의해 제공됩니다:

${\frac {n!}{1^{\alpha _{1}}2^{\alpha _{2}}\dotsm n^{\alpha _{n}}\alpha _{1}!\alpha _{2}!\dotsm \alpha _{n}!}}$.

Conjugating permutations

일반적으로, 순환 표기법에서 쓰인 순열을 합성하는 것은 쉽게 설명되는 패턴을 따르지 않습니다 – 합성의 순환은 합성되려는 순환과 다를 수 있습니다. 어쨌든, 순환 구조는 또 다른 순열 $\pi$에 의해 순열 $\sigma$을 켤레하는(conjugating) 특별한 경우에서 보존되며, 이것은 곱 $\pi \sigma \pi ^{-1}$을 형성함을 의미합니다. 여기서, $\pi \sigma \pi ^{-1}$은 $\sigma$의 켤레이고 그의 순환 표기법은 σ에 대해 순환 표기법을 취하고 그것 안에 있는 모든 엔트리에 π를 적용함으로써 얻어질 수 있습니다. 그것은 두 순열이 같은 유형을 가질 때 정확하게 켤레가 됨을 따릅니다.

Permutation order

순열 $\sigma$의 차수는 $\sigma ^{m}=\mathrm {id}$가 되도록 하는 가장-작은 양의 정수 m입니다. 그것은 그의 순환 길이의 최소 공통 배수(least common multiple)입니다. 예를 들어, $(\,1\,3\,2)(\,4\,5\,)$의 차수는 $2\cdot 3=6$입니다.

Parity of a permutation

유한 집합의 모든 각 순열은 전치의 곱으로 표현될 수 있습니다. 비록 주어진 순열에 대해 많은 그러한 표현이 존재할 수 있을지라도, 그것들 모두는 전치의 짝수 또는 홀수를 포함합니다. 따라서 모든 순열은 이 숫자에 따라 짝수 또는 홀수(even or odd)로 분류될 수 있습니다.

이 결과는 각 순열에, $\operatorname {sgn} \sigma$로 쓰이는, 부호를 할당하기 위해 확장될 수 있습니다. 만약 $\sigma$가 짝수이면 $\operatorname {sgn} \sigma =+1$이고 만약 $\sigma$가 홀수이면 $\operatorname {sgn} \sigma =-1$입니다. 그런-다음 두 순열 $\sigma$ 및 $\pi$에 대해

$\operatorname {sgn} (\sigma \pi )=\operatorname {sgn} \sigma \cdot \operatorname {sgn} \pi .$

그것은 $\operatorname {sgn} (\sigma \sigma ^{-1})=+1$임을 따릅니다.

Matrix representation

Composition of permutations corresponds to multiplication of permutation matrices.

우리는 n×n 행렬(matrix)로서 {1, 2, ..., n}의 순열을 나타낼 수 있습니다. 그렇게 하기 위한 두 자연스러운 방법이 있지만, 행렬의 곱셈이 같은 순서에서 순열의 곱셈에 해당하는 것에 대해 오직 하나뿐입니다: 이것은 그의 엔트리 M_i,j는 만약 i = σ(j)이면 1이고, 그렇지 않으면 0인 행렬 M을 σ와 결합시키는 그 하나입니다. 결과 행렬은 각 열과 각 행에서 정확히 하나의 엔트리 1을 가지고, 순열 행렬(permutation matrix)로 불립니다.
여기서 (파일)은 4 원소의 순열에 대해 이들 행렬의 목록입니다. 오른쪽에 케일리 테이블(Cayley table)은 3 원소의 순열에 대해 이들 행렬을 보여줍니다.

Foata's transition lemma

한-줄 및 정식의 순환 표기법 사이에 관계가 있습니다. 정식의 순환 표기법에서 순열 $(\,2\,)(\,3\,1\,)$을 생각해 보십시오. 만약 우리가 그의 순환 괄호를 지우면, 우리는 한-줄 표기법에서 순열 $(2,3,1)$을 얻습니다. 푸아타(Foata)의 전이 보조-정리는 이 대응의 본질을 n-순열 집합에 대한 (그 자체로의) 전단사로 확립합니다. 리처드 스탠리(Richard Stanley)는 이 대응을 근본적인 전단사(fundamental bijection)로 부릅니다.

$f$를 괄호-제거하는 변환으로 놓습니다. $q=f(p)$의 역은 덜 직관적입니다. 한-줄 표기법 $q=q_{1}q_{2}\cdots q_{n}$으로 시작하여, 정식의 순환 표기법에서 첫 번째 순환은 반드시 $q_{1}$으로 시작해야 합니다. 후속 원소가 $q_{1}$보다 더 작은 한, 우리는 같은 순환 안에 있습니다. 두 번째 순환은 $q_{j}>q_{1}$를 만족하는 가장-작은 인덱스 $j$에서 시작합니다. 달리 말해서, $q_{j}$는 그의 왼쪽에 있는 다른 어떤 것보다 크므로, 그것은 왼쪽-에서-오른쪽 최댓값(left-to-right maximum)으로 불립니다. 정식의 순환 표기법에서 모든 각 순환은 왼쪽-에서-오른쪽으로 최댓값으로 시작합니다.

예를 들어, 한-줄 표기법 $(3,1,2,5,4,8,9,7,6)$에서, 5는 3보다 더 큰 첫 번째 원소이므로, 첫 번째 순환은 $(\,3\,1\,2\,)$여야 합니다. 그런-다음 8은 5보다 더 큰 다음 원소이므로, 두 번째 순환은 $(\,5\,4\,)$입니다. 9는 8보다 더 크므로, $(\,8\,)$은 자체에 의해 하나의 순환입니다. 마지막으로, 9는 그의 오른쪽에서 모든 남아있는 원소보다 더 크므로, 마지막 순환은 $(\,9\,7\,6\,)$입니다.

첫 번째 따름정리처럼, 정확히 k 왼쪽-에서-오른쪽 최댓값을 갖는 n-순열의 숫자는 부호없는 첫 번째 종류의 스털링 숫자(Stirling number of the first kind), $c(n,k)$와 역시 같습니다. 게다가, 푸아타의 매핑은 k-약한 초과(excedances)를 갖는 n-순열을 k − 1 상승(ascents)을 갖는 n-순열로 취합니다. 예를 들어, (2)(31) = 321는 (인덱스 1과 2에서) 두 약한 초과를 가지지만, f(321) = 231는 (인덱스 1에서; 즉, 2에서 3까지) 하나의 상승을 가집니다.

Permutations of totally ordered sets

일부 응용에서, 순열되는 집합의 원소는 서로 비교될 것입니다. 이것은 집합 S가 임의의 두 원소가 비교될 수 있도록 전체 순서(total order)를 가짐을 요구합니다. 집합 {1, 2, ..., n}는 보통 "≤" 관계에 의해 전체 순서화되고 따라서 그것이 이들 응용에서 가장 자주 사용되는 집합이지만, 일반적으로, 임의의 전체적으로 순서화된 집합이 수행될 것입니다. 이들 응용에서, 순열의 순서화된 배열은 순열에서 위치에 대해 이야기하기 위해 필요됩니다.

S의 전체 순서화와 직접 관련된 여러 속성이 있습니다.

Ascents, descents, runs and excedances

n의 순열 σ의 오름(ascent)은 다음의 값이 현재의 값보다 더 큰 임의의 위치 i < n입니다. 즉, 만약 σ = σ₁σ₂...σ_n이면, i는 만약 σ_i < σ_i+1이면 오름입니다.

예를 들어, 순열 3452167은 1, 2, 5, 및 6 (위치에서) 오름을 가집니다.

비슷하게, 내림(descent)은 σ_i > σ_i+1을 갖는 위치 i < n이므로, $1\leq i<n$를 갖는 모든 각 i가 σ의 오름 또는 내림 중 하나입니다.

순열의 올라가는 연속(ascending run)은 양쪽 끝에서 확장될 수 없는 순열의 비-빈 상승하는 연속적인 부분-수열입니다; 그것은 연속적인 오름의 최대 수열에 해당합니다 (후자는 빈 것일 수 있습니다: 둘 연속적인 내림의 사이는 여전히 길이 1의 올라가는 연속이 있습니다). 반대로 순열의 증가하는 부분-수열(increasing subsequence)은 반드시 연속적인 것은 아닙니다: 그것은 일부 위치에서 값을 생략함으로써 순열에서 얻어진 원소의 증가하는 수열입니다. 예를 들어, 순열 2453167는 올라가는 연속 245, 3, 및 167을 가지지만, 그것은 증가하는 부분-수열 2367을 가집니다.

만약 순열은 k − 1 내림을 가지면, 그것은 k 올라가는 연속의 합집합이어야 합니다.

k 오름을 갖는 n의 순열의 숫자는 (정의에 의해) 오일러 숫자(Eulerian number) $\textstyle \left\langle {n \atop k}\right\rangle$입니다; 이것은 역시 k 내림을 갖는 n의 순열의 숫자입니다. 일부 저자는 어쨌든 k 올라가는 연속을 갖는 순열의 숫자로 오일러 숫자 $\textstyle \left\langle {n \atop k}\right\rangle$를 정의하며, 이것은 k − 1 내림에 해당합니다.

순열 σ₁σ₂...σ_n의 과잉(excedance)은 σ_j > j을 만족하는 인덱스 j입니다. 만약 부등식이 엄격하지 않으면 (즉, σ_j ≥ j), j는 약한 초과(weak excedance)라고 불립니다. k 초과를 갖는 n-순열의 숫자는 k 내림을 갖는 n-순열의 숫자와 일치합니다.

Inversions

Main article: Inversion (discrete mathematics)

In the 15 puzzle the goal is to get the squares in ascending order. Initial positions which have an odd number of inversions are impossible to solve.

순열 σ의 반전(inversion)은 순열의 엔트리가 반대 순서: $i<j$이고 $\sigma _{i}>\sigma _{j}$에 있는 위치의 쌍 (i, j)입니다. 따라서 하나의 하강은 단지 두 인접 위치에서 반전입니다. 예를 들어, 순열 σ = 23154은 셋의 반전: 엔트리 (2, 1), (3, 1), 및 (5, 4)의 쌍에 대해, (1, 3), (2, 3), 및 (4, 5)를 가집니다.

때때로 반전은 그것의 순서가 역전되는 값의 쌍 (σ_i,σ_j)로 정의됩니다; 이것은 반전의 숫자에 대해 차이를 만들지 않고, (역전된) 이 쌍은 역시 역 순열 σ⁻¹에 대해 위의 의미에서 반전입니다. 반전의 숫자는 순열의 엔트리가 순서가 어긋나는 정도에 대한 중요한 측정입니다; 그것은 σ와 σ⁻¹에 대해 같습니다. k 반전을 갖는 순열을 순서대로 가져오기 위해 (즉, 그것을 항등 순열로 변환하기 위해), 인접 전치(adjacent transposition)를 (그것에 의한 오른쪽-곱셈) 연속적으로 적용함으로써, 항상 가능하고 k 그러한 연산의 순열을 요구합니다. 게다가, 인접한 전치에 대해 합리적인 선택은 효과가 있을 것입니다: 각 단계에서 i와 i + 1의 전치를 선택하는 것으로 충분하며 여기서 i는 (비록 다른 하강을 생성할 수 있을지라도, 전치가 이 특정 하강을 제거하도록) 지금까지 수정된 순열의 하강입니다. 이것은 그러한 전치를 적용하면 반전의 숫자가 1만큼 감소하기 때문에 그렇습니다; 이 숫자가 비-영인 한, 순열은 항등이 아니므로, 그것은 적어도 하나의 하강을 가집니다. 거품 정렬(bubble sort)과 삽입 정렬(insertion sort)은 수열을 순서대로 넣기 위한 이 절차의 특정 인스턴스로 해석될 수 있습니다. 덧붙여서, 이 절차는 임의의 순열 σ가 인접한 전치의 곱으로 쓸 수 있음을 입증합니다; 이것에 대해 우리는 σ를 항등으로 변환하는 그러한 전치의 임의의 수열을 단순히 뒤집을 수 있습니다. 사실, σ를 항등으로 변환할 인접한 전치의 모든 수열을 열거함으로써, 우리는 (역전 후) 인접 전치의 곱으로 σ를 쓰는 최소 길이의 모든 표현의 완전한 목록을 얻습니다.

k 반전을 갖는 n의 순열의 숫자는 마호니안 숫자로 표현되며, 그것은 다음 곱의 전개에서 X^k의 계수입니다:

$\prod _{m=1}^{n}\sum _{i=0}^{m-1}X^{i}=1\left(1+X\right)\left(1+X+X^{2}\right)\cdots \left(1+X+X^{2}+\cdots +X^{n-1}\right),$

이것은 역시 q-팩토리얼 [n]_q! 로 (q를 X로 대체됨과 함께) 알려져 있습니다. 곱의 전개는 Necklace (combinatorics)에서 나타납니다.

$i<j$와 $\sigma (i)>\sigma (j)$를 만족하는 $\sigma \in S_{n},i,j\in \{1,2,\dots ,n\}$라고 놓습니다. 이 경우에서, 반전 $(i,j)$의 가중이 $\sigma (i)-\sigma (j)$라고 말합니다. Kobayashi (2011)는 다음 열거 공식을 입증했습니다:

$\sum _{i<j,\sigma (i)>\sigma (j)}(\sigma (i)-\sigma (j))=|\{\tau \in S_{n}\mid \tau \leq \sigma ,\tau {\text{ is bigrassmannian}}\}$

여기서 $\leq$는 대칭 그룹에서 브뤼아(Bruhat) 순서를 나타냅니다. 이 등급된 부분 순서는 종종 콕서터(Coxeter) 그룹의 맥락에서 나타납니다.

Permutations in computing

Numbering permutations

n의 순열을 나타내는 한 가지 방법은 0 ≤ N < n!를 갖는 정수 N에 의한 것이며, 제공된 편리한 방법은 숫자와 순열의 표시 사이를 순서화된 배열 (수열)로 변환하기 위해 제공됩니다. 이것은 임의적인 순열의 가장 간결한 표시를 제공하고, 컴퓨팅에서 n이 기계어에 포함될 수 있을 만큼 충분히 작을 때 특히 매력적입니다; 32비트 워드에 대해 이것은 n ≤ 12를 의미하고, 64-비트 워드에 대해 이것은 n ≤ 20를 의미합니다. 그 변환은 숫자의 수열 d_n, d_n−1, ..., d₂, d₁의 중간 형식을 통해 수행될 수 있으며, 여기서 d_i는 i보다 작은 비-음의 정수입니다 (우리는 d₁가 항상 0이기 때문에 생략할 수 있지만, 그것의 존재는 순열로의 후속 변환을 더 쉽게 설명하도록 만듭니다). 첫 번째 단계는 그때에 단순히 특정 혼합된 밑수(mixed radix) 표시인 팩토리얼 숫자 시스템(factorial number system)에서 N을 표현하는 것이며, 여기서, n!보다 작은 숫자에 대해, 연속 자릿수에 대해 밑수 (자리 값 또는 곱셈 인수)은 (n − 1)!, (n − 2)!, ..., 2!, 1!입니다. 두 번째 단계는 이 수열을 레머 코드(Lehmer code)로 해석하거나 (거의 동등하게) 반전 테이블로 해석합니다.

Rothe diagram for $\sigma =(6,3,8,1,4,9,7,2,5)$

σi i	1	2	3	4	5	6	7	8	9	Lehmer code
1	×	×	×	×	×	•				d9 = 5
2	×	×	•							d8 = 2
3	×	×		×	×		×	•		d7 = 5
4	•									d6 = 0
5		×		•						d5 = 1
6		×			×		×		•	d4 = 3
7		×			×		•			d3 = 2
8		•								d2 = 0
9					•					d1 = 0
Inversion table	3	6	1	2	4	0	2	0	0

순열 σ에 대해 레머 코드에서 숫자 d_n은 첫 번째 항 σ₁에 대해 선택을 나타내고, 숫자 d_n−1은 집합의 남아있는 n − 1 원소 중에서 두 번째 항 σ₂에 대해 선택을 나타내는 식이고, 이런 식으로 계속됩니다. 보다 정확하게, 각 d_n+1−i은 σ_i 항보다 엄격하게 작은 남아있는 원소의 숫자를 제공합니다. 그것들의 남아있는 원소는 일부 나중에 σ_j 항으로 나타날 수밖에 없으므로, 자릿수 d_n+1−i는 i를 포함하는 반전 (i,j)을 더 작은 인덱스 (i < j와 σ_i > σ_j에 대해 값 j의 숫자)로 셉니다. σ에 대해 반전 테이블은 매우 유사하지만, 여기서 d_n+1−k는 k = σ_j가 반전된 순서로 나타나는 두 값 중 작은 것으로 발생하는 반전 (i,j)의 숫자를 셉니다. 두 인코딩 모두는 n × n 로테 다이어그램 (하인리히 아우구스트 로테(Heinrich August Rothe)의 이름을 따서 지어짐)으로 시각화될 수 있으며, 이것에서 (i,σ_i)의 점은 순열의 엔트리를 표시하고, (i,σ_j)에서 십자형은 반전 (i,j)을 표시합니다; 반전의 정의에 의해, 십자형은 열에서 점 (j,σ_j) 앞과 행에서 점 (i,σ_i) 앞에 둘 다 오는 임의의 사각형에 나타납니다. 레머 코드는 연속 행에서 십자형의 숫자를 나열하고, 반면에 반전 테이블은 연속 열에서 십자형의 숫자를 나열합니다; 그것은 단지 역순열에 대해 레머 코드일 뿐이고, 그 반대의 경우도 마찬가지입니다.

레머 코드 d_n, d_n−1, ..., d₂, d₁을 순서화된 집합 S의 순열로 효과적으로 변환하기 위해, 우리는 증가하는 순서에서 S의 원소의 목록으로 시작하고, i에 대해 1에서 1까지 증가하여 σ_i를 d_n+1−i 다른 것에 의해 앞에 오게 되는 목록에서 원소로 설정하고, 해당 원소를 목록에서 제거할 수 있습니다. 반전 테이블 d_n, d_n−1, ..., d₂, d₁을 해당 순열로 변환하기 위해, 우리는 S의 원소를 가장 큰 것에서 가장 작은 것으로 초기 빈 수열에 삽입하는 동안 d₁에서 d_n까지 숫자를 순회할 수 있습니다; 반전 테이블에서 숫자 d를 사용하는 단계에서, S로부터 원소는 이미 존재하는 d 원소에 의해 앞에 오게 되는 점에서 수열에 삽입됩니다. 대안적으로 우리는 반전 테이블에서 숫자와 반대 순서에서 S의 원소 둘 다를 처리할 수 있으며, n 빈 슬롯 행에서 시작하고, 각 단계에서 S에서 원소를 d 다른 빈 슬롯에 의해 앞에 오게 되는 빈 슬롯에 배치합니다.

연속적인 자연수를 팩토리얼 숫자 시스템으로 변환하는 것은 사전식 순서(lexicographical order)에서 그것들의 수열을 생성하고 (임의의 혼합된 밑수 숫자 시스템을 갖는 경우와 마찬가지로), 나아가서 그것들을 순열로 변환하는 것은 사전식 순서화가 보존되며, 제공된 레머 코드 해석이 사용됩니다 (반전 테이블을 사용하여, 우리는 다른 순서화를 얻으며, 여기서 그것들의 첫 번째 엔트리의 값에 의한 것이 아닌 엔트리 1의 위치에 의해 순열을 비교함으로써 시작합니다). 팩토리얼 숫자 시스템 표시에서 숫자의 합은 순열의 반전의 숫자를 제공하고, 해당 합의 패리티는 순열의 시그니처(signature)를 제공합니다. 게다가, 반전 테이블에서 영들의 위치는 순열의 왼쪽에서-오른쪽 최고 (그 예제에서 6, 8, 9)의 값을 제공하고, 반면 레머 코드에서 영들의 위치는 오른쪽에서-왼쪽으로의 최소 (그 예에서 1, 2, 5 값 중 4, 8, 9 위치)의 위치입니다; 이것은 모든 순열 사이에서 그러한 극단값의 분포를 계산하는 것을 허용합니다. 레머 코드 d_n, d_n−1, ..., d₂, d₁를 갖는 순열이 오름 n − i을 갖는 것과 d_i ≥ d_i+1인 것은 필요충분 조건입니다.

Algorithms to generate permutations

컴퓨팅에서, 주어진 값의 수열의 순열을 생성해야 할 수 있습니다. 이를 수행하기 위한 가장 적합한 방법은 무작위로 선택된 순열을 원하는지, 또는 모든 순열을 원하는지 여부와 후자의 경우에서 특정 순서화가 요구되는지에 따라 다릅니다. 또 다른 질문은 주어진 수열에 있는 엔트리 사이의 가능한 상등을 고려해야 하는지 여부입니다; 만약 그렇다면, 우리는 수열의 오직 구별되는 중복집합 순열을 생성해야 합니다.

n의 순열을 생성하는 확실한 방법은 레머 코드(Lehmer code)에 대해 값을 생성하고 (가능한 n!까지의 정수의 팩토리얼 숫자 시스템(factorial number system) 표시를 사용하여), 그것들을 해당하는 순열로 변환하는 것입니다. 어쨌든, 후자의 단계는 간단하지만 효율적으로 구현하기가 힘든데, 왜냐하면 그것은, 임의의 위치에서, 수열에서 선택하고 그것에서 삭제하는 각각의 n 연산을 요구합니다; 배열(array) 또는 연결된 목록(linked list)과 같은 수열의 명백한 표현의, 둘 다는 변환을 수행하기 위해 약 n²/4 연산을 (다른 이유로) 요구합니다. n이 다소 작을 가능성과 함께 (특히 모든 순열의 생성이 필요되면) 그렇게 문제가 많지는 않지만, 무작위 생성과 시스템적인 생성 둘 다에 대해 훨씬 더 나은 간단한 대안이 있음이 밝혀졌습니다. 이러한 이유로 레머 코드에서 순열로의 변환을 O(n log n) 시간 내에 수행할 수 있도록 하는 특별한 데이터 구조를 사용하는 것은, 비록 확실히 가능할지라도, 유용하지 않은 것 같습니다.

Random generation of permutations

Main article: Fisher–Yates shuffle

주어진 n 값 수열의 무작위 순열(random permutation)을 생성하기 위해, 무작위로 선택된 n 순열을 수열에 적용하거나, 수열의 구별되는 (중복집합) 순열의 집합에서 무작위 원소를 선택하는지 여부는 차이가 없습니다. 이것은 왜냐하면, 심지어 값이 반복되는 경우에서 같은 순열된 수열을 초래하는 n의 많은 구별되는 순열이 있을 수 있을지라도, 그러한 순열의 숫자가 각 가능한 결과에 대해 같기 때문입니다. 숫자 n!의 증가로 인해 큰 n에 대해 실행 불가능하게 되는 시스템적인 생성과 달리, n이 무작위 생성에 대해 작을 것이라고 가정할 이유가 없습니다.

무작위 순열을 생성하는 기본 아이디어는 0 ≤ d_i < i를 (d₁은 항상 0이므로 생략될 수 있음) 만족시키는 정수 d₁,d₂,...,d_n의 수열의 무작위 하나를 생성하고 그것을 전단사(bijective) 대응을 통해 순열로 변환하는 것입니다. 후자의 대응에 대해 우리는 (반전) 수열을 레머 코드로 해석할 수 있고, 이것은 로널드 피셔(Ronald Fisher)와 프랭크 예이츠(Frank Yates)에 의해 1938년에 처음 출판된 생성 방법을 제공합니다. 당시에는 컴퓨터 구현이 문제가 아니었지만, 이 방법은 위에서 설명된 레머 코드에서 순열로 효율적으로 변환하기 위한 어려움을 겪습니다. 이것은 다른 전단사 대응을 사용함으로써 해결될 수 있습니다: d_i를 사용하여 (i 값을 감소하기 위해) 수열의 남아있는 i 원소 중에서 원소를 선택한 후, 원소를 제거하고 나아가서 원소를 한 위치 아래로 이동함으로써 수열을 압축하는 대신, 우리는 원소를 마지막 남아있는 원소와 교환(swaps)합니다. 따라서 선택을 위해 남아있는 원소는, 비록 그것들이 원래 수열에서와 같은 순서로 발생하지 않을지라도, 각 시점에서 연속적인 범위를 형성합니다. 정수의 수열에서 순열로의 매핑은 다소 복잡하지만, 즉시 귀납법(induction)에 의해 정확하게 하나의 방법에서 각 순열을 생성하는 것을 볼 수 있습니다. 선택된 원소가 마지막 남아있는 원소가 될 때, 교환 연산이 생략될 수 있습니다. 이것은 조건에 대한 테스트를 보증할 만큼 충분히 자주 발생하지 않지만, 마지막 원소가 모든 순열이 생성될 수 있음을 보장하기 위해 선택의 후보 사이에 포함되어야 합니다.

a[0], a[1], ..., a[n − 1]의 무작위 순열을 생성하기 위한 결과 알고리듬은 유사코드(pseudocode)에서 다음과 같이 설명될 수 있습니다:

for i from n downto 2 do
    di ← random element of { 0, ..., i − 1 }
    swap a[di] and a[i − 1]

이것은 다음과 같이 배열 a[i] = i의 초기화와 결합될 수 있습니다:

for i from 0 to n−1 do
    di+1 ← random element of { 0, ..., i }
    a[i] ← a[di+1]
    a[di+1] ← i

만약 d_i+1 = i이면, 첫 번째 할당은 초기화되지 않은 값을 복사하지만, 두 번째 할당은 그것을 올바른 값 i로 덮어쓸 것입니다.

어쨌든 피셔-예이츠는 순열을 생성하는 가장 빠른 알고리듬은 아닌데, 왜냐하면 피셔-예이츠는 본질적으로 순차적 알고리듬이고 "분할과 정복" 절차가 병렬로 같은 결과를 달성할 수 있기 때문입니다.

Generation in lexicographic order

주어진 수열의 모든 순열을 시스템적으로 생성하기 위한 많은 방법이 있습니다. 하나의 고전적이고 단순하고 유연한 알고리듬은 사전식 순서화(lexicographic ordering)에서, 만약 다음 순열이 있으면, 그것을 찾는 것을 기반으로 합니다. 그것은 반복된 값을 처리할 수 있으며, 이 경우에 대해 그것은 각각의 구별되는 중복집합 순열을 한 번 생성합니다. 심지어 보통의 순열에 대해 그것은 사전식 순서로 레머 코드에 대해 값을 생성하고 (아마도 팩토리얼 숫자 시스템(factorial number system)을 사용하여) 그것들을 순열로 변환하는 것보다 훨씬 더 효율적입니다. 그것은 (약하게) 증가(increasing)하는 순서로 수열을 정렬함으로써 시작하고 (사전식으로 최소 순열을 제공함), 그런-다음 하나가 발견되는 한 다음 순열로 진행하는 것을 반복합니다. 그 방법은 14세기 인도의 나라야나 판딧(Narayana Pandit)으로 거슬러 올라가고, 자주 재발견되어 왔습니다.

다음 알고리듬은 주어진 순열 후에 사전식으로 다음 순열을 생성합니다. 그것은 주어진 순열을 제자리에서 변경합니다.

1. a[k] < a[k + 1]를 만족하는 가장 큰 인덱스 k를 찾습니다. 만약 그러한 인덱스가 존재하지 않으면, 그 순열이 마지막 순열입니다.
2. a[k] < a[l]를 만족하는 k보다 큰 가장 큰 인덱스 l을 찾습니다.
3. a[k]의 값을 a[l]의 값과 교환합니다.
4. a[k + 1]에서 마지막 원소 a[n]를 하고 그것까지 수열을 반대로 합니다.

예를 들어, 수열 [1, 2, 3, 4] (증가하는 순서임)가 주어지고, 인덱스가 영-기반(zero-based)으로 주어지면, 단계는 다음과 같습니다:

1. 인덱스 k = 2인데, 왜냐하면 3은 4인 a[k + 1]보다 여전히 작은 가장 큰 인덱스가 되는 조건을 만족시키는 인덱스에 위치되기 때문입니다.
2. 인덱스 l = 3인데, 왜냐하면 조건 a[k] < a[l]을 만족시키기 위해 3보다 더 큰 수열에서 유일한 값이기 때문입니다.
3. a[2]와 a[3]의 값은 새로운 수열 [1, 2, 4, 3]를 형성하기 위해 교환됩니다.
4. k-인덱스 a[2] 이후의 마지막 원소까지의 수열은 반대로 됩니다. 오직 하나의 값이 이 인덱스 (3) 뒤에 놓이기 때문에, 그 수열은 이 인스턴스에서 변경되지 않은 채 남겨집니다. 따라서 초기 상태의 사전식 후속 순열은 순열됩니다: [1, 2, 4, 3].

이 알고리듬에 따르면, 다음 사전식 순열은 [1, 3, 2, 4]일 것이고, 24번째 순열은 점 a[k] < a[k + 1]가 존재하지 않는 것에서 [4, 3, 2, 1]일 것이며, 이것이 마지막 순열임을 나타냅니다.

이 방법은 순열당 약 3 비교와 1.5번 교환을 사용하며, 초기 정렬을 세지 않고 전체 수열에 걸쳐 상각됩니다.

Generation with minimal changes

Main articles: Steinhaus–Johnson–Trotter algorithm and Heap's algorithm

위의 알고리듬에 대한 대안, 스테인하우스–존슨–트로터 알고리듬(Steinhaus–Johnson–Trotter algorithm)은 출력에서 임의의 둘의 연속적인 순열이 둘의 인접한 값을 교환함으로써 다른 속성을 갖는 주어진 수열의 모든 순열에 대한 순서화를 생성합니다. 순열에 대한 이러한 순서화는 17세기 영국 벨 울리는 사람들에게 알려져 있었으며, 그들 사이에 "단조로운 변경"으로 알려져 있었습니다. 이 방법의 한 가지 장점은 한 순열에서 다음 순열로의 작은 총양이 순열당 일정한 시간에 방법을 구현되는 방법을 허용한다는 것입니다. 같은 것이 역시 모든 각 다른 출력 순열을 건너뜀으로써, 다시 순열당 일정한 시간에서, 짝수 순열의 부분집합을 쉽게 생성할 수 있습니다.

스테인하우스–존슨–트로터에 대한 대안은 힙의 알고리듬(Heap's algorithm)이며, 그것은 로버트 세지윅(Robert Sedgewick)에 의해 1977년 응용에서 순열을 생성하는 가장 빠른 알고리듬이라고 언급되었습니다.

다음 그림은 길이 $n=4$의 모든 순열을 생성하기 위한 앞서 언급한 모든 셋의 알고리듬과 문헌에 설명된 여섯 추가적인 알고리듬의 출력을 보여줍니다.

Ordering of all permutations of length $n=4$ generated by different algorithms. The permutations are color-coded, where   1,   2,   3,   4.

1. 사전식 순서화;
2. 스테인하우스–존슨–트로터 알고리듬(Steinhaus–Johnson–Trotter algorithm);
3. 힙의 알고리듬(Heap's algorithm);
4. 에를리히의 별-전치 알고리듬: 각 단계에서, 순열의 첫 번째 엔트리가 나중 엔트리와 교환됩니다;
5. 작스의 접두사 반전 알고리듬: 각 단계에서, 현재 순열의 접두사는 다음 순열을 얻기 위해 반전됩니다;
6. 스와다-윌리암스의 알고리듬: 각 순열은 한 위치만큼 순환 왼쪽-시프트, 또는 처음 두 엔트리의 교환에 의해 이전 순열과 다릅니다;
7. Corbett's algorithm: 각 순열은 일부 접두를 한 위치만큼 순환 왼쪽-시프트에 의해 이전 순열과 다릅니다.
8. 단일-트랙 순서화: 각 열은 나머지 하나의 다른 열의 순환 이동입니다.
9. 단일-트랙 그레이 코드: 각 열은 나머지 하나의 다른 열의 순환 이동이며, 더하기 임의의 둘의 연속적인 순열은 오직 하나 또는 둘의 전치에서 다릅니다.

Meandric permutations

미엔드릭 시스템(Meandric systems)은 미엔드릭 순열(meandric permutations), 교대 순열의 특별한 부분집합을 발생시킵니다. 집합 {1, 2, ..., 2n}의 교대 순열은 순환 표기법 형식에서 자릿수가 홀수와 짝수 정수 사이에서 교대함을 만족하는 (고정된 점없이) 순환 순열(cyclic permutation)입니다. 미엔드릭 순열은 RNA 이차 구조의 분석에 유용합니다. 모든 교대 순열이 미엔드릭인 것은 아닙니다. 힙의 알고리듬의 수정은 모든 (2n)! 순열 생성없이 순서 n(즉, 길이 2n)의 모든 교대 순열을 생성하기 위해 사용되어 왔습니다. 이들 교대 순열의 생성은 그것들이 미엔드릭인지 여부를 결정하기 위해 분석되기 전에 필요됩니다.

그 알고리듬은 재귀적입니다. 다음 테이블은 절차의 단계를 보여줍니다. 이전 단계에서, 길이 5의 모든 교대 순열이 생성되어졌습니다. 이들 각각의 셋의 사본은 오른쪽 끝에 더해진 "6"을 가지고, 그런-다음 이 마지막 엔트리와 짝수 위치에 있는 이전 엔트리를 포함하는 다른 전치가 적용됩니다 (항등을 포함; 즉 전치 없음).

이전 집합	자릿수의 전치	교대 순열
1-2-3-4-5-6		1-2-3-4-5-6
	4, 6	1-2-3-6-5-4
	2, 6	1-6-3-4-5-2
1-2-5-4-3-6		1-2-5-4-3-6
	4, 6	1-2-5-6-3-4
	2, 6	1-6-5-4-3-2
1-4-3-2-5-6		1-4-3-2-5-6
	2, 6	1-4-3-6-5-2
	4, 6	1-6-3-2-5-4
1-4-5-2-3-6		1-4-5-2-3-6
	2, 6	1-4-5-6-3-2
	4, 6	1-6-5-2-3-4

Applications

순열은 터보 코드(turbo codes)와 같은 오류 감지와 수정 알고리듬의 인터리버(interleaver) 구성 요소에 사용되며, 예를 들어, 3GPP Long Term Evolution 이동 통신 표준은 이들 아이디어를 사용합니다 (3GPP 기술 사양 36.212을 참조). 그러한 응용은 특정 바람직한 속성을 만족시키는 순열의 빠른 생성의 문제를 제기합니다. 그 방법 중 하나는 순열 다항식(permutation polynomials)을 기반으로 합니다. 역시 고유한 순열 해싱(Unique Permutation Hashing)에서 최적의 해싱에 대해 하나의 기반입니다.

See also

• Alternating permutation
• Convolution
• Cyclic order
• Even and odd permutations
• Josephus permutation
• Levi-Civita symbol
• List of permutation topics
• Major index
• Permutation category
• Permutation group
• Permutation pattern
• Permutation representation (symmetric group)
• Probability
• Rencontres numbers
• Sorting network
• Substitution cipher
• Superpattern
• Superpermutation
• Twelvefold way
• Weak order of permutations

Bibliography

• Bogart, Kenneth P. (1990), Introductory Combinatorics (2nd ed.), Harcourt Brace Jovanovich, ISBN 978-0-15-541576-8
• Bóna, Miklós (2004), Combinatorics of Permutations, Chapman Hall-CRC, ISBN 978-1-58488-434-7
• Bona, Miklos (2012), Combinatorics of Permutations (2nd ed.), CRC Press, ISBN 978-1-4398-5051-0
• Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice-Hall, ISBN 978-0-13-602040-0
• Cameron, Peter J. (1994), Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, ISBN 978-0-521-45761-3
• Carmichael, Robert D. (1956) [1937], Introduction to the theory of Groups of Finite Order, Dover, ISBN 978-0-486-60300-1
• Fraleigh, John B. (1976), A First Course In Abstract Algebra (2nd ed.), Reading: Addison-Wesley, ISBN 0-201-01984-1
• Gerstein, Larry J. (1987), Discrete Mathematics and Algebraic Structures, W.H. Freeman and Co., ISBN 978-0-7167-1804-8
• Hall, Marshall, Jr. (1959), The Theory of Groups, MacMillan{{citation}}: CS1 maint: multiple names: authors list (link)
• Humphreys, J. F. (1996), A course in group theory, Oxford University Press, ISBN 978-0-19-853459-4
• Knuth, Donald (1973), Sorting and Searching, The Art of Computer Programming, vol. 3 This book mentions the Lehmer code (without using that name) as a variant C₁,...,C_n of inversion tables in exercise 5.1.1–7 (p. 19), together with two other variants.
• Knuth, Donald (2005), Generating All Tuples and Permutations, The Art of Computer Programming, vol. 4, Addison–Wesley, ISBN 978-0-201-85393-3 Fascicle 2, first printing.
• McCoy, Neal H. (1968), Introduction To Modern Algebra, Revised Edition, Boston: Allyn and Bacon, LCCN 68015225
• Nering, Evar D. (1970), Linear Algebra and Matrix Theory (2nd ed.), New York: Wiley, LCCN 76091646
• Rotman, Joseph J. (2002), Advanced Modern Algebra, Prentice-Hall, ISBN 978-0-13-087868-7
• Stedman, Fabian (1677), Campanalogia, London The publisher is given as "W.S." who may have been William Smith, possibly acting as agent for the Society of College Youths, to which society the "Dedicatory" is addressed. In quotations the original long "S" has been replaced by a modern short "s".
• Webster's Seventh New Collegiate Dictionary, Springfield: G. & C. Merriam Company, 1969

Further reading

• Biggs, Norman L. (2002), Discrete Mathematics (2nd ed.), Oxford University Press, ISBN 978-0-19-850717-8
• Foata, Dominique; Schutzenberger, Marcel-Paul (1970), Théorie Géométrique des Polynômes Eulériens, Lecture Notes in Mathematics, vol. 138, Berlin, Heidelberg: Springer-Verlag, ISBN 978-3-540-04927-2. The link is to a freely available retyped (LaTeX'ed) and revised version of the text originally published by Springer-Verlag.
• Knuth, Donald (1998), Sorting and Searching, The Art of Computer Programming, vol. 3 (Second ed.), Addison–Wesley, ISBN 978-0-201-89685-5. Section 5.1: Combinatorial Properties of Permutations, pp. 11–72.
• Sedgewick, Robert (1977). "Permutation generation methods". ACM Computing Surveys. 9 (2): 137–164. doi:10.1145/356689.356692.

External links

• "Permutation", Encyclopedia of Mathematics, EMS Press, 2001 [1994]