순열

참고

번역중

이 단원에서는 순열을 만들고 제어하는 함수들을 서술합니다. 순열 \(p\) 는 \(0\) 에서 \(n-1\) 의 범주를 가지는 \(n\) 길이의 정수 배열을 의미합니다. 각각의 값 \(p_i\) 는 배열 내에서 한번만 나옵니다. 순열 \(p\) 를 벡터 \(v\) 에 적용하면 새로운 벡터 \(v'\) 를 얻을 수 있습니다.

\[v'_i = v_{p_i}\]

예를 들어서, 배열 \((0,1,3,2)\) 는 길이 4의 벡터의 원소 중 마지막 두 원소를 바꾸는 순열을 나타냅니다. 항등 순열은 \((0,1,2,3)\) 로 나타낼 수 있습니다.

Note that the permutations produced by the linear algebra routines correspond to the exchange of matrix columns, and so should be considered as applying to row-vectors in the form \(v' = v P\) rather than column-vectors, when permuting the elements of a vector.

이 단원에 기술된 함수들은 헤더 파일 gsl_permutation.h 에 기술되어 있습니다.

순열 구조체

type gsl_permutation

순열은 2 개의 원소를 가지는 구조체로 정의됩니다. 이 두 변수는 각각 순열의 크기와 순열 배열을 가르키는 포인터를 의미합니다. 순열 배열의 원소는 모두 size_t 입니다. gsl_permutation 구조체는 다음과 같이 정의되어 있습니다.

typedef struct
  {
    size_t size;
    size_t * data;
  } gsl_permutation;

순열 할당

gsl_permutation *gsl_permutation_alloc(size_t n)

크기 n 의 순열을 위한 메모리 공간을 할당합니다. 이 함수는 순열의 원소들을 초기화하지 않기 때문에 반환된 순열에서 각 원소들을 특정 값으로 정의되지 않은 상태입니다. gsl_permutation_calloc 함수를 사용하면 항등 순열로 초기화 된 순열을 얻을 수 있습니다. 순열을 할당하기에 메모리가 충분하지 않다면 NULL 포인터를 반환합니다.

gsl_permutation *gsl_permutation_calloc(size_t n)

크기 n 의 순열을 위한 메모리 공간을 할당합니다. 이 함수에서 반환하는 순열은 항등 순열입니다. 순열을 할당하기에 메모리가 충분하지 않다면 NULL 포인터를 반환합니다.

void gsl_permutation_init(gsl_permutation *p)

주어진 순열 p 를 항등 순열로 초기화합니다. n 크기의 순열에 대해, \((0, 1, 2, \dots, n - 1)\) 로 초기화 합니다.

void gsl_permutation_free(gsl_permutation *p)

순열 p 의 메모리를 해제합니다.

int gsl_permutation_memcpy(gsl_permutation *dest, const gsl_permutation *src)

주어진 순열 src 의 원소들을 dest 로 복사합니다. 이 두 순열은 반드시 같은 크기를 가져야 합니다.

순열 접근

다음 함수들은 순열 속 값에 접근하거나 이 값들을 제어하는 기능들을 제공합니다.

size_t gsl_permutation_get(const gsl_permutation *p, const size_t i)

주어진 순열 p 의 i 번째 원소의 값을 반환합니다. i 가 0에서 \(n-1\) 범위 밖으로 주어지면, 오류 관리자가 호출되고 0이 반환됩니다. HAVE_INLINE 이 정의된 경우, 인라인 함수가 사용됩니다.

int gsl_permutation_swap(gsl_permutation *p, const size_t i, const size_t j)

주어진 순열 p 의 i 번째 원소와 j 번째 원소의 값을 교환합니다.

순열의 성질

size_t gsl_permutation_size(const gsl_permutation *p)

주어진 순열 p 의 크기를 반환합니다.

size_t *gsl_permutation_data(const gsl_permutation *p)

주어진 순열 p 의 순열 배열을 가르키는 포인터를 반환합니다.

int gsl_permutation_valid(const gsl_permutation *p)

주어진 순열 p 가 타당한지 검사합니다. 구체적으로 크기 n 인 순열 p 가 0에서 n-1 까지의 값을 모두, 그리고 한번만 가지고 있는지 검사합니다.

순열 함수

void gsl_permutation_reverse(gsl_permutation *p)

주어진 순열 p 의 원소들을 역순으로 배열합니다.

int gsl_permutation_inverse(gsl_permutation *inv, const gsl_permutation *p)

주어진 순열 p 의 역순열을 계산해 inv 에 저장합니다.

int gsl_permutation_next(gsl_permutation *p)

This function advances the permutation p to the next permutation in lexicographic order and returns GSL_SUCCESS. If no further permutations are available it returns GSL_FAILURE and leaves p unmodified. Starting with the identity permutation and repeatedly applying this function will iterate through all possible permutations of a given order.

int gsl_permutation_prev(gsl_permutation *p)

This function steps backwards from the permutation p to the previous permutation in lexicographic order, returning GSL_SUCCESS. If no previous permutation is available it returns GSL_FAILURE and leaves p unmodified.

순열 적용

다음 함수들은 헤더 파일 gsl_permute.h 와 gsl_permute_vector.h 에 정의되어 있습니다.

int gsl_permute(const size_t *p, double *data, size_t stride, size_t n)

순열 p 를 길이 n , stride 크기의 걸음을 가지는 값 배열 data 에 적용합니다.

int gsl_permute_inverse(const size_t *p, double *data, size_t stride, size_t n)

순열 p 의 역순열을 길이 n , stride 크기의 걸음을 가지는 값 배열 data 에 적용합니다.

int gsl_permute_vector(const gsl_permutation *p, gsl_vector *v)

This function applies the permutation p to the elements of the vector v, considered as a row-vector acted on by a permutation matrix from the right, \(v' = v P\). The \(j\)-th column of the permutation matrix \(P\) is given by the \(p_j\)-th column of the identity matrix. The permutation p and the vector v must have the same length.

int gsl_permute_vector_inverse(const gsl_permutation *p, gsl_vector *v)

This function applies the inverse of the permutation p to the elements of the vector v, considered as a row-vector acted on by an inverse permutation matrix from the right, \(v' = v P^T\). Note that for permutation matrices the inverse is the same as the transpose. The \(j\)-th column of the permutation matrix \(P\) is given by the \(p_j\)-th column of the identity matrix. The permutation p and the vector v must have the same length.

int gsl_permute_matrix(const gsl_permutation *p, gsl_matrix *A)

This function applies the permutation p to the matrix A from the right, \(A' = A P\). The \(j\)-th column of the permutation matrix \(P\) is given by the \(p_j\)-th column of the identity matrix. This effectively permutes the columns of A according to the permutation p, and so the number of columns of A must equal the size of the permutation p.

int gsl_permutation_mul(gsl_permutation *p, const gsl_permutation *pa, const gsl_permutation *pb)

This function combines the two permutations pa and pb into a single permutation p, where \(p = pa * pb\) The permutation p is equivalent to applying pb first and then pa.

순열 읽고 쓰기

라이브러리에서 형식화 된 문자열이나 이진 파일로 순열을 읽고 쓸 수 있는 함수들을 제공합니다.

int gsl_permutation_fwrite(FILE *stream, const gsl_permutation *p)

This function writes the elements of the permutation p to the stream stream in binary format. The function returns GSL_EFAILED if there was a problem writing to the file. Since the data is written in the native binary format it may not be portable between different architectures.

int gsl_permutation_fread(FILE *stream, gsl_permutation *p)

This function reads into the permutation p from the open stream stream in binary format. The permutation p must be preallocated with the correct length since the function uses the size of p to determine how many bytes to read. The function returns GSL_EFAILED if there was a problem reading from the file. The data is assumed to have been written in the native binary format on the same architecture.

int gsl_permutation_fprintf(FILE *stream, const gsl_permutation *p, const char *format)

This function writes the elements of the permutation p line-by-line to the stream stream using the format specifier format, which should be suitable for a type of size_t. In ISO C99 the type modifier z represents size_t, so "%zu\n" is a suitable format 1. The function returns GSL_EFAILED if there was a problem writing to the file.

int gsl_permutation_fscanf(FILE *stream, gsl_permutation *p)

This function reads formatted data from the stream stream into the permutation p. The permutation p must be preallocated with the correct length since the function uses the size of p to determine how many numbers to read. The function returns GSL_EFAILED if there was a problem reading from the file.

원순열

A permutation can be represented in both linear and cyclic notations. The functions described in this section convert between the two forms. The linear notation is an index mapping, and has already been described above. The cyclic notation expresses a permutation as a series of circular rearrangements of groups of elements, or cycles.

For example, under the cycle (1 2 3), 1 is replaced by 2, 2 is replaced by 3 and 3 is replaced by 1 in a circular fashion. Cycles of different sets of elements can be combined independently, for example (1 2 3) (4 1) combines the cycle (1 2 3) with the cycle (4 5), which is an exchange of elements 4 and 5. A cycle of length one represents an element which is unchanged by the permutation and is referred to as a singleton.

It can be shown that every permutation can be decomposed into combinations of cycles. The decomposition is not unique, but can always be rearranged into a standard canonical form by a reordering of elements. The library uses the canonical form defined in Knuth’s Art of Computer Programming (Vol 1, 3rd Ed, 1997) Section 1.3.3, p.178.

The procedure for obtaining the canonical form given by Knuth is,

  1. Write all singleton cycles explicitly

  2. Within each cycle, put the smallest number first

  3. Order the cycles in decreasing order of the first number in the cycle.

For example, the linear representation (2 4 3 0 1) is represented as (1 4) (0 2 3) in canonical form. The permutation corresponds to an exchange of elements 1 and 4, and rotation of elements 0, 2 and 3.

The important property of the canonical form is that it can be reconstructed from the contents of each cycle without the brackets. In addition, by removing the brackets it can be considered as a linear representation of a different permutation. In the example given above the permutation (2 4 3 0 1) would become (1 4 0 2 3). This mapping has many applications in the theory of permutations.

int gsl_permutation_linear_to_canonical(gsl_permutation *q, const gsl_permutation *p)

This function computes the canonical form of the permutation p and stores it in the output argument q.

int gsl_permutation_canonical_to_linear(gsl_permutation *p, const gsl_permutation *q)

This function converts a permutation q in canonical form back into linear form storing it in the output argument p.

size_t gsl_permutation_inversions(const gsl_permutation *p)

This function counts the number of inversions in the permutation p. An inversion is any pair of elements that are not in order. For example, the permutation 2031 has three inversions, corresponding to the pairs (2,0) (2,1) and (3,1). The identity permutation has no inversions.

size_t gsl_permutation_linear_cycles(const gsl_permutation *p)

This function counts the number of cycles in the permutation p, given in linear form.

size_t gsl_permutation_canonical_cycles(const gsl_permutation *q)

This function counts the number of cycles in the permutation q, given in canonical form.

예제

이 예제에서는 항드원의 원소를 섞는 방법을 사용해 임의의 순열을 생성하고 그 순열의 역순열을 찾는 방법을 보여줍니다.

#include <stdio.h>
#include <gsl/gsl_rng.h>
#include <gsl/gsl_randist.h>
#include <gsl/gsl_permutation.h>

int
main (void)
{
  const size_t N = 10;
  const gsl_rng_type * T;
  gsl_rng * r;

  gsl_permutation * p = gsl_permutation_alloc (N);
  gsl_permutation * q = gsl_permutation_alloc (N);

  gsl_rng_env_setup();
  T = gsl_rng_default;
  r = gsl_rng_alloc (T);

  printf ("initial permutation:");
  gsl_permutation_init (p);
  gsl_permutation_fprintf (stdout, p, " %u");
  printf ("\n");

  printf (" random permutation:");
  gsl_ran_shuffle (r, p->data, N, sizeof(size_t));
  gsl_permutation_fprintf (stdout, p, " %u");
  printf ("\n");

  printf ("inverse permutation:");
  gsl_permutation_inverse (q, p);
  gsl_permutation_fprintf (stdout, q, " %u");
  printf ("\n");

  gsl_permutation_free (p);
  gsl_permutation_free (q);
  gsl_rng_free (r);

  return 0;
}

프로그램의 출력 결과는 다음과 같습니다.

$./a.out
initial permutation: 0 1 2 3 4 5 6 7 8 9
 random permutation: 1 3 5 2 7 6 0 4 9 8
inverse permutation: 6 0 3 1 7 2 5 4 9 8

The random permutation p[i] and its inverse q[i] are related through the identity p[q[i]] = i, which can be verified from the output.

The next example program steps forwards through all possible third order permutations, starting from the identity,

#include <stdio.h>
#include <gsl/gsl_permutation.h>

int
main (void)
{
  gsl_permutation * p = gsl_permutation_alloc (3);

  gsl_permutation_init (p);

  do
   {
      gsl_permutation_fprintf (stdout, p, " %u");
      printf ("\n");
   }
  while (gsl_permutation_next(p) == GSL_SUCCESS);

  gsl_permutation_free (p);

  return 0;
}

프로그램의 출력 결과는 다음과 같습니다.

$./a.out
 0 1 2
 0 2 1
 1 0 2
 1 2 0
 2 0 1
 2 1 0

The permutations are generated in lexicographic order. To reverse the sequence, begin with the final permutation (which is the reverse of the identity) and replace :fun`gsl_permutation_next` with :fun`gsl_permutation_prev`.

참고 문헌과 추가 자료

다음의 문헌에서 순열과 관련된 광범위한 내용을 참고할 수 있습니다.

  • Donald E. Knuth, The Art of Computer Programming: Sorting and Searching (Vol 3, 3rd Ed, 1997), Addison-Wesley, ISBN 0201896850.

정규형 순열에 관한 정의는 다음을 참고할 수 있습니다.

  • Donald E. Knuth, The Art of Computer Programming: Fundamental Algorithms (Vol 1, 3rd Ed, 1997), Addison-Wesley, ISBN 0201896850. Section 1.3.3, An Unusual Correspondence, p.178–179.

1

In versions of the GNU C library prior to the ISO C99 standard, the type modifier Z was used instead.