見出し画像

総当たりにおけるペアの特定方法

yssymmt

問題

幾つかの事象が同時発生することを考えるとき、総当たりの計算を行うことが多々あります。
事象がA=アメを買う、B=ブラウニーを買う、C=クッキーを買う、であるとすると、AとA、AとB、AとC、BとA、BとB、BとC、CとA、CとB、CとCが総当たりの同時発生事象です。このうちAとAのような同じ事象同士を考慮しない場合、これは左事象=右事象という条件で除外できます。そしてAとB、BとAという組み合わせは同じことを指していて、どちらかでよいときは、AとBの順序付けを行い左事象>右事象もしくは左事象<右事象で除外できます。しかしながらAとB、BとAという右左を入れ替えたペアを特定したい場合にどうするのが良いのだろう、というのが今回の問題です。答えは半分出ていて、実務でこのような問題に直面した際には以下のようなアプローチを採用しているのですが、これが普遍的な答えなのか不安があります。

アプローチ

採用しているアプローチは、まずA、B、Cに順序番号を付けます。例えばA=1、B=2、C=3です。そして総当たりでペアを作成した時に、左事象+右事象、左事象*右事象というデータを作成します。例えばAとBでは、1+2=3、1*2=2となります。これはBとAでも同じ値となります。この3と2という組み合わせは、BとC(5と6)、CとA(4と3)、またはその逆においても発生しないため、この2つをユニークに特定するのはこの2つの和と積によって可能となるというものです。

SQL

実際のSQLで試してみたのが以下です。Teradataのシステムカレンダーテーブルに1から7万程度の整数データが重複なくあるのでそれを左側と右側の順序番号とみなし、総当たりさせます。ここでは1万件で絞り込んでいるため、一時的にデータは1億件になるはずです。このデータに対して
同一事象同士はwhere句で除外します。これによって1万件が除外され、データは9,999万件となります。そして上述のように左側と右側の和(c3)、そして積(c4)を計算します。和と積の結果は左と右が入れ替わっても変わらないため、ペアとなるデータは同じになるはずです。ただ問題は、他のペアが同じ組み合わせになることがあるのだろうかという点です。仮に同じ組み合わせになるとするならば、count(*)の結果は2超、4とかになるはずですので、最後のクエリーでこれの最大値を取得しています。最大値が2に収まっていればユニークにペアを特定できている、2を超えれば特定できていないということになります。

select 
max(cnt) as maxcnt 
from ( 
	select 
	c3, 
	c4, 
	count(*) as cnt 
	from ( 
		select 
		c1, 
		c2, 
		c1+c2 as c3, 
		c1*c2 as c4 
		from ( 
			select 
			day_of_calendar as c1 
			from sys_calendar.calendar 
			where c1<=10000 
		) t1 cross join ( 
			select 
			day_of_calendar as c2 
			from sys_calendar.calendar 
			where c2<=10000 
		) t2 
		where c1<>c2 
	) t3 
	group by 1,2 
) t4 
;

1万件で試してみた結果は2に収まり、1万件の範囲内であればこのロジックは使えるということが言えます。1万件で通じるということは、例えば7,000件でも1万件総当たりの部分集合であるため通じるでしょう。しかしながら、これが10万件、100万件でも同様に、普遍的なロジックで使えるのかというのが未証明です。上述のように実務上は起こりうる総当たりの規模に応じてこの計算をあらかじめ行い、通用することを確認したうえで利用すればよいため、さしあたっての問題はないのですが、一方で数字は無限に大きく、何千万件で確認したところで普遍性は担保できず、すっきりしないままです。

抽象化

一応抽象化して考えると以下のようになります。

A+B, A*Bにおいて、Aに対してM分増加させ、
Bに対してN分増加させたとき、
その値は(A+M)+(B+N)と(A+M)*(B+N)となる。
このときにA+B = (A+M)+(B+N)
なおかつA*B = (A+M)*(B+N)となるMとNを考える。
ただしA≠Bであり、A>0、B>0である。

 

  • A+B = (A+M)+(B+N)から、両辺のA+Bを消してM+N = 0、
    変形してM = -Nとなる

  • これを代入するとAB = (A-N)(B+N)が言える

  • これを展開するとAB+NA-NB-NN = ABとなり、
    ABが両辺にあるので消すとNA-NB-NN = 0となる

  • これに対して両辺をNで割るとA-B-N = 0となる

  • ここまでで以下の4つが言える

    • M = -N

    • N = A-B

    • A = B+N

    • B = A-N = A+M

  • これを利用すると元の式A+B = (A+M)+(B+N)における右辺はB+Aとなることから、AをBにするM、BをAにするNが式を成り立たせる条件となる

  • 言い換えると、求めるMとNはAとBを入れ替えるように作用させるもののみであり、結果的にAとBを入れ替えたことに等しい。故にAとBを入れ替えた際にのみ条件が成り立つ

  • これはもう一つの式であるAB = (A+M)(B+N)においても同様となる

どこかに落とし穴がありそうな気もしてすっきりしないのですが、とりあえずは以上です。

///

#sql #teradata  

いいなと思ったら応援しよう！