[ < ] | [ > ] |  | [ << ] | [ Up ] | [ >> ] |  |  |  |  | [Top] | [Contents] | [Index] | [ ? ]

# 48. combinatorics

[ < ] | [ > ] |  | [ << ] | [ Up ] | [ >> ] |  |  |  |  | [Top] | [Contents] | [Index] | [ ? ]

## 48.1 Package combinatorics

`combinatorics`パッケージは、置換と合わせて機能したりリストの要素を置換するいくつかの関数を提供します。 次数 nの置換は 最初の n個の正の整数 1, 2, …, nの n!個の可能な順序すべてです。 このパッケージの関数は置換がこれらの整数のリストで表現されると仮定します。

循環は、すべて異なる2つ以上の整数 i_1, i_2, …, i_mのリストで表現されます。 そんなリストは 整数 i_2が i_1番目の位置に現れ、 整数 i_3が i_2番目の位置に現れ、 整数 i_1が i_m番目の位置に現れる置換を表現します。

例えば、 [4, 2, 1, 3]は次数4の24個の置換の1つです。 これは、循環 [1, 4, 3]としても表現することができます。 循環が置換を表現するのに使う関数は曖昧さを避けるために置換の次数も要求します。 例えば、 同じ循環 [1, 4, 3]は次数6の置換: [4, 2, 1, 3, 5, 6]も表します。 循環の積は循環のリストで表現されなければいけません: リストの最後の循環が最初に適用されます。 例えば、 [[2, 4], [1, 3, 6, 5]]は置換 [3, 4, 6, 2, 1, 5]と同値です。

循環はいくつかの方法で書くことができます。 例えば、 [1, 3, 6, 5]と [3, 6, 5, 1], [6, 5, 1, 3]はすべて同値です。 パッケージで使われる標準形は最小インデックスを最初に置くものです。 インデックス2つだけの循環は互換とも呼ばれます。 2つのインデックスが連続なものなら、隣接互換と呼ばれます。

インタラクティブなチュートリアルを走らせるには、 コマンド `demo(combinatorics)`を使ってください。 これは追加パッケージなので、 コマンド `load("combinatorics")`でロードしなければいけません。

Categories: Share packages · Package combinatorics

[ < ] | [ > ] |  | [ << ] | [ Up ] | [ >> ] |  |  |  |  | [Top] | [Contents] | [Index] | [ ? ]

## 48.2 Functions and Variables for Combinatorics

関数: apply_cycles (cl,l)

  リストか集合 lを、循環のリスト clを適用して置換します。 リストの最後の循環が最初に適用され、リスト clの最初の循環が最後に適用されます。

  `permute`も参照ください。

  例:

      (%i1) load("combinatorics")$
      (%i2) lis1:[a,b*c^2,4,z,x/y,1/2,ff23(x),0];
                              2        x  1
      (%o2)            [a, b c , 4, z, -, -, ff23(x), 0]
                                       y  2
      (%i3) apply_cycles ([[1, 6], [2, 6, 5, 7]], lis1);
                        x  1                       2
      (%o3)            [-, -, 4, z, ff23(x), a, b c , 0]
                        y  2

  Categories: Package combinatorics

関数: cyclep (c, n)

  もし cが次数 nの有効な循環、すなわち 繰り返しのない n以下の正の整数のリストなら trueを返します。 そうでなければ falseを返します。

  `permp`も参照してください。

  例:

      (%i1) load("combinatorics")$
      (%i2) cyclep ([-2,3,4], 5);
      (%o2)                          false
      (%i3) cyclep ([2,3,4,2], 5);
      (%o3)                          false
      (%i4) cyclep ([6,3,4], 5);
      (%o4)                          false
      (%i5) cyclep ([6,3,4], 6);
      (%o5)                          true

  Categories: Package combinatorics

関数: perm_cycles (p)

  置換 pを循環の積として返します。 循環は、循環の中の最小インデックスが最初に来る標準形で書かれます。

  `perm_decomp`も参照してください。

  例:

      (%i1) load("combinatorics")$
      (%i2) perm_cycles ([4, 6, 3, 1, 7, 5, 2, 8]);
      (%o2)                 [[1, 4], [2, 6, 5, 7]]

  Categories: Package combinatorics

関数: perm_decomp (p)

  その積が与えられた置換 pに等しい隣接互換の最小集合を返します。

  `perm_cycles`も参照してください。

  例:

      (%i1) load("combinatorics")$
      (%i2) perm_decomp ([4, 6, 3, 1, 7, 5, 2, 8]);
      (%o2) [[6, 7], [5, 6], [6, 7], [3, 4], [4, 5], [2, 3], [3, 4],
                                  [4, 5], [5, 6], [1, 2], [2, 3], [3, 4]]

  Categories: Package combinatorics

関数: perm_inverse (p)

  置換 pの逆、すなわち、 積 pqと積 qpが恒等置換: [1, 2, 3, …, n]に等しくなるような 置換 qを返します。 ここで、 nは pの長さです。

  `permult`も参照してください。

  例:

      (%i1) load("combinatorics")$
      (%i2) perm_inverse ([4, 6, 3, 1, 7, 5, 2, 8]);
      (%o2)                [4, 7, 3, 1, 6, 2, 5, 8]

  Categories: Package combinatorics

関数: perm_length (p)

  置換 pを 隣接互換の積として書くのに必要な隣接互換の最小数を決定します。 隣接互換は連続する2つの数だけの循環です。

  `perm_decomp`も参照してください。

  例:

      (%i1) load("combinatorics")$
      (%i2) perm_length ([4, 6, 3, 1, 7, 5, 2, 8]);
      (%o2)                           12

  Categories: Package combinatorics

関数: perm_lex_next (p)

  辞書式順序での置換の列で、 与えられた置換 pのあとに来る置換を返します。

  例:

      (%i1) load("combinatorics")$
      (%i2) perm_lex_next ([4, 6, 3, 1, 7, 5, 2, 8]);
      (%o2)                [4, 6, 3, 1, 7, 5, 8, 2]

  Categories: Package combinatorics

関数: perm_lex_rank (p)

  辞書式順序での置換の列で、 置換 pの位置を見つけます。 1から次数 nの置換までの整数です。

  `perm_lex_unrank`と `perms_lex`も参照してください。

  例:

      (%i1) load("combinatorics")$
      (%i2) perm_lex_rank ([4, 6, 3, 1, 7, 5, 2, 8]);
      (%o2)                          18255

  Categories: Package combinatorics

関数: perm_lex_unrank (n, i)

  辞書式順序での置換の列で、 (1から n!までの)位置 iの n-次数の置換を返します。

  `perm_lex_rank`と `perms_lex`も参照してください。

  例:

      (%i1) load("combinatorics")$
      (%i2) perm_lex_unrank (8, 18255);
      (%o2)                [4, 6, 3, 1, 7, 5, 2, 8]

  Categories: Package combinatorics

関数: perm_next (p)

  Trotter-Johnson順序での置換の列で、 与えられた置換 pのあとに来る置換を返します。

  `perms`も参照してください。

  例:

      (%i1) load("combinatorics")$
      (%i2) perm_next ([4, 6, 3, 1, 7, 5, 2, 8]);
      (%o2)                [4, 6, 3, 1, 7, 5, 8, 2]

  Categories: Package combinatorics

関数: perm_parity (p)

  置換 pの偶奇性を見つけます: 置換 pを隣接互換の積として書く隣接互換の最小数が偶数なら0を、 奇数なら1を返します。

  `perm_decomp`も参照してください。

  例:

      (%i1) load("combinatorics")$
      (%i2) perm_parity ([4, 6, 3, 1, 7, 5, 2, 8]);
      (%o2)                            0

  Categories: Package combinatorics

関数: perm_rank (p)

  辞書式順序での置換の列で、 置換 pの位置、1から次数 nの置換の整数、を見つけます。

  `perm_unrank`と `perms`も参照してください。

  例:

      (%i1) load("combinatorics")$
      (%i2) perm_rank ([4, 6, 3, 1, 7, 5, 2, 8]);
      (%o2)                          19729

  Categories: Package combinatorics

関数: perm_undecomp (cl, n)

  次数 nの循環のリスト clを それらの積に等しい n次数置換に変換します。

  `perm_decomp`も参照してください。

  例:

      (%i1) load("combinatorics")$
      (%i2) perm_undecomp ([[1,6],[2,6,5,7]], 8);
      (%o2)                [5, 6, 3, 4, 7, 1, 2, 8]

  Categories: Package combinatorics

関数: perm_unrank (n, i)

  Trotter-Johnson順序での置換の列で、 (1から n!までの)位置 iの n-次数置換を返します。

  `perm_rank`と `perms`も返します。

  例:

      (%i1) load("combinatorics")$
      (%i2) perm_unrank (8, 19729);
      (%o2)                [4, 6, 3, 1, 7, 5, 2, 8]

  Categories: Package combinatorics

関数: permp (p)

  もし pが有効な置換なら、すなわち 要素が1から nまでの整数すべてである、繰り返しのない長さ nのリストなら trueを返します。 そうでなければfalseを返します。

  例:

      (%i1) load("combinatorics")$
      (%i2) permp ([2,0,3,1]);
      (%o2)                          false
      (%i3) permp ([2,1,4,3]);
      (%o3)                          true

  Categories: Package combinatorics

関数: perms
`perms` (n)
`perms` (n, i)
`perms` (n, i, j)

  `perms(n)`は n-次数置換すべてのリストをTrotter-Johnson順序と呼ばれる順で返します。

  `perms(n, i)`は 置換の辞書式順序(訳注: Trotter-Johnson順序の間違い？)で (1から n!までの)i番目の位置のn-次数置換を返します。

  `perms(n, i, j)`は 置換の辞書式順序(訳注: Trotter-Johnson順序の間違い？)で 位置 iと位置 jの間にあるn-次数置換のリストを返します。

  Trotter-Johnson順序での置換の列は 恒等置換で始まり、 隣の置換が直前の置換から隣接互換1つで得られます。

  `perm_next`, `perm_rank`, `perm_unrank`も参照してください。

  例:

      (%i1) load("combinatorics")$
      (%i2) perms (4);
      (%o2) [[1, 2, 3, 4], [1, 2, 4, 3], [1, 4, 2, 3], [4, 1, 2, 3],
      [4, 1, 3, 2], [1, 4, 3, 2], [1, 3, 4, 2], [1, 3, 2, 4],
      [3, 1, 2, 4], [3, 1, 4, 2], [3, 4, 1, 2], [4, 3, 1, 2],
      [4, 3, 2, 1], [3, 4, 2, 1], [3, 2, 4, 1], [3, 2, 1, 4],
      [2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 3, 1], [4, 2, 3, 1],
      [4, 2, 1, 3], [2, 4, 1, 3], [2, 1, 4, 3], [2, 1, 3, 4]]
      (%i3) perms (4, 12);
      (%o3)                     [[4, 3, 1, 2]]
      (%i4) perms (4, 12, 14);
      (%o4)       [[4, 3, 1, 2], [4, 3, 2, 1], [3, 4, 2, 1]]

  Categories: Package combinatorics

関数: perms_lex
`perms_lex` (n)
`perms_lex` (n, i)
`perms_lex` (n, i, j)

  `perms_lex(n)`は n-次数置換すべてのリストを辞書式順序と呼ばれる順で返します。

  `perms_lex(n, i)`は 置換の辞書式順序で (1から n!までの)i番目の位置のn-次数置換を返します。

  `perms_lex(n, i, j)`は 置換の辞書式順序で 位置 iと位置 jの間にあるn-次数置換のリストを返します。

  辞書式順序での置換の列は 最小インデックスが1のすべての置換で始まり、 次のインデックスが2で始まるすべての置換が続きます。 インデックス iで始まる置換は iと異なる最初の n個の整数の置換であり、 それらもまた それらの整数の最小が最初に来る辞書式順序で置かれます。

  `perm_lex_next`, `perm_lex_rank`, `perm_lex_unrank`も参照してください。

  例:

      (%i1) load("combinatorics")$
      (%i2) perms_lex (4);
      (%o2) [[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2],
      [1, 4, 2, 3], [1, 4, 3, 2], [2, 1, 3, 4], [2, 1, 4, 3],
      [2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 1, 3], [2, 4, 3, 1],
      [3, 1, 2, 4], [3, 1, 4, 2], [3, 2, 1, 4], [3, 2, 4, 1],
      [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 1, 3, 2],
      [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 1, 2], [4, 3, 2, 1]]
      (%i3) perms_lex (4, 12);
      (%o3)                     [[2, 4, 3, 1]]
      (%i4) perms_lex (4, 12, 14);
      (%o4)       [[2, 4, 3, 1], [3, 1, 2, 4], [3, 1, 4, 2]]

  Categories: Package combinatorics

関数: permult (p_1, …, p_m)

  2つ以上の置換 p_1, …, p_mの積を返します。

  例:

      (%i1) load("combinatorics")$
      (%i2) permult ([2,3,1], [3,1,2], [2,1,3]);
      (%o2)                        [2, 1, 3]

  Categories: Package combinatorics

関数: permute (p, l)

  置換 pをリスト(または集合) lの要素に適用します。

  例:

      (%i1) load("combinatorics")$
      (%i2) lis1: [a,b*c^2,4,z,x/y,1/2,ff23(x),0];
                              2        x  1
      (%o2)            [a, b c , 4, z, -, -, ff23(x), 0]
                                       y  2
      (%i3) permute ([4, 6, 3, 1, 7, 5, 2, 8], lis1);
                           1                 x     2
      (%o3)            [z, -, 4, a, ff23(x), -, b c , 0]
                           2                 y

  Categories: Package combinatorics

関数: random_perm (n)

  次数 nのランダムな置換を返します。

  `random_permutation`も参照してください。

  例:

      (%i1) load("combinatorics")$
      (%i2) random_perm (7);
      (%o2)                  [6, 3, 4, 7, 5, 1, 2]

  Categories: Package combinatorics

[ << ] | [ >> ] |  |  |  |  |  | [Top] | [Contents] | [Index] | [ ? ]

This document was generated by 市川雄二 on October, 4 2018 using texi2html 1.76.