Skip to content

Instantly share code, notes, and snippets.

@binarymax
Forked from 140bytes/LICENSE.txt
Created September 4, 2011 20:47
Show Gist options
  • Save binarymax/1193484 to your computer and use it in GitHub Desktop.
Save binarymax/1193484 to your computer and use it in GitHub Desktop.
isSubset
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>
@tsaniel
Copy link

tsaniel commented Sep 5, 2011

I don't think using sort() is a good idea. It may change an array the original order.

@binarymax
Copy link
Author

Good point. I had room to copy the arrays with slice. If you can think of a better way please let me know.

@p01
Copy link

p01 commented Sep 7, 2011

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}

@p01
Copy link

p01 commented Sep 8, 2011

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

@jed
Copy link

jed commented Sep 8, 2011

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

@p01
Copy link

p01 commented Sep 8, 2011

Respect! Love this approach.

@pvdz
Copy link

pvdz commented Sep 8, 2011

Ah crap, I wasnt reading the comments. Meh! :) Very nice, I concede

@jdalton
Copy link

jdalton commented Sep 8, 2011

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

@binarymax
Copy link
Author

Very excellent! Thanks all :)

@p01
Copy link

p01 commented Sep 9, 2011

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}

@p01
Copy link

p01 commented Sep 10, 2011

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}

@atk
Copy link

atk commented Sep 10, 2011

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}

@jed
Copy link

jed commented Sep 10, 2011

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}

@jdalton
Copy link

jdalton commented Sep 10, 2011

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

@p01
Copy link

p01 commented Sep 10, 2011

@atk and @jed Sweeeet! Too bad, Array.indexOf is not supported in the previous version of IE :\

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

@jdalton
Copy link

jdalton commented Sep 10, 2011

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

@jdalton
Copy link

jdalton commented Sep 10, 2011

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)})}

@atk
Copy link

atk commented Sep 10, 2011

Nice one, though I'd still prefer it to be alongside a solution that does not require the browser to be ES5-compliant.

@p01
Copy link

p01 commented Sep 10, 2011

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)})}

@jdalton
Copy link

jdalton commented Sep 10, 2011

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

@atk
Copy link

atk commented Sep 13, 2011

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.

@FarSeeing
Copy link

Using Array#indexOf or === will fail on a = [NaN], b = [NaN]

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment