0

Estou tentando criar um array a partir da combinação de vários outros arrays, pegando um elemento de cada e sem repetições. Eu achei aqui uma boa função que testa todas as combinações possíveis:

function cartesian(...args) {
    var r = [], max = args.length-1;
    function helper(arr, i) {
        for (var j=0, l=args[i].length; j<l; j++) {
            var a = arr.slice(0); // clone arr
            a.push(args[i][j]);
            if (i==max)
                r.push(a);
            else
                helper(a, i+1);
        }
    }
    helper([], 0);
    return r;
}

Isso funciona caso os arrays sejam pequenos, pois eu pego todas as possibilidades e vou testando até achar a que eu quero, posso até fazer isso dentro da função mesmo, ex:

arr1 = [1,2,3,4,5, 6];
arr2 = ['a',2,5,6,4,7];
arr3 = ['a',1,3,'b','c',9, 2, 4, 5, 7, 1];

Rapidamente eu chegaria em uma combinação sem repetição de elementos, tipo:

arrResultante = [1,'a',3]

ou:

arrResultante = [1,'a','b']

Excluindo arrays com elementos repetidos, como [1, 'a', 'a']. Porém, com arrays muito grandes, e com muitas arrays também, gerar todas as possibilidades geradas demoraria muito tempo (no meu caso, 25 arrays, cada uma com uma quantidade de elementos que varia de 2 a 23).

Tentei, também, usar o método de destructuring:

arrayResultante = [...new Set([...arr1,...arr2,..., ...arrN])]

Mas isso, pelo que percebi, não mantém na ordem e não seleciona um elemento de cada array, apenas pega todos os elementos e vai removendo os que são duplicados até restar apenas um daquele elemento.

Então, como posso gerar um resultado sem elemento duplicado, pegando um elemento de cada array de uma grande quantidade de arrays com quantidade de elementos variados?

6
  • Por favor, edite a pergunta para limitá-la a um problema específico com detalhes suficientes para identificar uma resposta adequada.
    – Comunidade Bot
    18/03/2022 às 2:57
  • Não consigo entender como de [1,2,3,4,5, 6], ['a',2,5,6,4,7]e ['a',1,3,'b','c',9, 2, 4, 5, 7, 1] você chega a [1,'a',3] o resultado pelo que descreveu deveria ser algo como [1, 'a', 2, 3, 5, 4, 6, 'b', 'c', 7, 9] 18/03/2022 às 9:09
  • 1
    @AugustoVasques É o produto cartesiano. No caso, [1, 'a', 3] é o primeiro elemento do primeiro e segundo arrays, mais o terceiro elemento do terceiro array (as combinações usando o primeiro e segundo elementos do terceiro array - respectivamente [1, 'a', 'a'] e [1, 'a', 1] - não servem porque tem elementos repetidos)
    – hkotsubo
    18/03/2022 às 12:56
  • Agora eu entendi, obrigado! 18/03/2022 às 13:02
  • A ideia desse código parece uma versão similar ao bubble sort... ou algo parecido. ordenar um conjunto de itens variados mas em arrays.. será algo assim ordenar por correspondente??... 18/03/2022 às 13:47

1 Resposta 1

1

Em vez de gerar todas as combinações, basta verificar se a combinação tem elementos repetidos, e só adicione no resultado caso não tenha. Ou seja, use o Set apenas quando uma combinação for gerada. Acho que se mudar os nomes das variáveis ajuda a deixar mais claro:

function cartesian(...arrays) {
    var resultado = [], max = arrays.length - 1;
    function helper(arr, i) {
        for (var j = 0, len = arrays[i].length; j < len; j++) {
            var combinacao = arr.slice(0); // clone arr
            combinacao.push(arrays[i][j]);
            if (i == max) {
                // *** AQUI:*** se a combinação não tem elementos repetidos, adiciona no resultado
                if (new Set(combinacao).size == arrays.length)
                    resultado.push(combinacao);
            }
            else helper(combinacao, i + 1);
        }
    }
    helper([], 0);
    return resultado;
}

var arr1 = [1, 2, 3, 4, 5, 6];
var arr2 = ['a', 2, 5, 6, 4, 7];
var arr3 = ['a', 1, 3, 'b', 'c', 9, 2, 4, 5, 7, 1];
console.log(cartesian(arr1, arr2, arr3));

Outra alternativa é verificar se o elemento já existe na combinação, antes de inseri-lo na mesma. Caso já exista, pula e vai para o próximo.

function cartesian(...arrays) {
    var resultado = [], max = arrays.length - 1;
    function helper(arr, i) {
        for (var j = 0, len = arrays[i].length; j < len; j++) {
            var combinacao = arr.slice(0); // clone arr
            // ***AQUI:*** se o elemento já existe na combinação, ignora e vai para o próximo elemento
            if (combinacao.includes(arrays[i][j]))
                continue;
            combinacao.push(arrays[i][j]);
            if (i == max) {
                resultado.push(combinacao);
            }
            else helper(combinacao, i + 1);
        }
    }
    helper([], 0);
    return resultado;
}

var arr1 = [1, 2, 3, 4, 5, 6];
var arr2 = ['a', 2, 5, 6, 4, 7];
var arr3 = ['a', 1, 3, 'b', 'c', 9, 2, 4, 5, 7, 1];
console.log(cartesian(arr1, arr2, arr3));

Fiz alguns testes com o Benchmark.js e a segunda opção foi mais rápida, já que ela não precisa montar toda a combinação para só depois verificar se tem repetição. Verificando antes, ela pode detectar elementos repetidos antes de montar toda a combinação, e já ir para a próxima.

Claro que se não tiver muitos valores repetidos, essa diferença diminui e os tempos passam a ficar mais próximos.


Quanto a demorar, não tem muito jeito. Para gerar todas as combinações, você tem que iterar por todos os elementos de todos os arrays, e quanto mais elementos e arrays envolvidos, maior é a quantidade de combinações possíveis. E você só vai saber se há um elemento repetido quando estiver gerando a combinação (a primeira solução acima verifica depois que a combinação está pronta, a segunda verifica antes de adicionar o elemento nela, mas ainda sim, só será possível verificar isso durante o processo).

Então se você tem 25 arrays com 23 elementos cada, o total de combinações possíveis é 2523, ou seja, 142.108.547.152.020.040.000.000.000.000.000. Isso é um número da ordem de 1032 (só para ter uma ideia, isso é cerca de 20 mil vezes a quantidade estimada de átomos no corpo humano).

É um número absurdamente grande. Se o programa demorar 1 nanossegundo (ou seja, 0.000000001 segundo) para gerar cada combinação, ainda sim levaria mais de 4 quatrilhões de anos para terminar (cerca de 320 mil vezes a idade estimada do universo). Mas certamente a memória acabaria bem antes, já que você está guardando todas as combinações em um array de arrays.

Se somente um ou outro array tiver muitos elementos, aí melhora "um pouco". Mas teria que ser pouco mesmo. Se todos os 25 arrays tiverem 5 elementos, por exemplo, ainda sim serão mais de 9 milhões de combinações. Somente se a maioria tiver 4 elementos ou menos, e somente um ou outro tiver um pouco mais, aí estaremos trabalhando com menos de 1 milhão de combinações (ainda sim, memória continuará sendo um problema).

Para resolver a questão da memória (e somente ela, pois com relação ao tempo não tem muito o que fazer, como já explicado acima), uma alternativa seria usar uma função geradora, que só gera um resultado por vez, e depois descarta. Neste caso, você não vai ter um array com todas as combinações, e terá que trabalhar com elas uma a uma:

// generator function, gera um elemento por vez
// *** ATENÇÃO: não gera na mesma ordem das funções anteriores ***
function *cartesian(head, ...tail) {
    const remainder = tail.length > 0 ? cartesian(...tail) : [[]];
    for (let r of remainder)
        for (let h of head) {
            const result = [h, ...r];
            // só gera o resultado se não tiver elementos repetidos
            if (new Set(result).size == tail.length + 1) {
                yield result;
            }
        }
}

var arr1 = [1, 2, 3, 4, 5, 6];
var arr2 = ['a', 2, 5, 6, 4, 7];
var arr3 = ['a', 1, 3, 'b', 'c', 9, 2, 4, 5, 7, 1];
// em vez de gerar um array com todas as combinações, itera por uma de cada vez
for (var combinacao of cartesian(arr1, arr2, arr3)) {
    console.log(combinacao);
}

Claro que ainda seria possível pegar todos os resultados e guardar em um array, mas aí você não elimina o problema da memória. E de qualquer forma, para muitos arrays com vários elementos vai demorar de qualquer jeito, pois o problema é a quantidade de combinações possíveis e mais a verificação feita em cada combinação, para saber se não há elementos repetidos nela.

Você até pode tentar bibliotecas como esta (que promete ser "mais rápida"), ou esta (para trabalhar com grandes quantidades de arrays/elementos), mas fazendo uns testes, o ganho não foi tão significativo, por causa da verificação de elementos repetidos que tem que ser feita em cima do resultado (ambas as bibliotecas geram todas e não há opção de filtrar durante o processo, somente depois que o resultado é retornado).

1
  • 1
    Olá, @hkotsubo, obrigado pela resposta! Sério, ajudou demais. De fato, o problema é que para chegar na combinação sem repetições, o programa terá que passar pelas repetidas. A alternativa 2 responde bem ao meu interesse: ela consegue "pular" para a próxima combinação sem ficar combinando sequências que tem elementos repetidos anteriores a repetição atual. Diferente da primeira alternativa que passará por todas, mesmo tendo repetidas antes de chegar no final da sequência. Então, obrigado mais uma vez pela ajuda, continuarei, após terminar minhas tarefas, lendo sua resposta :)
    – Yoel Gama
    18/03/2022 às 20:42

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 .