Лучший способ получить комбинацию массива элементов в Рамде? - PullRequest
Новая
       26

Лучший способ получить комбинацию массива элементов в Рамде?

0 голосов
/ 28 сентября 2019

Каков наилучший способ реализовать функцию, которая принимает три аргумента

  • наименьшая длина комбинаций
  • максимальная длина комбинаций
  • массив значений

и возвращает все комбинации длины l (arg1 <= l <= arg2).Например, 

getComb (2, 2, [1, 2, 3]) === [[1,2], [2,3], [3,1]]
getComb (0, 3, [1, 2, 3]) === [[],[1],[2],[3],[1,2],[2,3],[3,1],[1,2,3]]

(=== определяется здесь как глубокие равные безотносительно к порядку (почти установленное равенство для обеих глубин массива). Также следует игнорировать дублирующиеся значения (например, getComb(a, b, [x,x,y]) === getComb(a, b, [x,y]) для всех a,b, x, y)

Затем можно ввести fn для получения всех комбинаций: 

getAllComb = arr => getComb (0, arr.length, arr)

Спасибо!

Ответы [ 5 ]

2 голосов
/ 29 сентября 2019

Вот еще одно рекурсивное решение, немного отличающееся от ответа Нины Шольц.У него есть функция, позволяющая точно выбирать n элементов из списка, а затем она используется в основной функции, которая вызывает его для каждого значения от min до max: 

const choose = (n, xs) =>
  n < 1 || n > xs .length
    ? []
    : n == 1
      ? [...xs .map (x => [x])]
      : [
          ...choose (n - 1, xs .slice (1)) .map (ys => [xs [0], ...ys]),
          ...choose (n , xs .slice (1))
        ]

const getCombs = (min, max, xs) => 
  xs .length == 0 || min > max
    ? [] 
    : [...choose (min, xs), ...getCombs (min + 1, max, xs)]


console .log (
  getCombs (0, 3, [1, 2, 3]),
  getCombs (2, 2, [1, 2, 3])
)

Здесь getCombs - основная функция, и она должна быть достаточно ясной, просто конкатенируя результат choose (min, xs) с результатом рекурсивного вызова getCombs (min + 1, max, xs).choose - это многократно используемая функция, которая работает с двойной рекурсией: первая выбирает все те комбинации, которые используют исходный элемент, а вторая - те, которые не используют.

Это не совсем соответствует Нинерешение, так как игнорирует пустой список, когда min равен нулю.Если вам нужен список с пустым списком, вы можете изменить choose на (немного уродливее, ИМХО) версию: 

const choose = (n, xs) =>
  n < 1 || n > xs .length
    ? [[]]
    : [
        ...choose (n - 1, xs .slice (1)) .map (ys => [xs [0], ...ys]),
        ...(n + 1 > xs .length ? [] : choose (n , xs .slice (1)))
      ]
1 голос
/ 28 сентября 2019

Вы можете использовать рекурсивный подход. 

function getComb(min, max, array) {
    function iter(left, right = [], push = true) {
        if (push && min <= right.length && right.length <= max) result.push(right);
        if (!left.length) return;
        iter(left.slice(1), [...right, left[0]]);
        iter(left.slice(1), right, false);
    }

    var result = [];
    iter(array);
    return result;
}

console.log(getComb(2, 2, [1, 2, 3]));
console.log(getComb(0, 3, [1, 2, 3]));
.as-console-wrapper { max-height: 100% !important; top: 0; }
1 голос
/ 28 сентября 2019

Один из способов реализации getComb: 

[1,2,3].reduce( (acc, v, i, original) =>
    acc.concat(original.slice(i+1).map( w => [w, v] )),
[]);
0 голосов
/ 29 сентября 2019

Вот решение (по крайней мере, getAllComb), которым я горжусь чем-то :) Есть много вещей, но большинство из них шаблонные

Вдохновленные цепочками битов 

// Generic helper functions
const appendIfNotFalse = fn => (acc, val) => R.ifElse (R.equals (false)) (R.always (acc)) (R.flip (R.append) (acc)) (fn (acc, val))

const mapAndFilter = fn => arr => R.reduce (appendIfNotFalse (fn)) ([]) (arr)

// My helper fn
const has1InBitstring = n => idx => (n & 2 ** idx) > 0

// Soltuion
const indices = arr => key => mapAndFilter ((_, j) => has1InBitstring (key) (j) ? j : false) (R.range (0) (arr.length))

const getAllComb = arr => R.times (i => R.props (indices (arr) (i)) (arr)) (2 ** arr.length)

// Example
getAllComb ([1,2,3]) === [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
0 голосов
/ 28 сентября 2019

Хорошо, у меня есть частичное решение (для a = 1, b = arr.length): 

const list = R.unapply (R.identity)
const xproduct = arr => R.apply (R.liftN (arr.length) (list)) (arr)
const getPerm = arr => xproduct (R.repeat (arr) (arr.length))
const getComb = arr => R.uniq (R.map (R.uniq) (getPerm (arr)))

getComb([1,2,3]) === [[1],[2],[3],[1,2],[2,3],[3,1],[1,2,3]]

Должно быть что-то лучше;)

...