「要素を戻さずに取り出していく」をGeoGebraで表現する

課題

list1 = {1,2,3,4,5,6,7,8,9,10}

list2 = {3,3,6,2,1}

とする。
list1から要素を取り出していく。一度取り出したものは戻さない。
list2は、取り出す要素のインデックスを指示している。ただし、当該インデックスは、list1におけるインデックスではなく、それまでに取り出した要素をlist1から除外した、残りのリストにおけるインデックスである。

まず左から3番目（3）を取り出す。

残ったものの左から3番目（4）を取り出す。

残ったものの左から6番目（8）を取り出す。

残ったものの左から2番目（2）を取り出す。

残ったものの左から1番目（1）を取り出す。

取り出した要素を順に並べると、{3,4,8,2,1}となる。このリストを「取り出し結果」と呼ぶことにする。

このように、list1（取り出し対象）、list2（取り出し指示）が決まると、「取り出し結果」が導ける。

そこで、「取り出し結果」を、list1とlist2を用いた従属オブジェクトとして、一般化して定義する方法を考えよう。

解答例

Element[Iteration[{RemoveUndefined[Join[{Take[Element[a, 1], 1, Element[Element[a, 2], 1] - 1], Take[Element[a, 1], Element[Element[a, 2], 1] + 1]}]], Take[Element[a, 2], 2], Join[{Element[a, 3], {Element[Element[a, 1], Element[Element[a, 2], 1]]}}]}, a, {{list1, list2, {}}}, Length[list2]], 3]

解説

総説

「要素を戻さず取り出す」ということを繰り返すわけだが、1回の取り出し作業を、いかにGeoGebraで表現するかがキーポイントである。

まずは、リスト{list1, list2}から出発しよう。これに対して同じ演算を繰り返していく。まずは、それぞれの演算で得られる結果が、それぞれの時点における

{ <現在残っている取り出し対象>, <未済の取り出し指示> }

を表せるように、演算の内容を構築してみよう。

演算の概要

演算の内容は、さしあたり、概略以下のようにする。

list2の最初の要素の値に従い、list1から要素を一つ取り出す。残りをlist1'とする。list2の最初の要素を削除し、list2'を得る。以上の演算から、{list1', list2'}を得る。これが、1回の取り出し作業を意味する。

{list1', list2'}に対しても、同様の演算を実行する。すなわち、list2'の最初の要素の値に従い、list1'から要素を一つ取り出す。残りをlist1''とする。list2'の最初の要素を削除し、list2''を得る。以上の演算から、{list1'', list2''}を得る。

同様の演算を、list2の要素数（Length[list2]）だけ繰り返せばよい。

GeoGebraにおける表現

以上の演算を、GeoGebraのコマンドを用いて表現してみよう。以下では、視認性を高めるため、リスト

{<要素1>, <要素2>}

を、

{

  <要素1>,

  <要素2>

}

と表すことがある。実際にGeoGebraの入力バーに入力する際は、改行を消して、1行にして頂きたい。

• 初期値

{

  list1,

  list2

}

• 演算

ある時点における、演算前の値をaとする*1。そうすると、aに1回の演算を行った結果は、以下のように表せる。

{

  RemoveUndefined[ Join[{ Take[Element[a, 1], 1, Element[Element[a, 2], 1] - 1], Take[Element[a, 1], Element[Element[a, 2], 1] + 1] }] ],

  Take[Element[a, 2], 2]

}

※ このリストを、以下では「演算リスト」と呼ぶ。

上記の最初の要素

RemoveUndefined[ Join[{ Take[Element[a, 1], 1, Element[Element[a, 2], 1] - 1], Take[Element[a, 1], Element[Element[a, 2], 1] + 1] }] ]

は、演算後に残っている取り出し対象を表す。

これを得るには、Join コマンドとTake コマンドを組み合わせて、演算前に残っている取り出し対象である Element[a, 1] から、Element[a, 1] の、「 Element[Element[a, 2], 1] 」番目の要素を取り除けばよい*2。

2番目の要素

Take[Element[a, 2], 2]

は、演算後における未済の取り出し指示を表す（その最初の要素が、次の演算における取り出し指示となる）。これを得るには、演算前における未済の取り出し指示 Element[a, 2] から、今行った演算指示（すなわち、の最初の要素）を削除したものである*3。

• 演算の繰り返し

演算の繰り返しを表現するには、演算の途中経過を含めて、結果をリストで返す IterationList コマンドや、繰り返しの最終結果のみを返す Iteration コマンドが有用である。

IterationList[ <演算リスト> , a, {{list1, list2}}, Length[list2] ]

すなわち

IterationList[ {RemoveUndefined[Join[{Take[Element[a, 1], 1, Element[Element[a, 2], 1] - 1], Take[Element[a, 1], Element[Element[a, 2], 1] + 1]}]], Take[Element[a, 2], 2]}, a, {{list1, list2}}, Length[list2] ]

とすれば、演算の経過をリストで得られる。

冒頭の設例では、下図のようなリストを得られる（下図は、得られたリストをTableText コマンドにかけたもの）。

1行目が初期値（左がlist1, 右がlist2）である。1回目の演算終了後の値が、2行目に書かれている。5回の演算を終えた最終結果が、6行目である。

上図の結果は、各時点における「取り出し対象の残り」と「未済の取り出し指示」を表している。これに対して、最終目的は、「取り出し結果」を得ること、すなわち、各演算において取り出したものを、演算順にすべて集めたリストである。そこで、初期値の末尾に「取り出し結果」をつけ加えて、演算を増築しよう。

演算の増築

• 初期値

{

  list1,

  list2,

  { }

}

初期値の3つ目の要素に、空のリストを加えた。後の演算で、取り出した要素を格納していく。

• 演算

ある時点における、演算前の値をaとする*4。そうすると、aに1回の演算を行った結果は、以下のように表せる。

{

  RemoveUndefined[ Join[{ Take[Element[a, 1], 1, Element[Element[a, 2], 1] - 1], Take[Element[a, 1], Element[Element[a, 2], 1] + 1] }] ],

  Take[Element[a, 2], 2],

  Join[{ Element[a, 3], {Element[Element[a, 1], Element[Element[a, 2], 1]]} }]

}

※ このリストを、以下では「増築演算リスト」と呼ぶ。

増築演算リストの第1,2要素は、演算リストと同じである。増えたのは、第3要素の

Join[{ Element[a, 3], {Element[Element[a, 1], Element[Element[a, 2], 1]]} }]

である。Element[a, 3] は、今回の演算前における取り出し結果である。それに、Joinコマンドを用いて、今回の演算において取り出してきた要素 Element[Element[a, 1], Element[Element[a, 2], 1]] を加えている。

• 演算の繰り返し

IterationList[ <増築演算リスト>, a, {{list1, list2, {}}}, Length[list2] ]

すなわち、

IterationList[ {RemoveUndefined[ Join[{Take[Element[a, 1], 1, Element[Element[a, 2], 1] - 1], Take[Element[a, 1], Element[Element[a, 2], 1] + 1]}] ], Take[Element[a, 2], 2], Join[{Element[a, 3], {Element[Element[a, 1], Element[Element[a, 2], 1]]}}]}, a, {{list1, list2, {}}}, Length[list2] ]

※ このリストを、以下では「全データリスト」と呼ぶ。

これによって得られるリストは、冒頭の設例では、下図のようになる（下図は、得られたリストをTableText コマンドにかけたもの）。

3列目が増えている。3列目の最終行 {3,4,8,2,1} が、本課題の目的である「取り出し結果」である。

この「全データリスト」は、取り出し対象の残り（1列目）、未済の取り出し指示（2列目）、取り出し結果（3列目）を、すべての取り出し作業について表示しており、取り出し作業（演算）の全貌が把握できる。

最終結果のみが知りたい場合は、上記の「全データリスト」の定義式のうち、「IterationList」を、「Iteration」に置き換えた、

Iteration[{RemoveUndefined[Join[{Take[Element[a, 1], 1, Element[Element[a, 2], 1] - 1], Take[Element[a, 1], Element[Element[a, 2], 1] + 1]}]], Take[Element[a, 2], 2], Join[{Element[a, 3], {Element[Element[a, 1], Element[Element[a, 2], 1]]}}]}, a, {{list1, list2, {}}}, Length[list2]]

※ このリストを、以下では「最終結果リスト」と呼ぶ。

を用いる。これは、全データリストをTableTextで表した場合の最終行である。上記説例においては、下図のようになる。

最終結果リストの3番目の要素が、本課題の目的である「取り出し結果」である。これは、

Element[ <最終結果リスト>, 3 ]

すなわち、

Element[ Iteration[{RemoveUndefined[Join[{Take[Element[a, 1], 1, Element[Element[a, 2], 1] - 1], Take[Element[a, 1], Element[Element[a, 2], 1] + 1]}]], Take[Element[a, 2], 2], Join[{Element[a, 3], {Element[Element[a, 1], Element[Element[a, 2], 1]]}}]}, a, {{list1, list2, {}}}, Length[list2]], 3 ]

 と表すことができる。

参考

下図は、

list1 = {1,2,3,4,5,6,7,8,9,10}

list2 = {10,3,6,2,1,4,2,3,2,1}

の場合の、全データリストを、TableTextで表したものである。

*1:上記の通り、aの初期値は、{list1, list2}である。

*2:JoinとTakeを組み合わせて、リストから特定のインデックスの要素を削除する構文は、

Join[{ Take[ <削除対象リスト>, 1, <削除したい要素のインデックス> - 1 ], Take[ <削除対象リスト>, <削除したい要素のインデックス> + 1] }]

である。

なお、削除したい要素のインデックスが、削除対象リストの最終インデックスの場合には、結果に未定義「?」が混入するようである。そのため、RemoveUndefined コマンドを入れてある。

また、要素を取り除くために、Remove コマンドを使うのは推奨できない。なぜならば、取り出し対象のリストに、同じ値をもつ要素が複数ある場合には、Remove コマンドは、そのうち一番インデックスが若い要素のみを削除するからである。場合によっては、同じ値をもつ複数の要素のうち、たとえば2番目にインデックスが若いものを取り除く必要があることも考えれば、Remove コマンドより、JoinとTakeを組み合わせる方が適切であろう。

*3:

Take[ <リスト>, 2 ]

で、リストの最初の要素だけを削除したものを得られる

*4:上記の通り、aの初期値は、{ list1, list2, {} }である。