# JavaScript Algorithm to return all subarrays of a given array

1. Jul 1, 2016

### SlurrerOfSpeech

I can't find this exact algorithm anywhere on the internet. What I'm trying to implement is the following function

Code (Text):

// Returns all subarrays of the given array, not including the empty array
// ex. [a,b,c].subarrays() = [ [a], [b], [c], [a,b], [a,c], [b,c], [a,b,c] ]
Array.prototype.subarrays = function(...)
{
// ..
}

in a larger program I'm writing. (I know how to do it easily if the subarrays are contiguous sequences of the original array)

Also, if this makes things easier, in the single use case of my program the original array has unique items.

2. Jul 1, 2016

### Filip Larsen

Perhaps you can use the fact that for a list of n elements there are 2n sub-lists, including the empty one. For instance, if there is 8 elements, then if you iterate i from 1 to 256 then the each of the 8 bits for each value of i will tell whether or not to include the element corresponding to each bit.

3. Jul 1, 2016

### JorisL

Filip's solution seems the most elegant to me.

You don't want the empty set i.e. the number $(0000\,\, 0000)_2=(0)_{10}$ isn't a part of the list you generate.
The first one would be $(0000\,\, 0001)_2=(1)_{10}$, the second one $(0000\,\, 0010)_2=(2)_{10}$ and so on.
So it is a simple sequence $1,2,\ldots ,256$ that you have to relate to the correct subsets of your array.

E.g. right-most bit corresponds to "array[0]" and so on.

This won't give you an array of subarrays ordered by length of said subarrays so you might have to do a sorting step if you want this.
In that case the sorting is likely the most expensive part of the code (if you need to optimize the code sometime later on). Perhaps a specialized sorting algorithm can use the pattern found in the length of the generated subarrays.

4. Jul 1, 2016

### SlurrerOfSpeech

Genius! I'm going to do that.

5. Jul 1, 2016

### SlurrerOfSpeech

Worked beautfiully. Thanks!

This ended up being my implementation:

Code (Text):

// Returns all subarrays of the given array, not including the empty array
// ex. [a,b,c].subarrays() = [ [a], [b], [c], [a,b], [a,c], [b,c], [a,b,c] ]
Array.prototype.subarrays = function()
{
var subs = [];
for(var i = 0, n = Math.pow(2,this.length); i < n; ++i)
{
var sub = [];
for(var j = 0; j < this.length; ++j)
{
if (((i >> j) & 1) == 1)
sub.push(this[j]);
}
subs.push(sub);
}
return subs;
}