Javascript - all lottery combinations generator via recursion

Question

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

Here is a none recursive variation that can be used to get C(max,6). e.g. 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(''));

outputs

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

I tried writing a recursive algorithm so I could get C(max,length) as the above is hard-coded to C(max,6) and came up with the below, but I am not sure how to get the params needed to build the combination string as above.

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

Bonus question, is there a straight forward way to mathematically convert a lottery combination to an integer and vice versa as opposed to using the brute force method above?

e.g. from the output above

  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.

There is really no need to generate all, there is a function to get nth combination out of x. — skobaljic, May 14 '17 at 22:54

le_m · Accepted Answer · 2017-05-20T23:21:54.423

5

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

A memory efficient generator function lends itself very well to this task:

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

edited May 20 '17 at 23:21

answered May 14 '17 at 23:15

le_m

19,302
9
64
74

Great! but it increments by reversed order? – ericsicons May 15 '17 at 03:04
@ericsicons last edit reversed the order to better match your output. – le_m May 15 '17 at 03:30

ericsicons · Answer 2 · 2017-09-12T05:09:03.743

Bonus question, is there a straight forward way to mathematically convert a lottery combination to an integer?

function getLotteryNum(combination, max = 49) {
    const combinationLength = combination.length;

    const Σ = (currentNum, prevNum = 0, pos = 1) => {

        let sum = 0;
        const Δk = combinationLength - pos;

        while (currentNum > prevNum) {
            let Δn = max - currentNum;
            sum += mathjs.combinations(Δn, Δk);
            currentNum--;
        }
        return sum;
    }

    const ΣΣ = (acc, num, ii, comb) =>
        acc + (comb.length - ii === 1 ?
            comb.slice(-2).reduce((acc, num) => num - acc, 0) :
            Σ(num - 1, ii > 0 ? comb[ii - 1] : 0, ii + 1));

    return combination.reduce(ΣΣ, 0);
}
//e.g.
console.log(getLotteryNum([44, 45, 46, 47, 48, 49])); // 13983816
console.log(getLotteryNum([1, 2, 3, 4, 5, 6])); // 1
console.log(getLotteryNum([9, 26, 31, 36, 38, 44])); //10108381

Javascript - all lottery combinations generator via recursion

2 Answers2