JavaScript中的数学集合实现是什么？

Question

JavaScript的数学集合实现在哪里？它应该包括交叉,联合,补充和(对于奖励积分)笛卡尔积的有效实现.

不,这不是功课.我有一个yubikey,它是一个USB键盘,键入从16个密钥代码中选择的序列,键入一个128位的一次性密码(otp).为了使其更有用,软件应根据生成的字符检测键盘布局,并将这些字符映射回"us"布局中的内容,以便与现有后端兼容.

所以我有93个不同的16个字符序列,代表yubikey可以在430个键盘布局中输入的所有内容.(为此目的,许多布局都是相同的.)特定otp的可能映射是每个16个字符的序列,其中包含otp中的每个字符.

为了有效地找到它,我使用反向索引将每个可能的字符映射到使用该字符的键盘布局列表.答案是otp中每个唯一字符的反向索引的每个条目的交集.这几乎总是与1个元素结合在一起.

用一个很好的实现来编写这个跨浏览器会更容易Set().

到目前为止的代码是http://dingoskidneys.com/~dholth/yubikey/

Answer 1

通过使用jPaq或其他实现Array.prototype.reduce和Array.prototype.forEach函数的JavaScript库,您可以创建一个接受两个或更多数组的笛卡尔积函数.以下是计算两个或多个数组的笛卡尔积的函数的代码:

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的想法.

Answer 2

我不知道任何现有的实现,但如果您的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或set.hasOwnProperty(item)代替set[item] === true,但true明确地检查,您自动忽略可能附加到对象的任何函数(如果有人修改了Object.prototype,或者它不是普通对象).