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

Question

哪里有一个好的 JavaScript 数学集合实现？它应该包括交集、并集、补集和（奖励点）笛卡尔积的有效实现。

不，这不是家庭作业。我有一个 yubikey，它是一个 USB 键盘，可以输入从 16 个键码中选择的序列来输入 128 位一次性密码 (otp)。为了使其更有用，软件应根据生成的字符检测键盘布局，并将这些字符映射回“us”布局中的内容，以便与现有后端兼容。

因此，我有 93 个不同的 16 个字符序列，代表 yubikey 在 430 种键盘布局中的每一种中可以输入的所有内容。 （为此目的，许多布局都是相同的。）特定 otp 的可能映射是包含 otp 中每个字符的每个 16 个字符序列。

为了有效地找到这一点，我使用反向索引将每个可能的字符映射到使用该字符的键盘布局列表。答案是 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

我不知道任何现有的实现，但如果您的集合元素是字符串（或具有唯一的字符串表示形式），您可以非常轻松地使用 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，但通过 for 检查true 显式地，您会自动忽略可能附加到该对象的任何函数（以防有人修改了 Object.prototype，或者它不是一个普通对象）。

Answer 3

使用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); })
            );
        }, []);
    }, [[]]);
}

Answer 4

Sylvester 是一个很好的库，用于在 Javascript 中进行向量和矩阵数学运算。这是我现在能想到的唯一的数学库。

Answer 5

我个人喜欢 jPaq 中的实现方式（http://jpaq.org/documentation/数组+as+集合/1.0/）。以下是我测试成功的三个示例：

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 的好处是您可以下载代码对于这三个函数。 jPaq 做到了这一点，这样您就不必下载您不会使用的额外内容。

Answer 6

我已经完成了一个 JavaScript Set 实现，主要关注高效的差异，交集和并集操作。它位于 GitHub。非常欢迎分叉和新操作！ :-)

Answer 7

在引发这个问题的程序中，集合是数组，相交是

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

当然，它在ie中不起作用。