4

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

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

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

为了有效地找到这一点，我使用反向索引将每个可能的字符映射到使用该字符的键盘布局列表。答案是 otp 中每个唯一字符的反向索引的每个条目的交集。这几乎总是以恰好 1 个元素结束。

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

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

4

7 回答 7

11

通过使用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 的想法。

于 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 setorset.hasOwnProperty(item)代替set[item] === true，但是通过true显式检查，您会自动忽略可能附加到对象的任何函数（以防有人修改了 Object.prototype，或者它不是普通对象）。

于 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

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

于 2009-08-12T14:39:59.280 回答
1

我个人喜欢它在 jPaq ( http://jpaq.org/documentation/Arrays+as+Sets/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 做到了，因此您不必下载无论如何都不会使用的额外内容。

于 2011-03-16T21:56:01.240 回答
1

我已经完成了一个 JavaScript Set 实现，主要关注效率difference和操作。它在 GitHub 上可用。非常欢迎分叉和新操作！:-)intersectionunion

于 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 回答