Melhor combinação entre listas

Tendo os elementos A, C, D e E e listas, encontrar a melhor lista ou a melhor combinação entre elas que contenha todos ou a maioria dos elementos.

Fiz esse código para melhorar o processo de carregamento de arquivos externos de onde trabalho. Cada página precisa de X, Y arquivos, as listas são pacotes de arquivos e a melhor combinação é aquela que carrega o mínimo possível e sem fazer muitos requests no servidor. Talvez alguns arquivos sejam carregados individualmente.

Tratar o conjunto de arquivos como pacotes, mesmo que carregando excendente é um benefício pois aproveita melhor o cache cliente-servidor. Para um projeto grande isso pode resultar em tráfego de rede e processamento de servidor reduzidos.

O código está em Javascript, mas originalmente foi implementando em outra linguagem e com alguns recursos a mais.

// objetivo
var reqr = ['a', 'c', 'd', 'e'];

// listas
var list = {
	x: ['a', 'b', 'c'],
	y: ['a', 'b', 'e'],
	w: ['b', 'c'],
	i: ['d', 'e', 'f'],
	j: ['a', 'b', 'd', 'f', 'g'],
	k: ['b', 'm', 'n', 'o']
};

// resoluções do problema
var resv = [];

// primeira resolução é carregar tudo individualmente
// consequentemente a pior. com base nesse resolução novas serão geradas
resv.push({
	conn: [],
	find: [],
	need: reqr,
	rank: 0
});

// percorre as resoluções gerando novas combinações
for (var i = 0; i < resv.length; i++) {
	// a resolução pode ter suprido todos os requisitos
	// não significa que seja a melhor
	// todas as combinações serão testadas
	if (resv[i].need.length > 0) {
		// para cada resolução todas as listas são percorridas
		// buscando novas resoluções (combinações).
		// uma solução nunca é modificada, novas são geradas
		for (var name in list) {
			var find = [];
			var need = [];
			// agrupa os itens encontrados em find
			// e os não encontrados em need
			for (var j = 0; j < resv[i].need.length; j++) {
				var item = resv[i].need[j];
				if (list[name].indexOf(item) != -1) {
					find.push(item);
				}
				else {
					need.push(item);
				}
			}
			// para ser uma nova resolução precisa
			// ter ao menos uma nova saída
			if (find.length > 0) {
				// herda as conexões da resolução
				var conn = resv[i].conn.slice(0);
				// adiciona a lista nas conexões
				conn.push(name);
				// ranqueamento da resolução
				// modifique para dar mais peso de acordo com seus critérios
				// no caso, ter mais conexões reduz o rank
				var rank = find.length / (list[name].length + need.length + (resv[i].conn.length * 2) - resv[i].rank);
				// adiciona nas resoluções
				resv.push({
					conn: conn,
					find: find,
					need: need,
					rank: rank
				});
			}
		}
	}
}

// ordena todas as resoluções por rank
resv.sort(function(a, b) {
	return b.rank - a.rank;
});

// e assume a resolução com maior rank
var solv = resv[0];

Depuração

function debug() {
	var html = '';
	
	html += '<table border=1>';
	html += '<caption>' + reqr + '</caption>';
	
	for (var i = 0; i < resv.length; i++) {
		html += '' +
			'<tr>' +
				'<td>' + resv[i].conn + '</td>' +
				'<td>' + resv[i].rank + '</td>' +
				'<td>' + resv[i].need + '</td>' +
			'</tr>';
	}
	
	html += '</table>';
	
	var div = document.createElement('div');
	div.innerHTML = html;
	document.body.appendChild(div);
}

Github: https://github.com/Moraga/itemsinlists.js

NPM Package: https://www.npmjs.com/package/itemsinlists

You may also like...

  • Camilo Teixeira de Melo

    Parabéns pela solução, Alê. Só tenho duas criticas. Achei o post um pouco confuso, a princípio. Talvez fosse melhor colocar a solução completa, ou seja carregando os arquivos externos. Outra é que eu acho que o algoritmo está muito complexo. No pior caso ele está com N³ e no caso médio com N². Acho que dá para melhorar a peformace do código. Mas de qualquer forma, gênial como sempre. 😉

  • moraga86

    Obrigado!! É, realmente precisa de uma melhorada na explicação e também por exemplos mais concretos. Referente a quantidade de combinações, não cheguei a por em números, vou dar uma olhada. Muito obrigado pelas considerações!