4

JavaScript の適切な数学的セットの実装はどこにありますか? 交差、結合、補数、および (ボーナス ポイントの場合) デカルト積の効率的な実装を含める必要があります。

いいえ、宿題ではありません。yubikey を入手しました。これは、16 個のキーコードから選択したシーケンスを入力して、128 ビットのワンタイム パスワード (otp) を入力する USB キーボードです。より便利にするために、ソフトウェアは、生成された文字に基づいてキーボード レイアウトを検出し、既存のバックエンドとの互換性のために、それらの文字を "us" レイアウトに戻す必要があります。

つまり、430 のキーボード レイアウトのそれぞれで yubikey が入力できるすべてを表す 16 文字の 93 の異なるシーケンスがあります。(この目的のために、多くのレイアウトは同じです。) 特定の otp の可能なマッピングは、otp 内のすべての文字を含む各 16 文字のシーケンスです。

これを効率的に見つけるために、考えられる各文字をその文字を使用するキーボード レイアウトのリストにマッピングする逆インデックスを使用します。答えは、otp 内の各一意の文字の逆インデックスの各エントリの共通部分です。これはほとんどの場合、正確に 1 つの要素で終わります。

の適切な実装を使用して、このクロスブラウザーを作成する方が簡単ですSet()。

これまでのコードはhttp://dingoskidneys.com/~dholth/yubikey/にあります

4

7 に答える 7

11

Array.prototype.reduce および Array.prototype.forEach 関数を実装するjPaqまたは別の JavaScript ライブラリを使用することにより、2 つ以上の配列を受け入れるデカルト積関数を作成できます。以下は、2 つ以上の配列のデカルト積を計算する関数のコードです。

function cartesianProductOf() {
  return Array.prototype.reduce.call(arguments, function(a, b) {
    var ret = [];
    a.forEach(function(a) {
      b.forEach(function(b) {
        ret.push(a.concat([b]));
      });
    });
    return ret;
  }, [[]]);
}

これがライブラリにある限り、関数の命名に関する提案を受け入れて、jPaqに追加できるようにします。ところで、盗作を避けるために、私はこの記事からreduceを使用するというアイデアを思いつきました。

于 2011-04-11T19:53:29.067 に答える
6

既存の実装については知りませんが、set要素が文字列である（または一意の文字列表現を持っている）場合は、JavaScriptオブジェクトを非常に簡単に使用できます。要素はオブジェクトのプロパティになり、値は何でもかまいません。

// Make a set from an array of elements
function makeSet(items) {
    var set = {};
    for (var i = 0; i < items.length; i++) {
        set[items[i]] = true;
    }
    return set;
}

function copyInto(s, copy) {
    for (var item in s) {
        if (s[item] === true) {
            copy[item] = true;
        }
    }
}

function union(s1, s2) {
    var u = {};
    copyInto(s1, u);
    copyInto(s2, u);
    return u;
}

function intersection(s1, s2) {
    var i = {};
    for (var item in s1) {
        if (s1[item] === true && s2[item] === true) {
            i[item] = true;
        }
    }
    return i;
}

function difference(s1, s2) {
    var diff = {};
    copyInto(s1, diff);
    for (var item in s2) {
        if (s2[item] === true) {
            delete diff[item];
        }
    }
    return diff;
}

// etc.

の代わりにitem in setまたはを使用することもできますが、明示的にチェックすると、オブジェクトにアタッチされている可能性のある関数が自動的に無視されます（誰かがObject.prototypeを変更した場合、またはプレーンオブジェクトではない場合）。set.hasOwnProperty(item)set[item] === truetrue

于 2009-08-12T22:51:47.020 に答える
2

Underscoreの reduce メソッドを使用します。

function cartesianProductOf(){
    return _.reduce(arguments, function(mtrx, vals){
        return _.reduce(vals, function(array, val){
            return array.concat(
                _.map(mtrx, function(row){ return row.concat(val); })
            );
        }, []);
    }, [[]]);
}
于 2011-10-28T19:43:27.253 に答える
1

個人的には、jPaq ( http://jpaq.org/documentation/Arrays+as+Sets/1.0/ ) で行う方法が気に入っています。以下に、私がうまくテストした 3 つの例を示します。

alert([1,2,3,4,5].subtract([2,3,5]));  // evaluates to [1,4]
alert([1,2,5].union([1,3,4,5]));  // evaluates to [1,2,5,3,4]
alert([1,2,3,5].intersect([0,1,2,4,6]));  // evaluates to [1,2]

jPaq の優れた点は、これら 3 つの関数のコードをダウンロードできることです。jPaq は、とにかく使用しない余分なものをダウンロードする必要がないようにします。

于 2011-03-16T21:56:01.240 に答える
1

Sylvesterは、Javascript でベクトルと行列の計算を行うための優れたライブラリです。それは私が今考えることができる唯一の数学ライブラリです。

于 2009-08-12T14:39:59.280 に答える
1

主に効率的な,および操作に関係する JavaScript Set の実装を行いました。GitHub で入手できます。フォークと新しい操作は大歓迎です! :-)differenceintersectionunion

于 2012-01-06T12:16:57.623 に答える
0

この質問を引き起こしたプログラムでは、セットは配列であり、交差は

s = [1,2,3];
q = [3,4,5];
sq = s.filter(function(x) {
    return q.indexOf(x) >= 0;
});

もちろん、ieでは機能しません。

于 2009-08-12T14:52:49.070 に答える