What's a good mathematical sets implementation

问题:

Where is a good mathematical sets implementation for JavaScript? It should include efficient implementations of intersection, union, complement, and (for bonus points) the Cartesian product.

No, it's not homework. I got a yubikey, it is a USB keyboard that types a sequence chosen from 16 keycodes to type a 128-bit one time password (otp). To make it more useful, software should detect the keyboard layout based on the characters produced and map those characters back to what they would be in the "us" layout for compatibility with the existing backend.

So I've got 93 different sequences of 16 characters representing everything the yubikey can type in each of 430 keyboard layouts. (Many layouts are the same for this purpose.) The possible mappings for a particular otp is each 16-character sequence that contains every character in the otp.

To find this efficiently I use a reverse index mapping each possible character to a list of the keyboard layouts that use that character. The answer is the intersection of each entry of the reverse index for each unique character in the otp. This almost always winds up with exactly 1 element.

It would be easier to write this cross-browser with a good implementation of Set().

Code so far is at http://dingoskidneys.com/~dholth/yubikey/

回答1:

I don't know of any existing implementations, but if your set elements are strings (or have a unique string representation) you can use JavaScript objects pretty easily. The elements would be the object properties, and the value could be anything.

// 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.

You could also use item in set or set.hasOwnProperty(item) instead of set[item] === true, but checking by for true explicitly, you automatically ignore any functions that might be attached to the object (in case someone modified Object.prototype, or it's not a plain object).

回答2:

By using jPaq or another JavaScript library that implements the Array.prototype.reduce and Array.prototype.forEach functions, you can create a cartesian product function that accepts two or more arrays. Here is code for a function that computes the cartesian product of two or more arrays:

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

As far as this being in a library, I am open to suggestions for the naming of the function so that I can add it into jPaq. By the way, so as not to plagiarize, I did get the idea of using reduce from this post.

回答3:

Using Underscore's reduce method.

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

回答4:

Sylvester is a good library for doing vector and matrix Math in Javascript. It's the only Math library I can think of right now.

回答5:

I personally like how it is done in jPaq (http://jpaq.org/documentation/Arrays+as+Sets/1.0/). Here are three examples that I tested out successfully:

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]

The nice thing about jPaq is the fact that you can just download the code for these three functions. jPaq makes it so you don't have to download the extra stuff that you will not be using anyway.

回答6:

I've done a JavaScript Set implementation mainly concerned with efficient difference, intersection and union operations. It's available at GitHub. Forks and new operations are very welcome! :-)

回答7:

In the program that sparked this question, a set is an Array and intersect is

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

Of course it doesn't work in ie.