配列内に重複がないことを確認するには？

８月１日木曜日、晴れ

暑い。

今日もおもいたってしまった帰り道。
一駅分走って帰ろうと１キロ過ぎたあたりで見事につったふくらはぎ。
めっちゃ痛い。どうしようかしらん？　ピンチ！
だったけれどしばらく歩いてごまかして、痛むのを無視してふたたび走って帰った。
こんなんすると、明日以降ひどいことになるのかな？
とりあえず階段の昇り降りが辛くて悶絶。

いたいよう　いたいよう　あんよがいたいよう。

おなかがいたいこねずみ｜福音館書店

＊　＊　＊

配列内に重複要素がないことを確かめるには？　というお題を考えていて、とりあえずこんなのをひねり出していた。

const noDup = vs => {
	let f = _ => true;
	for (let v of vs) {
		if (f(v)) {
			const g = f;
			f = x => x != v && g(x);
		} else {
			return false;
		}
	}
	return true;
}

N 番目の要素を取り出して、それまで見てきた N - 1 番目までに同じ値がないことを確認する。この N を１から配列の長さになるまで繰り返して、すべて確認が終われば OK、そうでなければ NG。

ほぼ同じロジックを配列のインデックスアクセスだけで実現するならこんな感じになる。

const noDup = vs => vs.lenght < 2 || (N => {
  var i;
  for (i = 1; i != N && ((M, X) => {
    var j;
    for (j = 0; j != M && vs[j] != X; j += 1)
      ;
    return j == M;
  })(i, vs[i]); i += 1)
    ;
  return i == N;
})(vs.length);

＊　＊　＊

長さ N の配列 b のすべての要素に重複がないこと。これを愚直に書くとこうなる。

（∀ i, j: 0 <= i < N ∧ 0 <= j < N ∧ ¬(i = j): ¬(b[i] = b[j])）

つまり N より小さい i と j を考え、これが互いに異なるすべての組み合わせに対して b の i 番目の要素と j 番目の要素は違う値になる。

証明していないんだけれど、もうちょっと比較する範囲を狭められるはずで、たとえば：

（∀ i: 0 <= i < N - 1: （∀ j: i + 1 <= j < N: ¬(b[i] = b[j])））

配列の先頭から順に要素を取り出して、そこから後ろに同じ要素がないこと。次の要素を取り出して、そこから後ろに同じ要素がないこと。さらに次の要素を取り出して……、と、これを配列の終端まで続ける。

あるいは先ほどのコードは次の命題を実装したもの：

（∀ i: 1 <= i < N: （∀ j: 0 <= j < i: ¬(b[i] = b[j])））

ある要素を取り出して、そこまでに同じ値を持つものがない。

＊　＊　＊

いくつかの命題が同じ値を持つことを証明したり、その命題とプログラムが等価であることを示したり。

これを自分の道具箱にきちんと納められたらなあ……