JavaScript - сортировка двумерного массива по численности

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));

, который возвращает двумерный массив, заполненный каждой комбинацией ...

[ [ 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 ]
]

Но я хочу следующий порядок

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

Я пытался использовать .sort, но это сортирует комбинации по алфавиту

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

Но это не тот порядок, который мне нужен.

Как я могу отсортировать массив, чтобы содержимоемассива обрабатываются численно, и результат в том же порядке, как я упоминал выше?

Answer 1

Это связано с функциональным программированием, поэтому я решил показать функциональный способ генерирования комбинаций в правильном порядке.

Под функциональным я имею в виду использование функций, которыеоперируйте исключительно с их входными аргументами (вместо того, чтобы полагаться на внешнее состояние) и возвращать значение (вместо того, чтобы полагаться на мутацию).Это прямая противоположность стиля императив .

Использование Array.prototype.sort не является ни необходимым, ни функциональным (оно изменяет свои входные данные), и поэтому оно не будет использоваться в этом ответе.

Вы также упомянули, что прошло некоторое время с тех пор, как вы написали рекурсивные программы.Это должно заставить колеса снова вращаться!

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)

Достигнуто правильное упорядочение

[ 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 ]

Связано: Power Set - пока эта программа не генерирует правильное упорядочениеУпрощенная форма показывает вам, как вы можете начать думать о том, как решить проблему самостоятельно.concat теперь является базовой двоичной операцией, а powerSet имеет упрощенные логические ветви.

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' ]
// , []
// ]

Несмотря на меньшую сложность, powerSet даже работает с пустым вводом, что делает его общей функцией

getCombinations ([])
// => undefined

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

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

Answer 2

Вы можете использовать вместо последующей сортировки функцию, которая создает нужные комбинации как отсортированный результат напрямую.

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; }

Answer 3

Вы можете использовать функцию сравнения следующим образом:

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));

Answer 4

Вы можете имитировать это, используя естественную сортировку, соединяя числовые значения точками или любым другим символом, который вам нравится.

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; }

---

Вот сокращенный метод, использующий сортировку с плавающей точкой.

Примечание: Это хитрость, и вы можете получить ошибки точности с плавающей запятой с большими списками.

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 ]
]
-->

Answer 5

Вы можете передать функцию сравнения в sort(), которая реализует желаемую логику сортировки.

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;
});