群論と対称性
GAP を使う - プログラミング言語として

GAP では一連の計算をファイルにまとめて書いておき、それを読み込むことによって複数の処理を一度に行うことができる。しかし、同じ処理の繰り返しや、条件によって異なる処理を行うなど、単にコマンドを並べておくだけよりも、細かい処理を行うこともできる。ここではこれらの処理の方法を解説する。

ここで述べる内容はそのすべてを覚える必要はない。特に目的もなくプログラミングを学ぶことは楽しくないので、身につかないことが多い。しかしどんなことが出来るのかを知っていれば、必要なときにその方法を調べて利用できるので、説明を読みながら一通り試してみるといいだろう。

リストは数列のようなものと考えてよい。ものの列であって、順序があり、また要素の重複も許される。 GAP では [1,3,6,2,1] のように , (カンマ) でくくって [ ] で囲んで表される。リスト L の i 番目の要素は L[i] で表される。要素は必ずしも連続していなくてもよいが、定義されていない要素にアクセスしようとするとエラーとなる。

gap> L := [1,2];
[ 1, 2 ]
gap> L[5] := 3;
3
gap> L;
[ 1, 2,,, 3 ]
gap> L[2];
2
gap> L[4];
List Element: [4] must have an assigned value
not in any function
Entering break read-eval-print loop ...
you can 'quit;' to quit to outer loop, or
you can 'return;' after assigning a value to continue
brk> quit;

リストの成分は同種のものである必要はない。例えば、数字と行列が混在しても構わない。

連続する数字のリストは [1..10] のように省略することができる。また等差数列は [1,3..11] のようにはじめの 2 項と最終項を指定することによって書くことができる。これは後で説明するループ (繰り返し) で多く用いられる。

二つのリストをつなげるには Appen, リストの最後に要素を加えるには Add を用いる。要素を消したいならば Unbind を用いる (Unbind は定義済みの変数を未定義に戻すときに用いられ、リスト以外にも使える)。

gap> L := [1,3];
[ 1, 3 ]
gap> M := [2,3];
[ 2, 3 ]
gap> Append(L,M);    
gap> L;
[ 1, 3, 2, 3 ]
gap> Add(L,5);
gap> L;
[ 1, 3, 2, 3, 5 ]
gap> Unbind(L[3]);
gap> L;
[ 1, 3,, 3, 5]

集合

集合はリストの特別なものとして扱われる。重複がなく、かつ小さいものから順に並んでいるリストが集合である。リストから集合を作るには Set を用いる。

gap> L := [1, 2, 3, 2, 1];
[ 1, 2, 3, 2, 1 ]
gap> IsSet(L);
false
gap> S := Set(L);
[ 1, 2, 3 ]
gap> IsSet(S);
true

集合の基本的な演算は Union, Intersection であろう。また、ある物が集合の要素であるかどうかは次の例のようにして確認できる。集合から要素を外すには RemoveSet を用いる。

gap> S := [1,2,3];
[ 1, 2, 3 ]
gap> T := [2,3,4];
[ 2, 3, 4 ]
gap> Union(S, T);
[ 1, 2, 3, 4 ]
gap> Intersection(S, T);
[ 2, 3 ]
gap> 1 in S;
true
gap> 1 in T;
false
gap> RemoveSet(S, 1);  
gap> S;
[ 2, 3 ]

リストと集合の便利な使い方

まず簡単な例を示す。

gap> List([1..10], IsPrimeInt);
[ false, true, true, false, true, false, true, false, false, false ]
gap> List([1..12], x -> Gcd(12,x));    
[ 1, 2, 3, 4, 1, 6, 1, 4, 3, 2, 1, 12 ]

List というコマンドは、一つ目に与えたリストの要素に、二つ目の関数を働かせたものを要素とするリストを返す。この例では 1 から 10 までの数に IsPrimeInt を働かせるので、素数でない 1 に対しては false を、素数である 2 に対しては true を、などとなっている。二つ目に与える関数は、一つ目の例のように簡単なものではない場合もある。二つ目の例では 1 から 12 までの数に対して、その数と 12 の最大公約数のリストを返している。 x をリストの要素として Gcd(12, x) を要素とするリストを返すのである。これを利用すると、かなり複雑なものも書くことが出来る。

例えば、自然数 n に関する命題 P(n) が [1..100] の範囲で正しいかどうかを知るためには

gap> Set(List([1..100], P)) = [true];

とすればよい (これは、単なる例であって効率のよい方法ではない)。

課題. 上の例の意味を理解せよ。そして、この方法がなぜ効率が悪いのかを考察せよ。

上の例と同じ役割をもつ効率のよい方法は以下の通りである。

gap> ForAll([1..100], IsPrime);
false
gap> ForAny([1..100], IsPrime);
true

ForAll でリストの任意の要素に対して正しいかどうか (すなわち ∀) を返し、 ForAny でリストのある要素に対して正しいかどうか (すなわち ∃) を返す。

次に、与えられた集合の要素のうち、ある条件を満たすものだけを抜き出す方法を説明する。

gap> Filtered([1..50], IsPrimeInt); 
[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 ]

Filtered は一つ目に与えられた集合 (リストでも構わない) に対して、二つ目に与えられた関数の戻り値が true であるものだけを抜き出した集合 (リスト) を返す。例えば

gap> L := [1..100];;
gap> L1 := Filtered(L, 条件1);;
gap> L2 := Filtered(L1, 条件2);;
gap> L3 := Filtered(L2, 条件3);;

のように、繰り返し条件で絞り込むことも出来る。

条件に与える関数は複雑ならば自分で書くことも出来る。これについては後で関数の説明で詳しく述べる。

例. ここで簡単な例を見ておこう。コマンドの意味などはコメントを見れば分かるだろう。

gap> G := SymmetricGroup(4);                  # 4 次の対称群
Sym( [ 1 .. 4 ] )
gap> El := Elements(G);                       # S_4 の元をすべて求める。
[ (), (3,4), (2,3), (2,3,4), (2,4,3), (2,4), (1,2), (1,2)(3,4), (1,2,3), 
  (1,2,3,4), (1,2,4,3), (1,2,4), (1,3,2), (1,3,4,2), (1,3), (1,3,4), 
  (1,3)(2,4), (1,3,2,4), (1,4,3,2), (1,4,2), (1,4,3), (1,4), (1,4,2,3), 
  (1,4)(2,3) ]
gap> List(El, Order);                         # S_4 の元の位数のリスト
[ 1, 2, 2, 3, 3, 2, 2, 2, 3, 4, 4, 3, 3, 4, 2, 3, 2, 4, 4, 3, 3, 2, 4, 2 ]
gap> Filtered(El, x -> (Order(x)=2));         # S_4 の元のうち、位数 2 のもの
[ (3,4), (2,3), (2,4), (1,2), (1,2)(3,4), (1,3), (1,3)(2,4), (1,4), 
  (1,4)(2,3) ]

ループ - for

同じような処理を繰り返し行うときにはループを用いる。ループにはここで説明する for を使う方法と、あとで説明する while を用いる方法がある。あらかじめループする回数や範囲が決まっているときには for を用い、そうでないときには while を用いることが多い。

gap> sum := 0;
0
gap> for i in [1..10] do sum := sum + i; od;
gap> sum;
55

この例では 1 から 10 までの和を求めている。まず sum に 0 を代入しておき、 i をリスト [1..10] の要素を動かして、順番に sum に加えている。 for ループをインデント (行頭の空白) をつけて見やすく書くと以下のようになる。

for i in [1..10] do
  sum := sum + i;
od;

for で i を動かし、do と od で囲まれた部分を繰り返し処理する。

条件分岐

条件分岐は以下のように行う。

gap> n := 10;
10
gap> if IsPrimeInt(n) then Print("Prime\n"); else  Print("Not Prime\n"); fi;
Not Prime

ファイルに書く場合はインデントを適当につけて

if IsPrimeInt(n) then
  Print("Prime\n");
else
  Print("Not Prime\n");
fi;

のように書いた方が見やすい。 true でないときに何もしないのであれば else 以下を省略して fi; で終わってもよい。また then と else のあとには複数のコマンドを書いてもよい。また if のあとに更に条件分岐を続けたいときは、 if (条件1) ... elif (条件2) ... elif (条件3) ... else ... fi; などとして書くことができる。

ここで条件式の書き方についてまとめておこう。まず簡単な比較は以下の通りである。

gap> 2 < 3;
true
gap> 2 <= 3;
true
gap> 2 > 3; 
false
gap> 2 >= 3;
false
gap> 2 = 3;
false
gap> 2 <> 3;
true

等しいかどうかは = で、等しくないことは <> で表されることに注意しておく。次に and (かつ) と or (または) についてであるが、これはそのまま書けばよい。

gap> (2 < 3) and (3 > 4);
false
gap> (2 < 3) or (3 > 4); 
true

必要ならばカッコを自由に付けることが出来る。

ループ - while

for ループは、予め繰り返しの範囲が分かっている場合に用いられることが多いのに対し、 while ループは繰り返しの回数が分からないときによく使われる。 while は与えられた条件が満たされる限り、指定されたコマンドを繰り返す。条件式などに誤りがあると無限ループに陥りやすいので注意が必要である。プログラム例は、見やすくインデントをつけて書く。

sum := 0;; i := 1;;
while i <= 10 do
  sum := sum + i;
  i := i + 1;
od;

これを実行すると sum は 1 から 10 までの和となり、結果として 55 となる。 for と異なり i の値も変更してやらなければならないことに注意しておく。 i := i + 1 を書き忘れれば、i は 1 のままなので、条件が満たされ続け、無限ループになる。

条件分岐やループは、ある程度まとまったプログラムを書くときにしか利用しないかもしれないが、次に説明する関数を書くときには多用することになるであろう。

関数

GAP では与えられた関数を使うだけでなく、自分で新しい関数を書いてそれを利用することもできる。もっとも簡単な例は以下のようなものである。

gap> PlusOne := function(x) return x+1; end;
function( x ) ... end
gap> PlusOne(1);
2

関数をインデントをつけて書くと以下のようになる。

PlusOne := fucntion(x)
  return x + 1;
end;

例を見れば雰囲気は分かると思うので、ここではこれ以上は説明しない。簡単な例題をやっておこう。

課題. 与えられた数の 2 乗を求める関数を書いて、その動作を確認しなさい。

いくつかの例を見ながら、いくつかのことを説明する。

例. 与えられた自然数 n に対して 1 から n までの和を返す関数。

sum := function(n)
  local i, ans;

  ans := 0;
  for i in [1..n] do
    ans := ans + i;
  od;
  return ans;
end;

ここで、変数 i と ans は local と宣言されている。このような変数を局所変数という。局所変数はこの関数内でのみ有効な変数であり、関数の外で同じ名前の変数が利用されていても、完全に別な物として扱われ、関数内で値が書き換えられても、外の変数を書き換えたりしない。局所変数を利用することによって関数の独立性が高まり、その関数を利用する人が関数内で利用されている変数名を気にしなくても済む。関数内で利用する変数は、特別な理由がない限り局所変数にした方がよいであろう。

例. 与えられた数が正ならば 1 を、負ならば -1 を、0 ならば 0 を返す関数。

sign := function(a)
  if a > 0 then
    return 1;
  elif a < 0 then
    return -1;
  else
    return 0;
  fi;
end;

この例のように return はプログラムのどこに書いてあってもよく、また複数書いてもよい。ループが何重かになっているとき、それを抜けるのは面倒であるが、関数としておけば、どこからでも return で抜けることができる。

課題. 与えられた有限群 G に対して、G の位数 2 の元の個数を返す関数を書きなさい。

プログラムを書き慣れていない人は複雑な処理を行うときに、一つの大きなプログラムや関数を書くことが多い。そのようにすると誤りも混入しやすく管理が煩雑になる。大きなプログラムを書くときには簡単な機能を持った小さな関数をたくさん用意して、それを組み合わせてプログラムを作ると考えたほうがよい。

戻る

Akihide Hanaki (Shinshu University)

群論と対称性GAP を使う - プログラミング言語として

リスト

集合

リストと集合の便利な使い方

ループ - for

条件分岐

ループ - while

関数

群論と対称性
GAP を使う - プログラミング言語として