Algorithm to return all subarrays of a given array

[SlurrerOfSpeech]

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

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

 

[Filip Larsen]

Perhaps you can use the fact that for a list of n elements there are 2ⁿ 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.

 

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

 

[SlurrerOfSpeech]

Perhaps you can use the fact that for a list of n elements there are 2ⁿ 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.

Genius! I'm going to do that.

 

[SlurrerOfSpeech]

Worked beautfiully. Thanks!

This ended up being my implementation:

// 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; 
}

 

[kitarp]

could someone give the code in c++?please

 

[pbuk]

The JavaScript code is very easy to follow, if your knowledge of C++ is not sufficient to translate it then do you think you will to be able to use it?

 

[kitarp]

The JavaScript code is very easy to follow, if your knowledge of C++ is not sufficient to translate it then do you think you will to be able to use it?

Sorry but i don't know javascript and really didn't understood the logic either so if someone could share a C++ snippet it might would have Helped me out

 

[Filip Larsen]

Regarding the logic of the Javascript code in this thread it is really simple:

1. Given is an array a of length n.
2. For each i from zero to 2ⁿ do
   1. Set array sa = []
   2. For each j from zero to n do
      1. If the i has the j'th bit set then append a[j] to sa.
   3. Use sa for something.

Of course, if you go with implementing this in C++ then all of the above lines will give rise to considerations on how to map this onto C++ data types and similar.

Edit: removed my somewhat brain-farted recommendation for using std::next_permutation as this of course does permutations and not sampling.