JSの配列で集合算を考えてみた
どんなプログラミングでも基本的な配列の操作において、集合算を実装したいということはあるかと思います。言語仕様やライブラリに実装されていればそれを使えばよいですが、そうでない場合に自分で実装せざるをえないなくなったり、興味や頭の体操で実装してみたくなることもあるかと思います。
新しいJavaScriptではSetオブジェクトが定義されているようですが、(→[Link]「ECMAScript Language Specification ECMA-262 6th Edition – DRAFT」)こちらにもとりあえず集合算は見当たりません。
前からある配列(Arrayオブジェクト)で集合算をするロジックを考えてみました。具体的には2つの配列から新しい結果の配列を返す関数を考えてみました。Arrayは重複を許しますので、重複を排除しつつ計算します。和集合は全ての要素だから簡単ですが、共通部分は割と複雑です。ひとまとめにして、とりあえず以下のような関数を実装してみました。
配列Aと配列Bを集合A,Bとみなして(重複は排除)、全体の和集合A∪BをA-BとA∩BとB-Aに分けて、演算の種類に応じて各集合から要素を新しい配列に詰めるかどうかを指定します。
var MathSet; MathSet = {}; MathSet.Operator = {}; MathSet.Operator.Union = [1,1,1]; MathSet.Operator.Intersection = [0,0,1]; MathSet.Operator.DiffLR = [1,0,0]; MathSet.Operator.DiffRL = [0,1,0]; MathSet.Operator.SymmDiff = [1,1,0]; MathSet.Operation = function(arrayA, arrayB, operator) { var ptnA = [operator[0]]; var ptnB = [operator[1]]; var ptnAB = [operator[2]]; var set = {}; for (var i = 0; i < arrayA.length; i++) { set[arrayA[i]] = ptnA; } for (var j = 0; j < arrayB.length; j++) { set[arrayB[j]] = (set[arrayB[j]] && set[arrayB[j]] != ptnB) ? ptnAB : ptnB; } var newArr = []; for (var v in set) { if (set[v][0] == 1) { newArr.push(v); } } return newArr; };
以下のように使用します。(exec()をボタンのonclickなどで指定して、クリックで実行します。)
function exec(){ var A = [1,2,3,3,1,2]; var B = [2,3,5,6,3,6,8]; result=""; result+="arrayA:\t";result+=A;result+="\r\n"; result+="arrayB:\t";result+=B;result+="\r\n"; result+="\r\n"; result+="A∪B:\t";result+=MathSet.Operation(A, B, MathSet.Operator.Union);result+="\r\n"; result+="A∩B:\t";result+=MathSet.Operation(A, B, MathSet.Operator.Intersection);result+="\r\n"; result+="A-B:\t";result+=MathSet.Operation(A, B, MathSet.Operator.DiffLR);result+="\r\n"; result+="B-A:\t";result+=MathSet.Operation(A, B, MathSet.Operator.DiffRL);result+="\r\n"; result+="XOR:\t";result+=MathSet.Operation(A, B, MathSet.Operator.SymmDiff);result+="\r\n"; alert(result); }
結果:
arrayA: 1,2,3,3,1,2 arrayB: 2,3,5,6,3,6,8 A∪B: 1,2,3,5,6,8 A∩B: 2,3 A-B: 1 B-A: 5,6,8 XOR: 1,5,6,8
実行例では、数字要素のサンプルとしましたが、文字列要素などでももちろん実行可能です。
もっと効率が良くて、短いもの、解かりやすいものを考えたならばぜひ教えてください。