Skip to content

Instantly share code, notes, and snippets.

@paulinep
Created September 23, 2018 11:42
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save paulinep/d883a34735a0f6e026a284746721c53c to your computer and use it in GitHub Desktop.
Save paulinep/d883a34735a0f6e026a284746721c53c to your computer and use it in GitHub Desktop.
k combinations of N elements. k, n are natural numbers 0<=k<=n. The output is the nessesary number of rows.
process.stdin.on('readable', () => {
const v = process.stdin.read();
if (v !== null) {
let input = v.toString('utf8').split(" ").map(n => parseInt(n));
let k = input[0] || 0;
let n = input[1] || 0;
//Count of combinations
let c = 0;
// took here http://e-maxx.ru/algo/generating_combinations
function nextCombination(position, lasta) {
for (let p = position; p >= 0; --p) {
if (lasta[p] < n - k + p) {
lasta[p]++;
for (let j = p + 1; j < k; ++j) {
lasta[j] = lasta[j - 1] + 1;
}
process.stdout.write(lasta.join(' ').toString() + '\n');
c++;
//next recurtion
if (lasta[k - 1] < n - 1) {
nextCombination(k - 1, lasta);
}
}
}
}
let lasta = [];
//the initial combination is first numbers from 0 to k
for (let i = 0; i < k; i++) {
lasta.push(i);
}
process.stdout.write(lasta.join(' ').toString() + '\n');
//Start recurtion
nextCombination(k - 1, lasta);
}
});
@paulinep
Copy link
Author

Sample Input 1:

2 3
Sample Output 1:

0 1
0 2
1 2

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment