-
-
Save binarymax/1193484 to your computer and use it in GitHub Desktop.
| function( | |
| S, //The Set array | |
| u, //The Subset array to check | |
| b, //Set index | |
| s, //Subset index | |
| e, //Set length | |
| t //Subset length | |
| ) { | |
| var A=S.slice().sort(), //copy and sort set array | |
| B=u.slice().sort(); //copy and sort subset array | |
| b=s=0; //init indexes | |
| e=S.length; //get array lengths | |
| t=u.length; | |
| while(b<e&&s<t) //go until one array hits the end | |
| if(A[b++]==B[s])s++; //if element found from subset in set, inc subset index | |
| return s==t //returns true if every subset element exists | |
| } |
| function(S,u,b,s,e,t){var A=S.slice().sort(),B=u.slice().sort();b=s=0;e=S.length;t=u.length;while(b<e&&s<t)if(A[b++]==B[s])s++;return s==t} |
| DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE | |
| Version 2, December 2004 | |
| Copyright (C) 2011 Max Irwin http://www.binarymax.com/ | |
| Everyone is permitted to copy and distribute verbatim or modified | |
| copies of this license document, and changing it is allowed as long | |
| as the name is changed. | |
| DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE | |
| TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION | |
| 0. You just DO WHAT THE FUCK YOU WANT TO. |
| { | |
| "name": "isSubset", | |
| "description": "Checks if array 'u' is subset of array 'S'.", | |
| "keywords": [ | |
| "subset", | |
| "set" | |
| ] | |
| } |
| <!DOCTYPE html> | |
| <title>Foo</title> | |
| <div>Expected value: <b>true,false,true,true</b></div> | |
| <div>Actual value: <b id="ret"></b></div> | |
| <script> | |
| // write a small example that shows off the API for your example | |
| // and tests it in one fell swoop. | |
| var f = function(S,u,b,s,e,t){var A=S.slice().sort(),B=u.slice().sort();b=s=0;e=S.length;t=u.length;while(b<e&&s<t)if(A[b++]==B[s])s++;return s==t} | |
| var a = ["apples","oranges","bananas","grapes","strawberries"]; | |
| var b = ["strawberries","bananas"]; | |
| var c = ["strawberries","kiwis"]; | |
| var d = []; | |
| var r1 = f(a,b); // b is a subset of a | |
| var r2 = f(a,c); // c is not a subset of a | |
| var r3 = f(a,d); // The empty set is a subset | |
| var r4 = f(a,a); // A set is a subset of itself | |
| document.getElementById( "ret" ).innerHTML = r1 + ',' + r2 + ',' + r3 + ',' + r4; | |
| </script> |
Good point. I had room to copy the arrays with slice. If you can think of a better way please let me know.
114 bytes ;)
function(a,b){for(var A=a.slice().sort(),B=b.slice().sort(),c=A.length,d=B.length;c*d;)d-=A[--c]==B[d-1];return!d}
111 bytes
function(a,b){for(var A=a.slice().sort(),B=b.slice().sort(),d=B.length;A.length*d;)d-=A.pop()==B[d-1];return!d}
Kudos to @kuvos for the hint
function(a,b,c,d){for(c={},d=a.length;d--;c[a[d]]=1);for(a in b)d*=b[a]in c;return!!d}86 bytes
Respect! Love this approach.
Ah crap, I wasnt reading the comments. Meh! :) Very nice, I concede
Tested @jed's 86 byte snippet and it will cause false positives/negatives if say
var f = function(a,b,c,d){for(c={},d=a.length;d--;c[a[d]]=1);for(a in b)d*=b[a]in c;return!!d};
var a = ['apples', 'oranges', 'bananas', 'grapes', 'strawberries'];
var b = ['constructor', 'hasOwnProperty', 'isPrototypeOf', 'propertyIsEnumerable', 'toLocaleString', 'toString', 'valueOf'];
f(a,b) // returns true, but should be false
// OR
var x = { 'x': 1 };
var y = { 'y': 1 };
var a = [x];
var b = [y];
f(a,b) // returns true, but should be false
// OR (a false negative)
var x = {
'i': 0,
'toString': function() {
return 'id' + this.i++;
}
};
var a = [x];
var b = [x];
f(a,b) // returns false, but should be true
Very excellent! Thanks all :)
The .slice() returns a "copy" of the arrays which prevents the .sort() from reordering the original variables, therefore we can reuse the arguments a and b, which bring us down to 109 bytes
function(a,b,c){for(a=a.slice().sort(),b=b.slice().sort(),c=b.length;a.length*c;)c-=a.pop()==b[c-1];return!c}
Sacrificing a little speed saves another 4 bytes ➡ 105 bytes
function(a,b,c){for(a=a.slice().sort(),c=b.length;a.length*c;)c-=a.pop()==b.slice().sort()[c-1];return!c}
My smallest version using indexOf to golf this down to 71 bytes (though it does not take care of manipulated toString property):
function(a,b,c,d){for(d=c=b.length;c--;d=d*~a.indexOf(b[c]));return!!d}
hey, using indexOf is cheating! heh.
you still have a byte to squeeze tho:
function(a,b,c,d){for(d=c=b.length;c--;d*=~a.indexOf(b[c]));return!!d}
Besides the issues with solutions that rely on string coercion / for..in, others, including the original, that rely on Array#sort, like @p01's, can give a false negative with say
var f = function(a,b,c){for(a=a.slice().sort(),c=b.length;a.length*c;)c-=a.pop()==b.slice().sort()[c-1];return!c};
var x = { 'x': 1 };
var y = { 'y': 1 };
var a = [x, y];
var b = [y, x];
f(a, b); // returns false, but should be true
@jdalton Alas, that's an issue with EVERY implementations here. To avoid the false negative, you'd have to do a strict ( and deep ? ) comparison of the items.
Nope, atk's solution (I don't know if it was intentional because his wording makes me think he meant to use String#indexOf) avoids all false positives/negatives presented (even those tests with custom toString() methods). As you pointed out it requires ES5 Array#indexOf or a compliant shim for those enviro's that don't have it.
if Array#indexOf is allowed then lets go with a 63 byte one that uses Array#indexOf and Array#every:
function(a,b){return b.every(function(b){return~a.indexOf(b)})}
Nice one, though I'd still prefer it to be alongside a solution that does not require the browser to be ES5-compliant.
Thanks for the info about ES5 Array.indexOf et al.
Btw, you mixed up the two arguments in your 63 bytes implementation. It should read:
function(a,b){return b.every(function(b){return~a.indexOf(b)})}
@p01 yap, I typo'ed and corrected it shortly after (before your comment on it). Reviewing the actual comment instead of the email notification will help prevent mixups like that.
Shortest non ES5-Fallback (tested against Jon's cases):
function(a,b,c,d,e,f){f=0;for(d in b){e=0;for(c in a)e+=a[c]===b[d];f+=e}return!!f}
83bytes, tested in FF6, probable issues with for...in in some engines, yet untested.
Using Array#indexOf or === will fail on a = [NaN], b = [NaN]
I don't think using sort() is a good idea. It may change an array the original order.