12

Eu gerei uma lista de verbetes de uma enciclopédia e quero achar a melhor maneira de separar os verbetes de forma que eu escolha um número de dias e eu tenha uma programação de quais verbetes ler por dia.

(A lista está aqui: https://pastebin.com/4qNLqCJj)

O primeiro item é o volume, o segundo o verbete, o terceiro o número de caracteres e o quarto é um id (gerado a partir da data que foi gravada a entrada no meu pc).

Eu gostaria de fazer um script que gerasse uma programação, eu entraria o número de dias e ela dividiria o número de caracteres total da enciclopédia e separaria os verbetes a partir do número de caracteres da média.

Exemplo: Eu entro com o número de dias, 120. O script irá gerar uma programação de modo que eu possa ler todos os caracteres dos três volumes da enciclopédia em 120 dias. Por exemplo:

A programação deverá ter 120 dias, sendo que cada dia terá um número X de verbetes tendo seu número de caracteres somado igualando um número mais próximo possível da média de caracteres por dia.

Os verbetes podem ser lidos em qualquer ordem e em qualquer volume, o que importa é eles serem distribuídos de modo que seja lido uma quantia quase igual de carcteres cada dia.


Eu fiz uma pergunta anterior relacionada a isso e um usuário sugeriu o algorítmo de erro de predição, mas não estou conseguindo adaptar ele para esse script.

Veja: Qual o algoritmo para distribuir os parágrafos?

Como eu poderia fazer isso?

2
  • Se eu entendi corretamente, o que você quer fazer envolve esses passos: 1) Calcular a média de caracteres por dia necessários para que toda a enciclopédia seja lida nos 120 dias; 2) Agrupar verbetes por dia, de forma que cada dia tenha verbetes que componham aproximadamente o mesmo número de caracteres da média. Se esse entendimento está correto, você provavelmente sabe fazer (1) mas está com dificuldade em fazer (2). Commented 20/05/2017 às 14:41
  • 2
    Uma solução "simples" é ordenar os verbetes do menor para o maior (isto é, menos caracteres para mais caracteres) e ir alocando-os nos dias até que ultrapassem a média calculada em (1). É claro que podem haver verbetes que sozinhos já ultrapassem a média ou que não podem ser combinados com nenhum outro sem ultrapassá-la, então nesse caso você tem que utilizar alguma outra heurística para fazer a melhor divisão. Algoritmos de melhor divisão são mais complexos e se relacionam com o famoso Problema da Mochila. Talvez essa leitura te ajude. Commented 20/05/2017 às 14:45

3 Respostas 3

2
+150

Não li as outras respostas, e não sei maneira "inteligente" de resolver a sua questão. Dito isso, achei o problema interessante, e tentei resolver "ao meu modo" (na unha).

Imagino que você não queira/possa quebrar um verbete ao meio - se não você poderia fazer uma divisão "perfeita" e não teria aberto uma pergunta.

Digo isso porque percebi que você tem verbetes com 70 caracteres - e outros com 7000, o que dificulta (acredito) uma boa distribuição.

O que o código que eu escrevi pretende fazer, é o seguinte:

  • Preencher a quantidade de dias desejada com os maiores verbetes encontrados
  • Procurar pelos dias cuja soma de caracteres está mais distante da média
  • Adicionar novos verbetes a esses dias
  • E é isso. Nos meus testes, o resultado parece razoável, mas confesso que apanhei tanto da programação em si que não pude testar muito as possíveis soluções!

    O programa espera um arquivo de texto, com formatação idêntica ao que você postou no pastebin - informação de cada verbete separada por ponto e vírgula, e verbetes separados um do outro por uma nova linha:

    vol1;Ageu, Livro de;4629;1494553563.48
    vol1;Agricultura;6593;1494553566.18
    vol1;Água;8947;1494553571.57
    vol1;Águia;10794;1494553577.0
    vol1;Aguilhada;1688;1494553582.39
    vol1;Agulha;580;1494553585.11
    vol1;Agulha, Orifício da;1418;1494553587.82
    

    Resultado: screenshot do programa rodando

    "use strict";
    function mostraDados() {
    	if (window.carregado) {
    		document.getElementById("qtdcaracteres").value = window.qtdcaracteres;
    		document.getElementById("qtdverbetes").value = window.qtdverbetes;
    		if (document.getElementById("qtddias").value > window.qtdverbetes) {
    			document.getElementById("qtddias").value = window.qtdverbetes;
    		}	
    		var qtddias = document.getElementById("qtddias").value;
    		document.getElementById("qtdmedia").value = Math.round(window.qtdcaracteres/qtddias);
    		window.qtdmedia = Math.round(window.qtdcaracteres/qtddias);
    	}
    }
    
    function saida(div, texto) {
    	div.innerHTML = div.innerHTML + texto;	
    }
    
    function limpa(div) {
    	div.innerHTML = "";	
    }
    function criaVerbetes(meuArray) {
    		var obj = new Array();
    		for (var i = 0; i < meuArray.length; i++) {
    			obj[i] = {
    				vol: (meuArray[i].split(";"))[0],
    				titulo: (meuArray[i].split(";"))[1],
    				caracteres: (meuArray[i].split(";"))[2],
    				id: (meuArray[i].split(";"))[3],
    				pegaCaracteres: function() { return parseInt(this.caracteres); },
    			}
    		}
    	return obj;
    }
    
    function contaCaracteres(meuArray) {
    		var qtdCaracteres = 0;
    		for (var i = 0; i < meuArray.length; i++) {
    			qtdCaracteres += meuArray[i].pegaCaracteres();
    		}
    	return qtdCaracteres;
    }
    
    function ordena(meuArray) {
    		meuArray.sort(function(a, b) {
    			return a.pegaCaracteres() - b.pegaCaracteres();
    		});
    }
    
    function ordenaId(meuArray) {
    		meuArray.sort(function(a, b) {
    			return a.id - b.id;
    		});
    }
    
    function listaVerbetes(meuArray) {
    	for (var i = 0; i < meuArray.length; i++) {
    		console.log(meuArray[i].titulo + ": " + meuArray[i].pegaCaracteres());
    	}
    }
    
    function criaArrayDeDias() {
    	var dias = document.getElementById("qtddias").value;
    	var meuArray = new Array();
    	
    	for (var i = 0; i < dias; i++) {
    		meuArray[i] = {
    			verbete: [],
    			pegaSoma: function() {
    				var ct=0;
    				for (var i = 0; i < this.verbete.length; i++) {
    					ct += this.verbete[i].pegaCaracteres();
    				}
    				return ct;
    			}
    		}
    	}
    
    	return meuArray;
    }
    
    function calcula() {
    	if (window.carregado) {
    		window.objDia = criaArrayDeDias();
    		window.colecaoVerbetes = criaVerbetes(arrayVerbetes);
        
                    ordena(colecaoVerbetes);
    
    		for (var i = 0; i < window.objDia.length; i++) {
    			window.objDia[i].verbete[window.objDia[i].verbete.length] = window.colecaoVerbetes.pop();
    		}
    		
    		var longeDaMedia = 0;
    		var index;
    		while(window.colecaoVerbetes.length > 0) {
    			for (var i = 0; i < window.objDia.length; i++) {
    			var provisorio = window.qtdmedia - window.objDia[i].pegaSoma();
    				if (longeDaMedia < provisorio) {
    					longeDaMedia = provisorio;
    					index = i;
    				}			
    			}
    			window.objDia[index].
    				verbete[window.objDia[index].
    					verbete.length] = window.colecaoVerbetes.pop();
    			longeDaMedia = 0;
    		}
    
    		// saiu do while! hora de morfar
    		var div = document.getElementById('saida');
    		var div2 = document.getElementById('saida2');
    		for (var i = 0; i < window.objDia.length; i++) {
    				ordenaId(window.objDia[i].verbete);				
    		}
    
    		limpa(div);
    		for (var z = 0; z < window.objDia.length; z++) {
    			saida(div, "Dia " + z + ":<br>");
    			saida(div, "soma de caracteres: " + window.objDia[z].pegaSoma() + "<br>");
    			saida(div, "numero de verbetes: " + window.objDia[z].verbete.length + "<br><br>");
    		}
    
    
    		var div = document.getElementById('saida');
    		limpa(div2);
    				for (var z = 0; z < window.objDia.length; z++) {
    			saida(div2, "Dia " + z + ":<br>");
    			for (var g = 0; g < window.objDia[z].verbete.length; g++) {
    				saida(div2, window.objDia[z].verbete[g].vol + ", " +
    					window.objDia[z].verbete[g].titulo + "<br>");
    			}
    			saida(div2, "<br>");
    		}
    
    	} else { console.log("nao carregado"); }
    }
    
    function leArquivo(e) {
    	var arquivo = e.target.files[0];
    	var leitor = new FileReader();
    	leitor.onload = function(e) {
    		window.arquivoTexto = e.target.result;
    		window.arrayVerbetes = arquivoTexto.split("\n");
    		window.carregado = true;
    		window.objDia = criaArrayDeDias();
    		window.objVerbetes = criaVerbetes(arrayVerbetes);
    		window.colecaoVerbetes = window.objVerbetes;
    		window.qtdverbetes = window.objVerbetes.length;
    		window.qtdcaracteres = contaCaracteres(objVerbetes);
    		mostraDados();
    	};
    leitor.readAsText(arquivo);
    }
    
    document.getElementById('arquivo').addEventListener('change', leArquivo, false);
    document.getElementById('qtddias').addEventListener('change', mostraDados, false);
    label {display:block;}
    textarea {display:block;}
    
    .container{
        font-family: Tahoma, Verdana, Segoe, sans-serif;
        padding: 10px;
        background-color:#d6d6c2;
        display:flex;
    }
    .container2{
        color: #000;
        height:400px;
        overflow-y:scroll;
    }
    .divide{
        padding: 10px;
        flex-grow: 1;
    }
    <!DOCTYPE html>
    <html>
    <body> 
    <head>
    <meta charset="utf-8"/>
    </head>
    <body>
    <div class="container">
    	<div class="divide">
    			<label for="title">Quantidade de verbetes</label>
    			<textarea id="qtdverbetes" rows="2" cols="15" readonly></textarea>
    			<label for="title">Quantidade de caracteres</label>
    			<textarea id="qtdcaracteres" rows="2" cols="15" readonly></textarea>
    			<label for="title">Media caracteres/dia</label>
    			<textarea id="qtdmedia" rows="2" cols="15" readonly></textarea>
    		</div>
    		<div class="divide">
    			<input type="file" id="arquivo"/><hr>
    			<label for="title">Numero de dias</label>
    			<textarea id="qtddias" rows="2" cols="15"></textarea>
    			<hr>
    			<button onclick="calcula()">Calcular</button>
    		</div>
    		</div>
    	<div class="container">
    		<div class="divide">
    			<p>Contagem de caracteres:</p>
    			<div class="container2" id="saida"></div>
    		</div>
    		<div class="divide">
    			<p>Verbetes:</p>
    			<div class="container2" id="saida2"></div>
    		</div>
    <script src=".\verbetes.js">
    </script>
    </body>
    </html>

    0
    0

    Ola,

    Bom os verbetes podem ser lidos aleatoriamente? exemplo no mesmo dia ler verbetes do volume 1, 2 e 3 aleatoriamente?

    se não puder voce pode fazer algo como a logica abaixo:

    Variaves do script:
    
    somaDeCaracteres = soma dos caracteres de todas os verbetes
    dias = numero de dias desejados
    media = media de caracteres diarios
    numeroDeVerbetes = quantidade de verbetes totais
    caracteresRestantesNoDia = ?
    
    Logica: 
    
    1 - 
    Para cada verbete em verbetes{
        somaDeCaracteres = somaDeCaracteres + verbete.caracteres
        numeroDeVerbetes = numeroDeVerbetes + 1
    }
    
    2 - 
    
    media = somaDeCaracteres  dias
    
    3 - 
    caracteresRestantesNoDia = media
    diaAtual = 1
    Para cada verbete em verbetes{
        se caracteresRestantesNoDia - verbete.caracteres > 0 {
            adicionaVerbeteNaLista(diaAtual)
            caracteresRestantesNoDia = caracteresRestantesNoDia - verbete.caracteres
        }senao{
            diaAtual = diaAtual + 1
            caracteresRestantesNoDia = media
        }
    }
    

    Assim ele respeita a media, caso um verbete a mais em algum dia ultrapasse a media ele não adiciona... desta forma o ultimo dia tera caracteres a menos que os outros.

    3
    • Os verbetes podem ser lidos em qualquer ordem e em qualquer volume, o que importa é eles serem distribuídos de modo que seja lido uma quantia quase igual de carcteres cada dia. Commented 17/05/2017 às 19:14
    • É valido começar a ler um verbete em um dia e terminar no outro? pois se for necessário terminar o verbete inteiro no dia que começou acredito que nao seja possivel dividir em quantias iguais....
      – João
      Commented 19/05/2017 às 1:06
    • Se eu lesse metade de um verbete hoje e acabasse amanhã isso significa que eu teria que contar o número de caracteres antes da leitura, o que não torna a tarefa muito prática. Commented 19/05/2017 às 18:34
    0

    Resolver este problema não é difícil, o problema é a viabilidade devido ao custo computacional.

    Uma forma simples de resolver: criar um algoritmo que gera todas as combinações possíveis e depois verificar qual varia menos em relação a média, que pode ser feito por exemplo, verificando qual tem o menor desvio quadrático, o que é algo fácil.

    A dificuldade deste problema é devido a sua complexidade que cresce de forma exponencial, ou seja, seu custo computacional aumenta muito ao aumentar o tamanho do problema.

    Sugiro que veja este vídeo que explica muito bem isso (apesar de ser em espanhol está bem compreensível). https://www.youtube.com/watch?v=UR2oDYZ-Sao

    É obvio que na solução que eu dei, você pode simplificar algumas coisas para não ter que testar todas as combinações e encontrar uma solução melhor, porém a solução continuará sendo de complexidade exponencial.

    Com 120 dias e 4321 verbetes, o tempo para encontrar a resposta será absurdamente grande, mas é a única forma de garantir que a melhor distribuição foi encontrada.

    O que pode ser feito é desenvolver uma ideia para uma solução não ideal, onde você não irá encontrar a melhor distribuição, mas que talvez o resultado seja satisfatório para seu objetivo, porém isto depende do seu objetivo. Se era somente a melhor solução, infelizmente não há muito o que fazer, mas se uma solução não ideal também for válida podemos tentar algumas ideias. A pergunta que fica é qual seu objetivo?

    2
    • Obrigado pela resposta. Não me importo muito com tempo computacional já que levei mais de 6 horas rodando 3 scripts que extraíram os verbetes da enciclopédia. Como dito na pergunta, meu objetivo é fazer uma programação que me permita ler igualmente um número de caracteres X a cada dia. Isso quer dizer que eu vou ler alguns verbetes hoje, alguns amanhã, mas no fim do número de dias eu terei lido os três volumes. Só que o detalhe é o número de combinações será astronômico já que eu poderia ler de 1 a vários verbetes por dia. Acredito que o script deve ser mais inteligente. Commented 19/05/2017 às 18:32
    • 1
      Realmente, "criar um algoritmo que gera todas as combinações possíveis" é uma solução de complexidade fatorial que vai muito rapidamente se tornar inviável conforme cresce o número de verbetes. Mais informações aqui: pt.stackoverflow.com/questions/56836/… Commented 20/05/2017 às 14:51

    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 .