JavaScript - Sort 2D array, numerically

Question

function getCombinations(_list) {
    var fn = function(active, rest, a) {
        if (!active.length && !rest.length)
            return;
        if (!rest.length) {
            a.push(active);
        } else {
            fn(active.concat(rest[0]), rest.slice(1), a);
            fn(active, rest.slice(1), a);
        }
        return a;
    }
    return fn([], _list, []);
}

var list = [1, 2, 3, 4]

console.log(getCombinations(list));

Which returns a 2D array, filled with every combination ...

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

But I want the following order

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

I tried using .sort, but that sorts the combinations alphabetically

getCombinations([ 1, 2, 10 ]).sort()
// [ [ 1 ]
// , [ 1, 10 ]
// , [ 1, 2 ]
// , [ 1, 2, 10 ]
// , [ 10 ]
// , [ 2 ]
// , [ 2, 10 ]
// ]

But this is not the ordering I want.

How can I sort the array, so that the contents of the array are treated numerically, and the result is the same order as I mentioned above?

Can I convince you to generate the combinations in the order you need them? — Mulan
– Mulan, Commented Apr 25, 2018 at 14:17
@user633183 I thought about that. It's been a while since I've played around with recursive programming, but I'll take a look at it. Whether in creation or afterwards in sorting, it's all the same. — Birrel
– Birrel, Commented Apr 25, 2018 at 14:23
@JaredSmith the JavaScript sort() method is functional programming — Birrel
– Birrel, Commented Apr 25, 2018 at 14:31
@Birrel 1. It's not, Array.prototype.sort mutates the original array and 2. even if it were you don't call it anywhere in the provided code. I could maybe see it qualifying because of your use of recursion. Maybe. Please read the tag description before using it on questions, I (and I assume others subscribing to the tag) don't want to get spammed with a bunch of emails not relevant to our interests. — Jared Smith
– Jared Smith, Commented Apr 25, 2018 at 15:03

Nina Scholz · Accepted Answer · 2018-04-25 14:51:05Z

3

You could use instead of sorting afterwards, a function which creates the wanted combinations as sorted result directly.

function getCombinations(list) {

    function iter(index, values) {
        var temp = values.concat(list[index]);
        result.push(temp);
        if (++index < list.length) {
            iter(index, temp);
            iter(index, values);
        }
    }

    var result = [];
    iter(0, []);
    return result;
}

var list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12];
    result = getCombinations(list);

console.log(result.length);
console.log(result.map(a => a.join(' ')));

.as-console-wrapper { max-height: 100% !important; top: 0; }

answered Apr 25, 2018 at 14:51

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Máté Safranka · Accepted Answer · 2018-04-25 14:29:37Z

2

You can pass a comparator function to sort() that implements your desired sorting logic.

arr.sort((one, other) => {
    let minL = Math.min(one.length, other.length);
    for (let i = 0; i < minL; i++) {
        if (one[i] != other[i]) return one[i] - other[i];
    }
    return one.length - other.length;
});

answered Apr 25, 2018 at 14:29

Máté Safranka

4,1061 gold badge12 silver badges22 bronze badges

3 Comments

Birrel Over a year ago

Simple, and the first to the finish line. Thanks for checking it and modifying your solution.

Kaddath Over a year ago

nice use of the != type instead of !== to discard undefineds. And corrected quick enough that i didn't have time to comment ;)

Mulan Over a year ago

@Birrel, Sorting the result is a backward way to approach the problem. I recommend you view Nina's answer that generates the combinations in the correct order. This is especially important if you're generating combinations of a large input where sorting increases time cost exponentially for each element added to the input.

Mulan · Accepted Answer · 2018-04-25 16:05:50Z

This is tagged with functional-programming so I thought I'd show a functional way to generate the combinations in the correct order.

By functional, I mean using using functions that operate solely on their input arguments (rather than relying on external state) and return a value (rather than relying on mutation). This is a direct contrast to imperative style.

Using Array.prototype.sort is neither necessary nor functional (it mutates its input), and so it will not be used in this answer.

You also mentioned it's been awhile since you've written recursive programs. This should get the wheels spinning again!

const identity = x =>
  x
  
const concat = (xs, ...ys) =>
  ys.length === 0
    ? xs
    : xs.concat (concat (...ys))
  
const subsets = ([ x, ...xs ], _return = identity) =>
  xs.length === 0
    ? _return ([ [ x ] ])
    : subsets 
        ( xs
        , ss =>
            _return ( concat ( [ [ x ] ]
                             , ss.map (s => concat ([ x ], s))
                             , ss
                             )
                    )
        )
        
for (const set of subsets ([ 1, 2, 3, 4 ]))
  console.log (set)

The correct ordering is achieved

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

Related: Power Set – while this program doesn't generate the correct ordering, it's simplified form shows you how you can begin to think about approaching the problem on your own. concat is now a basic binary operation and powerSet has simplified logic branches.

const identity = x =>
  x
  
const concat = (xs, ys) =>
  xs.concat (ys)
  
const None =
  Symbol ()
  
const powerSet = ([ x = None, ...xs ], _return = identity) =>
  x === None
    ? _return ([ [] ]) // base case: no X
    : powerSet         // inductive case: at least one X
        ( xs
        , ss =>
            _return ( concat ( ss.map (s => concat ([ x ], s))
                             , ss
                             )
                    )
        )
          
console.log (powerSet ([ 'x', 'y', 'z' ]))
// [ [ 'x', 'y', 'z' ]
// , [ 'x', 'y' ]
// , [ 'x', 'z' ]
// , [ 'x' ]
// , [ 'y', 'z' ]
// , [ 'y' ]
// , [ 'z' ]
// , []
// ]

Despite being less complex, powerSet even works with an empty input, making it a total function

getCombinations ([])
// => undefined

subsets ([])
// => [ [ undefined ] ]

powerSet ([])
// => [ [] ]

Kaddath · Accepted Answer · 2018-04-25 14:30:42Z

You can use a comparison function like this:

var arr = [
    [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],
    [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],
    [1, 3, 3, 4, 5, 6, 7, 8, 9, 12],
    [1, 2, 3, 4, 5, 6, 7, 8, 9, 12],
    [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
    [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12],
    [1, 2, 3, 4, 5, 6, 7, 8, 9, 11],
    [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12],
];

function sortNumericArrays(a, b){
    var i, l = a.length > b.length ? a.length : b.length, result = 0;
    for(i = 0; i < l; i++){
        if(undefined === a[i]){
            result = -1;
            i = l;
        }else if(undefined === b[i]){
            result = 1;
            i = l;
        }else if(a[i] !== b[i]){
            result = a[i] - b[i];
            i = l;
        }
    }
    return result;
}

console.log(arr.sort(sortNumericArrays));

Mr. Polywhirl · Accepted Answer · 2018-04-25 15:37:56Z

-1

You can mimic this, by using a natural sort by joining the number values by dots, or any other character you like.

var list = [
  [ 1, 2, 3, 4 ],
  [ 1, 2, 3 ],
  [ 1, 2, 4 ],
  [ 1, 2 ],
  [ 1, 3, 4 ],
  [ 1, 3 ],
  [ 1, 4 ],
  [ 1 ],
  [ 2, 3, 4 ],
  [ 2, 3 ],
  [ 2, 4 ],
  [ 2 ],
  [ 3, 4 ],
  [ 3 ],
  [ 4 ]
];

function versionNumberSort(a, b) {
  return a.join('.').localeCompare(b.join('.'))
}

console.log(list.sort(versionNumberSort).map(l => l.join(', ')).join('\n'));

.as-console-wrapper { top: 0; max-height: 100% !important; }

Here is a shorthand method, using floating-point sorting.

Note: This is a trick, and you could get floating-point precision errors with larger lists.

var list = [
  [ 1, 2, 3, 4 ],
  [ 1, 2, 3 ],
  [ 1, 2, 4 ],
  [ 1, 2 ],
  [ 1, 3, 4 ],
  [ 1, 3 ],
  [ 1, 4 ],
  [ 1 ],
  [ 2, 3, 4 ],
  [ 2, 3 ],
  [ 2, 4 ],
  [ 2 ],
  [ 3, 4 ],
  [ 3 ],
  [ 4 ]
];

function sortNumberArrays(a, b) {
  return parseFloat('0.' + a.join('')) - parseFloat('0.' + b.join(''));
}

console.log(list.sort(sortNumberArrays).map(l => l.join(', ')).join('\n'));

.as-console-wrapper { top: 0; max-height: 100% !important; }

<!--
Desired result:

[
  [ 1 ]
  [ 1, 2 ]
  [ 1, 2, 3]
  [ 1, 2, 3, 4 ]
  [ 1, 2, 4]
  [ 1, 3 ]
  [ 1, 3, 4 ]
  [ 1, 4 ]
  [ 2 ]
  ...
  [ 4 ]
]
-->

edited Apr 25, 2018 at 15:37

answered Apr 25, 2018 at 14:49

Mr. Polywhirl

49.1k12 gold badges96 silver badges147 bronze badges

1 Comment

Mr. Polywhirl Over a year ago

@Birrel AFter failing to get the recursion to work, because you have too look at every element in each array when comparing, I utilized a simpler method. You can use natural sorting. Think of it as sorting version numbers or sections of an article.

Collectives™ on Stack Overflow

JavaScript - Sort 2D array, numerically

5 Answers 5

Comments

3 Comments

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

3 Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related