在 Ramda 中获得元素数组组合的最佳方法？

Question

实现带三个参数的函数的最佳方法是什么

组合的最小长度
组合的最大长度
值数组

和returns长度为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)

谢谢！

Answer 1

实现 getComb 的一种方法是：

[1,2,3].reduce( (acc, v, i, original) =>
    acc.concat(original.slice(i+1).map( w => [w, v] )),
[]);

Answer 2

您可以采用递归方法。

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

Answer 3

好的，我有一个部分解决方案（针对 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]]

必须有更好的东西 ;)

Answer 4

这是另一个递归解决方案，其结构与 Nina Scholz 的答案略有不同。它有一个函数可以从列表中精确选择 n 个元素，然后在 main 函数中使用它，它为从 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是main函数，应该还算清楚，就是把choose (min, xs)的结果和递归调用getCombs (min + 1, max, xs)的结果拼接起来。 choose 是一个很好的可重用函数，它在双重递归上运行，第一个选择所有使用初始元素的组合，第二个选择所有不使用初始元素的组合。

这与 Nina 的解决方案不太匹配，因为当 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)))
      ]

Answer 5

这是一个解决方案（至少 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]]

在 Ramda 中获得元素数组组合的最佳方法？

Best way to get combination of array of elements in Ramda?

javascript

functional-programming

ramda.js