Javascript - generator of all lottery combinations via recursion
I am trying to write an algorithm that generates all lottery combinations recursively.
There is no recursive variation here that can be used to get C (max, 6). for example with (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 to write a recursive algorithm so that I can get C (max, length) since the above is hardcoded to C (max, 6) and came up with below, but I'm not sure how to get the parameters needed to construct 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 direct way to mathematically convert a lottery combination to an integer and vice versa, rather than using the brute force method above?
eg. from the exit 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.
source to share
I am trying to write an algorithm that generates all lottery combinations recursively.
An efficient memory generator function is well suited for 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);
}
source to share
Bonus question, is there a direct 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
source to share