javascript 为N选择X创建循环

nnvyjq4y  于 2022-10-30  发布在  Java
关注(0)|答案(2)|浏览(130)

假设我有一个包含N个成员的列表:

const list = [0, 1, 2, ...(N-1)];

我想做(N选X),从数学上讲,所以我需要创建一个函数:

const findAllCombinations = (x, list) => {
     // return all x combinations of the list
};

如果X是2,我可以这样做:

const findAllCombinations = (x, list) => {
    for(let i = 0; i < list.length; i++){
      for(let j = i+1; j < list.length; j++){
           // N choose 2
       }
     }
};

但不确定如何以捕获N个choose X的方式进行循环,如果可能的话,最好是 * 迭代 * 而不是 * 递归 *!但递归解决方案就可以了。
这是我的尝试,但它是错误的:

const combine = (x, list) => {

    // Note: N = list.length

    if(list.length < x){
        throw new Error('not enough elements to combine.');
    }

    if (x < 1) {
        return [];
    }

    const ret = [];

    for(let v of combine(x-1, list.slice(1))){
        ret.push([list[0], ...v]);
    }

    return ret;
}

console.log(
   combine(3, ['a','b,'c','d'])
)

目标将是得到这4种组合:

[a,b,c]
[a,b,d]
[a,c,d]
[b,c,d]

...因为(4 choose 3) = 4
以下是我想要的输出:

combine(0,[1,2,3]) => [[]] // as  N choose 0 = 1
combine(1,[1,2,3]) => [[1],[2],[3]] // as  N choose 1 = N
combine(2,[1,2,3]) => [[1,2],[1,3],[2,3]]]] // as  N choose N-1 = N
combine(3,[1,2,3]) => [[1,2,3]] // as  N choose N = 1

要查看更好的所需输出列表,请参阅:https://gist.github.com/ORESoftware/941eabac77cd268c826d9e17ae4886fa

xqnpmsa8

xqnpmsa81#

下面是一种迭代方法,它使用给定集合中的索引组合。
从k个索引的初始组合开始,这些索引被原地移位/递增,以便获得长度为k的下一个组合,依此类推:

function * combinations(set, k) {
  const n = set.length;
  if (k > n)
    return;

  // Shift combi indexes to make it the next k-combination. Return true if
  // successful, false otherwise (when there is no next of that length).
  const next = (combi, i) => {
    if (++combi[i] < n)
      return true;
    let limit = n;
    while (i > 0) {
      if (++combi[--i] < --limit) {
        let idx = combi[i];
        while (++i < combi.length)
          combi[i] = ++idx;
        return true;
      }
    }
    return false;
  };

  const combi = Array.from(Array(k), (_, i) => i);
  const i = k-1;

  do yield combi.map(j => set[j]);
  while (next(combi, i));
}

这比人们想象的要高效得多,尤其是与总是从空组合开始而不考虑k的递归算法相比(函数next()可能会被优化)。
一个更复杂的版本,它允许指定一个k值列表,以及是否允许重复,可以在这里找到(以及它上面的递归实现)。

yv5phkfx

yv5phkfx2#

结果证明我们可以避免使用递归。
我想到了Python中的itertools.combinations
CPython是开源的,所以我们可以看到C. https://github.com/python/cpython/blob/main/Modules/itertoolsmodule.c中的源代码
您可以看到itertools_combinations_implcombinations_next的函数定义。
不过,还有一些refCount和垃圾收集器的东西,它们可能与另一种语言无关。
我尝试在TypeScript中编写一个“combinationsobject”版本,并在其后添加了一些测试(TS playground),然后很容易从编译输出中获得JS:

"use strict";
//this class is based on https://github.com/python/cpython/blob/main/Modules/itertoolsmodule.c
class CombinationObject {
    constructor(list, r) {
        let n = list.length;
        this.pool = list;
        this.indices = [];
        for (let i = 0; i < r; i++)
            this.indices[i] = i;
        this.result = null;
        this.r = r;
        this.stopped = r > n;
    }
    next() {
        if (this.stopped)
            return null;
        let { pool, indices, r } = this;
        if (this.result === null) {
            //first pass 
            this.result = [];
            for (let i = 0; i < r; i++) {
                let index = indices[i];
                this.result[i] = pool[index];
            }
        }
        else {
            this.result = this.result.slice();
            let n = pool.length;
            let i; //needs to be used outside the for loop 
            /* Scan indices right-to-left until finding one that is not at its maximum (i + n - r). */
            for (i = r - 1; i >= 0 && indices[i] == i + n - r; i--) { }
            if (i < 0) {
                this.stopped = true;
                return null;
            }
            /* Increment the current index which we know is not at its maximum.
              Then move back to the right setting each index to its lowest possible value (one higher than the index to its left).
            */
            indices[i]++;
            for (let j = i + 1; j < r; j++) {
                indices[j] = indices[j - 1] + 1;
            }
            /* Update the result for the new indices starting with i, the leftmost index that changed */
            for (; i < r; i++) {
                let index = indices[i];
                this.result[i] = pool[index];
            }
        }
        return this.result;
    }
}
let list = ["One", 2, "Three", 4, 5, 'Six'];
let K = 3;
const LIMIT = 1000;
let co = new CombinationObject(list, K);
let count = 0;
while (!co.stopped && count < LIMIT) {
    let result = co.next();
    if (result === null)
        break;
    console.log(result);
    count++;
}
function factorial(n) {
    let t = 1;
    for (let i = 2; i <= n; i++)
        t *= i;
    return t;
}
function nCk(n, k) {
    if (k > n)
        return 0;
    return factorial(n) / factorial(n - k) / factorial(k);
}
console.log(nCk(list.length, K));
console.log(count);

相关问题