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(max,length)，因为上面的代码被硬编码为 C(max,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

I am trying to write an algorithm that generates all lottery combinations recursively.

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

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