[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
48.1 Package combinatorics | ||
48.2 Functions and Variables for Combinatorics |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
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] | [ ? ] |
リストか集合 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
もし 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
置換 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
その積が与えられた置換 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
置換 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
置換 pを 隣接互換の積として書くのに必要な隣接互換の最小数を決定します。 隣接互換は連続する2つの数だけの循環です。
perm_decomp
も参照してください。
例:
(%i1) load("combinatorics")$ (%i2) perm_length ([4, 6, 3, 1, 7, 5, 2, 8]); (%o2) 12 |
Categories: Package combinatorics
辞書式順序での置換の列で、 与えられた置換 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
辞書式順序での置換の列で、 置換 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
辞書式順序での置換の列で、 (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
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
置換 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
辞書式順序での置換の列で、 置換 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
次数 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
Trotter-Johnson順序での置換の列で、 (1から n!までの)位置 iの n-次数置換を返します。
例:
(%i1) load("combinatorics")$ (%i2) perm_unrank (8, 19729); (%o2) [4, 6, 3, 1, 7, 5, 2, 8] |
Categories: Package combinatorics
もし 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(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(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
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
置換 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
次数 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.