javascript - Create a filtered power set in reverse order -

i'm not sure if need has name, it's pretty close power set. here's desire:

input:[1,2,3,4]  output: [1,2,3,4] [1,2,3] [1,2,4] [1,3,4] [1,2] [1,3] [1,4] 

this differs power set in 3 ways:

1. all subsets include first value (1)
2. the minimum size of subset 2
3. the order goes longest shortest

my current solution create power set, filter out values don't start first value, , reverse sort. slow i'm looking better solution.

from longest shortest, run test on each subset until find set returns true. makes me wonder if use generator don't have create values @ once (nice have, not necessary since max size ~25 members, or ~33mm sets).

any appreciated!

generating power set done using bit masks.

consider set a = {1, 2, 3, 4}. define 4 element boolean vector , denote i. now, define b = { a[i] | i[i] = true }. there 2 things notice:

1. b subset of a.
2. by iterating on possible values of i can generate subsets
3. a integer number's bits can used i treating each of bits single boolean value.

that being said, here's algorithm generates subsets of array:

"use strict"; var input = [1, 2, 3, 4];  var ismemberinset = function (indexingvector, _, index) {     return indexingvector & (1 << index); }  var subsetcount = math.pow(2, input.length); (var indexingvector = 0; indexingvector < subsetcount; indexingvector++) {     var subset = input.filter(ismemberinset.bind(undefined, indexingvector));     console.log(subset); } 

but can better! in fact, few simple modifications of above algorithm can solve entirely problem.

firstly, need include first value of array, need mirror indexing vector generation. in other words, redefine b = { a[i.length - - 1] | i[i] = true }.

secondly, need iterate indexing vector in reverse order means:

for (var = subsetcount - 1; >= 0; i--) 

thirdly, don't care subsets, of length > 2 need not iterate way 0, instead iterate until pow(2, input.length - 1) indexing vector contains first , second values , other values indexing vector don't include first value:

var subsetscontainingthefirstvalue = math.pow(2, input.length - 1); (var = subsetcount - 1; > subsetscontainingthefirstvalue; i--) 

finally, arrive @ code:

"use strict";    var input = [1, 2, 3, 4];  var integersize = 32;  var ismemberinset = function (indexingvector , _, index) {     return indexingvector & (1 << (input.length - index - 1)); }  var subsetcount = math.pow(2, input.length); var subsetscontainingthefirstvalue = math.pow(2, input.length - 1); (var indexingvector  = subsetcount - 1; indexingvector  > subsetscontainingthefirstvalue; indexingvector --) {     var subset = input.filter(ismemberinset.bind(undefined, indexingvector ));     console.log(subset); } 

output:

[1, 2, 3, 4] [1, 2, 3] [1, 2, 4] [1, 2] [1, 3, 4] [1, 3] [1, 4] 

note: code above works fact mentioned maximum number of elements 25. if number more 32, wouldn't have been able use integers , have instead needed boolean arrays.