Wednesday, July 28, 2021

javascript get all subsets of an array, then sort subsets by length, and preserve order

This stackoverflow  had an elegant all permutations generator:

const getAllSubsets = 
      theArray => theArray.reduce(
        (subsets, value) => subsets.concat(
         subsets.map(set => [value,...set])
        ),
        [[]]
      );
const elems = [1,2,3];
console.log(JSON.stringify(getAllSubsets(elems)));

I can't say I really understand how it works! But here is the output:

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

I realized I would like it better if we sorted by length... the empty set, each single entry set, each 2 entry set... 

console.log(JSON.stringify(
      getAllSubsets(elems)
          .sort((a,b)=>a.length - b.length)
));

That made

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

Much better! But still, it would be cool if each individual array was sorted - not on the value but based on the order in the original set:

So I end up making

console.log(JSON.stringify(
      getAllSubsets(elems)
          .sort((a,b)=>a.length - b.length)
          .map(arr=>arr.sort((a,b)=>elems.indexOf(a) - elems.indexOf(b)  ))
));

That's cool! let me change elems to ["Foo", "Bar", "Baz"]:

[[],['Foo'],['Bar'],['Baz'],['Foo','Bar'],['Foo','Baz'],['Bar','Baz'],['Foo','Bar','Baz']]

Perfect!

UPDATE: the Typescript version that function is

const getAllSubsets = (theArray:string[]) => theArray.reduce(
        (subsets, value) => subsets.concat(
          subsets.map(set => [value,...set])
        ), [[] as string[]]
);

No comments:

Post a Comment