Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

JavaScript Algorithm to return all subarrays of a given array

  1. Jul 1, 2016 #1
    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. jcsd
  3. Jul 1, 2016 #2

    Filip Larsen

    User Avatar
    Gold Member

    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.
     
  4. Jul 1, 2016 #3
    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.
     
  5. Jul 1, 2016 #4
    Genius! I'm going to do that.
     
  6. Jul 1, 2016 #5
    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;
    }
     
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Algorithm to return all subarrays of a given array
Loading...