Javascript - 通过递归生成所有彩票组合

Question

我正在尝试编写一种递归生成所有彩票组合的算法.

这是一个无递归变量,可用于获得C(max,6).例如c(7,6)

let min = 1;
let max = 7;
let lotteryNum = 0;
let outputString = [];
for (let a = min; a <= max - 5; a++) {
    for (let b = a + 1; b <= max - 4; b++) {
        for (let c = b + 1; c <= max - 3; c++) {
            for (let d = c + 1; d <= max - 2; d++) {
                for (let e = d + 1; e <= max - 1; e++) {
                    for (let f = e + 1; f <= max; f++) {
                        lotteryNum++
                        outputString.push(format([a, b, c, d, e, f]) +
                            " <= " + lotteryNum + "\n");
                    }
                }
            }
        }
    }
}

function format(n) {
    n.forEach((v, i) => {
        n[i] = v < 10 ? '0' + v : '' + v;
    });
    return n.join(' ');
}
console.log(outputString.join(''));

输出

01 02 03 04 05 06 <= 1
01 02 03 04 05 07 <= 2
01 02 03 04 06 07 <= 3
01 02 03 05 06 07 <= 4
01 02 04 05 06 07 <= 5
01 03 04 05 06 07 <= 6
02 03 04 05 06 07 <= 7

我尝试编写一个递归算法,因此我可以得到C(最大值,长度),因为上面的硬编码为C(最大值,6),并提出了下面的内容,但我不知道如何获得构建所需的参数如上所述的组合字符串.

function doRec(min, max, offset) {
    if (offset >= 0) {
        for (let a = min; a <= max - offset; a++) {
            doRec(a + 1, max, offset - 1);
        }
    } else {
        // how  to create outputString params?
    }
}
doRec(1, 7, 5);

奖金问题,是否有一种直接的方式将数字组合转换为整数,反之亦然,而不是使用上面的暴力方法？

例如,从上面的输出

  01 02 03 04 05 06 <=> this is lottery number 1
  02 03 04 05 06 07 <=> this is lottery number 7

  so something like getLotteryNumber('02 03 04 05 06 07') returns 7 in this case.

Answer 1

我正在尝试编写一种递归生成所有彩票组合的算法.

内存高效的生成器函数非常适合这项任务:

// Generate all k-combinations of numbers [1..n] without repetition:
function* combinations(n, k) { 
  if (k < 1) {
    yield [];
  } else {
    for (let i = k; i <= n; i++) {
      for (let tail of combinations(i - 1, k - 1)) {
        tail.push(i);
        yield tail;
      }
    } 
  }
}

// Example:
for (let combination of combinations(7, 6)) { 
  console.log(combination);
}