Algorithm to return all subarrays of a given array

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

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

Answers and Replies

  • #2
Filip Larsen
Gold Member
1,344
258
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.
 
  • Like
Likes FactChecker and jim mcnamara
  • #3
489
189
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
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.
Genius! I'm going to do that.
 
  • #5
Worked beautfiully. Thanks!

This ended up being my implementation:

Code:
// 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; 
}
 
  • Like
Likes jim mcnamara and Pepper Mint
  • #6
2
0
could someone give the code in c++?please
 
  • #7
pbuk
Science Advisor
Gold Member
1,996
797
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?
 
  • #8
2
0
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
 
  • #9
Filip Larsen
Gold Member
1,344
258
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 2n 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.
 
Last edited:

Related Threads on Algorithm to return all subarrays of a given array

Replies
13
Views
1K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
4
Views
2K
Replies
4
Views
686
  • Last Post
Replies
1
Views
3K
Replies
2
Views
3K
Replies
7
Views
1K
Replies
10
Views
5K
Top