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,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]
[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)