0

Preciso gerar uma lista com todas as combinações possíveis com p elementos dado um determinado conjunto (array) de tamanho n. Tanto o tamanho do conjunto (n) quanto o tamanho da combinação (p) podem ser definidos na chamada da função.

Exemplo:

Conjunto = ["A", "B", "C", "D", "E"];

Resultado:

1: ["A", "B", "C"]
2: ["A", "B", "D"]
3: ["A", "B", "E"]
4: ["A", "C", "D"]
5: ["A", "C", "E"]
6: ["A", "D", "E"]
7: ["B", "C", "D"]
8: ["B", "C", "E"]
9: ["B", "D", "E"]
10: ["C", "D", "E"]

Até o momento, implementei o seguinte código em JavaScript:

const conjunto = ["A", "B", "C", "D", "E"];

function calculaCombinacoes(n, k){
    const c = fatorial(n) / (fatorial(k) * fatorial(n-k));
    return Math.trunc(c);
}

function fatorial(x){
    if (x >= 0) {
        let fatorial = 1;
        let contador = x;
        for (let i = 0; i < contador; i++) {
            fatorial = fatorial * x;
            x--;
        }
        return fatorial;
    }else{
        return false;
    }
}


/**
 * Gera todas as combinações possíveis de um conjunto tomados p a p
 * @param {*} conjunto 
 * @param {*} p 
 * @returns 
 */
function geraCobinacoes(conjunto, p){
    //Pega o tamanho do conjunto
    const n = conjunto.length;
    //calcula total de combinações possíveis
    const c = calculaCombinacoes(n, p);

    //Encerra caso o tamanho do conjunto seja menor que p
    if (n < p) {
        return false;        
    }

    //Ponteiro que indica a posição do primeiro elemento da combinação no conjunto
    let k = 0;
    //Ponteiro que indica a posição do último elemento da combinação no conjunto
    let u = n-p;

    //Array da combinação
    let combinacao;

    //Loop para iterar em todas as combinações possíveis
    for (let i = 0; i < c; i++) {
        //Zera o vetor combinação
        combinacao = [];
        //Lopp para iterar em todos os elementos da combinação
        for (let j = 0; j < p; j++) {
            combinacao.push(conjunto[k + j]);

        }
        console.log(combinacao);
    }
}

geraCobinacoes(conjunto, 3);

Agora falta definir o código dentro do segundo for. Alguma sugestão?

1 Resposta 1

1

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

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .