Uma forma de resolver é usar um array que contém as posições do conjunto que você vai pegar para gerar a combinação. Inicialmente, você o preenche com os números de 0 a p - 1
. No seu caso, seria [0, 1, 2]
.
Nesta configuração inicial, você pega a primeira combinação, que são as p
primeiras posições. Depois, basta ir variando o array de posições para pegar todas as combinações possíveis ([0, 1, 3]
, [0, 1, 4]
, [0, 2, 3]
, etc). Seria algo assim:
function combinations(conjunto, p) {
// função auxiliar, cria um sub-array de "conjunto", usando as posições de "indices"
function fromIndices(conjunto, indices) {
var v = [];
for (var i of indices) {
v.push(conjunto[i]);
}
return v;
}
if (p > conjunto.length)
return [];
var result = [];
// índices (números de 0 a r-1)
var indices = [...Array(p).keys()];
result.push(fromIndices(conjunto, indices));
while (true) {
var found = false;
for (var i = p - 1; i >= 0; i--) {
if (indices[i] != i + conjunto.length - p) {
found = true;
indices[i]++;
break; // encontrou índice que vai variar, sai do for
}
}
if (!found) // não tem mais variações, sai do while
break;
for (var j = i + 1; j < p; j++)
indices[j] = indices[j - 1] + 1;
result.push(fromIndices(conjunto, indices));
}
return result;
}
const conjunto = ["A", "B", "C", "D", "E"];
for (var x of combinations(conjunto, 3)) {
console.log(x);
}
Claro que também dá para fazer recursivo (que provavelmente é a maioria das soluções que você vai encontrar por aí). Uma alternativa é este algoritmo, que usa um array auxiliar indicando as posições que serão usadas.
Depois, a cada chamada recursiva você inicia na posição seguinte, podendo aumentar o tamanho ou não dependendo do caso.
function subset(conjunto, used, startIndex, currentSize, p, result) {
if (currentSize === p) {
var comb = [];
for (var i = 0; i < conjunto.length; i++) {
if (used[i])
comb.push(conjunto[i]);
}
result.push(comb);
return;
}
if (startIndex === conjunto.length)
return;
used[startIndex] = true;
subset(conjunto, used, startIndex + 1, currentSize + 1, p, result);
used[startIndex] = false;
subset(conjunto, used, startIndex + 1, currentSize, p, result);
}
function combinations(conjunto, p) {
var result = [];
subset(conjunto, Array(conjunto.length).fill(false), 0, 0, p, result);
return result;
}
const conjunto = ["A", "B", "C", "D", "E"];
for (var x of combinations(conjunto, 3)) {
console.log(x);
}
Generator functions
Conforme o array aumenta, a quantidade de combinações possíveis cresce exponencialmente, então pode ser que não seja viável manter em memória um array contendo todas elas.
Neste caso, uma opção seria usar uma generator function. A diferença é que ela gera uma combinação de cada vez, e depois esta é descartada (a menos, é claro, que eu a guarde em algum lugar, como um array), gastando menos memória:
// o asterisco indica que é uma generator function
function* combinations(conjunto, p) {
function fromIndices(conjunto, indices) {
var v = [];
for (var i of indices) {
v.push(conjunto[i]);
}
return v;
}
if (p > conjunto.length) {
yield []; // yield para "retornar" o valor
return;
}
var result = [];
// índices (números de 0 a r-1)
var indices = [...Array(p).keys()];
yield fromIndices(conjunto, indices);
while (true) {
var found = false;
for (var i = p - 1; i >= 0; i--) {
if (indices[i] != i + conjunto.length - p) {
found = true;
indices[i]++;
break; // encontrou índice que vai variar, sai do for
}
}
if (!found) // não tem mais variações, sai do while
break;
for (var j = i + 1; j < p; j++)
indices[j] = indices[j - 1] + 1;
yield fromIndices(conjunto, indices);
}
}
const conjunto = ["A", "B", "C", "D", "E"];
for (var x of combinations(conjunto, 3)) {
console.log(x);
}
Já se for recursivo, deve-se usar o operador yield *
para delegar as chamadas recursivas:
function* subset(conjunto, used, startIndex, currentSize, p) {
if (currentSize === p) {
var comb = [];
for (var i = 0; i < conjunto.length; i++) {
if (used[i])
comb.push(conjunto[i]);
}
yield comb;
return;
}
if (startIndex === conjunto.length)
return;
used[startIndex] = true;
yield* subset(conjunto, used, startIndex + 1, currentSize + 1, p);
used[startIndex] = false;
yield* subset(conjunto, used, startIndex + 1, currentSize, p);
}
function* combinations(conjunto, p) {
yield* subset(conjunto, Array(conjunto.length).fill(false), 0, 0, p);
}
const conjunto = ["A", "B", "C", "D", "E"];
for (var x of combinations(conjunto, 3)) {
console.log(x);
}