14

Minha dúvida é a seguinte, eu tenho uma array com todas as cidades do país,+- 5000 cidades, eu tenho uma função que sorteia uma dessas cidades e imprime o resultado na tela.

Eu gostaria de que as cidades grandes representassem uma ocorrência maior no resultado por serem mais populosas, ou seja, eu gostaria de dar pesos matemáticos baseados em porcentagem para que ocorressem mais vezes as capitais, por exemplo, com seus devidos pesos numéricos.

Eu posso enumerar os pesos para essas cidades manualmente, o que eu preciso saber é como eu construo a lógica desse sorteio com média ponderada

Eu poderia aumentar manualmente a ocorrência de São Paulo, por exemplo, calculando quantas vezes a cidade deveria aparecer para que a cidade de Serra da Saudade que tem apenas 822 habitantes ocorra a uma frequência tipo 0,0000...1% , mas isso seria uma loucura, apenas faria sentido em arrays muito pequenas, mesmo assim minha unidade mínima em % seria de 1.

4
  • Isso é fácil, é só somar os habitantes de todas as cidades existentes e dividir o número de habitantes pelo total, salvaguardando que 1% seria o mínimo.
    – Jorge B.
    Commented 7/11/2014 às 8:55
  • a resposta do @JorgeB. está muito boa, mas outra opção é a regra 3simples matematica.no.sapo.pt/regra3sind.htm, Se o rio tiver a populadação de 6453682 e corresponde a um um numero de repetições de 50000 -- Salvador tem 2902927 que corresponde a X Commented 7/11/2014 às 9:36
  • 1
    @Caputo Isso iria ocorrer apenas se eu mantivesse as strings ao invés de tratar como número, eu me expressei bem mal na parte final, o que eu quis dizer é que se eu fizesse a loucura de aumentar a quantidade de valores na array, eu poderia compensar o cálculo repetindo os valores com maior porcentagem, mas como disse, é loucura
    – Fernando
    Commented 7/11/2014 às 17:11
  • @Fernando Entendido!, vou remover o comentário acima e depois este
    – Caputo
    Commented 7/11/2014 às 17:13

5 Respostas 5

13

Cria uma tabela com os habitantes EX São paulo tem 64000 habitantes, São paulo representa os números de 1-64000, com essa mesma analogia rio representaria por exemplo a faixa 64000-128000, e sua cidade de numero 5000 representaria por exemplo 8.900.000 - 9.000.000.

Logo, ao invés de sortear a cidade você sortearia um numero de 1 à 9.000.000.

Se não precisar de tanta exatidão divide todas as faixas pela menor faixa e usa somente a parte inteira.

Exemplo cidade de menor habitantes tem 100 moradores.

então ela representaria uma faixa de tamanho 1.

já são paulo que tinha 64000 vai representar uma faixa de 640, e etc,

Assim seu programa vai ficar mais leve e quase com o mesmo resultado.

6
  • 1
    Excelente! Faz muito mais sentido enumerar as possibilidades e atribuir um resultado posterior do que parsear as strings e só depois atribuir-lhes valor, mudou o jeito que eu estava pensando em atacar o problema, obrigado! - Ps. sou artista plástico, perdoem-me se eu não estiver usando os termos técnicos adequados.
    – Fernando
    Commented 7/11/2014 às 17:34
  • artista plastico? sahuashuas programar por gosto não por obrigação é a melhor coisa. eu também não sigo na area, mas to pensando em mudar de curso
    – Joannis
    Commented 7/11/2014 às 17:36
  • hahahaha, na verdade é meio que pro meu trabalho mesmo, eu tenho uma obra que é um gerador de heterônimos artísticos como é um criador de perfis artísticos, o programa deve sortear uma cidade, além de outros valores, como acho que ficaria irreal aparecer São Paulo, Salvador, Rio com a mesma chance que as outras cidades eu considerei a mudança, graças à gentileza do povo daqui, isso vai ser possível
    – Fernando
    Commented 7/11/2014 às 17:48
  • @Fernando Se esta resposta lhe ajudou, nada melhor que marcá-la como aceita. Ajuda o autor com pontos, aos outros a não verem como uma pergunta sem resposta, ao site a manter a organização e a você que ganha uns pontinhos por aceitar a resposta.
    – Caputo
    Commented 7/11/2014 às 18:18
  • 1
    Eu achei que poderia marcar duas soluções como corretas, a sua resposta mata meu problema à pauladas, por ser em JS e eu estou trabalhando com AS2 que é o primo feio, no entanto vou votar na do @Joannis como sendo a correta por ser uma resposta genérica como foi minha pergunta, por ele ter recebido mais votos na resposta e por ele ter postado primeiro, como você mencionou.
    – Fernando
    Commented 7/11/2014 às 18:29
7

Edit

Não tinha visto a resposta do @Joannis quando escrevi, que ela tinha dado a mesma ideia :(

Vou manter somente pelo exemplo, mas inclusive já votei na resposta dela!


Uma idéia seria criar um conceito de tickets para sorteio.

  1. Obter o menor valor de população.

  2. Para dar diretos iguais, cada cidade terá um número de entrada igual a parte inteira da divisão da sua população pela menor população

Por exemplo

Cidade     População  Entradas  Numeros para sorteio
Cidade A      5.000     1           1
Cidade B     18.000     3           2, 3, 4
Cidade C    153.245    30           5, .., 34
Cidade D  2.162.301   432           35, ..., 466
  1. Sortar um número entre 1 e o maior(466), e assim cada cidade terá a chance ponderada em relação a sua população. Neste caso a primeira cidade teria uma chance de 1 / 466 e a maior 432 / 466 respeitando a proporcionalidade. Exemplo:

Porderiam se colocados em um array com uma repetição

var cidades = [
  { nome: 'cidadeA',
    populacao: 1000 },
  { nome: 'cidadeB',
    populacao: 3000 },
  { nome: 'cidadeC',
    populacao: 6000 }
];

var arraySorteio = [];

var menorPopulacao = 1000;

cidades.forEach(function (cidade) {
  var repeticoes = Math.floor(cidade.populacao/menorPopulacao);
  for (i = 0; i < repeticoes; i++) { 
    arraySorteio.push(cidade.nome);
  }  
});
    
alert(JSON.stringify(arraySorteio));

//e agora o sorteio
var posicaoSorteada = Math.floor((Math.random() * arraySorteio.length));
alert(posicaoSorteada + ' - ' + arraySorteio[posicaoSorteada]);

8
  • Como seria então feito o sorteio?
    – ramaral
    Commented 7/11/2014 às 12:25
  • Adicionei mais uma etapa para explicar @ramaral
    – Caputo
    Commented 7/11/2014 às 12:28
  • 1
    No fundo é o mesmo que eu proponho. Aquilo que você chama de entradas é levado em conta na 1ª fase. Cada cidade entra no sorteio com um peso correspondente à sua população: Uma cidade com 1000 habitantes tem 1000 entradas, uma cidade com 5000 habitantes tem 5000 entradas, etc.
    – ramaral
    Commented 7/11/2014 às 12:55
  • E acho que "mais no fundo ainda" :) é bem parecido com a resposta do Joannis. No caso dele a entradas seriam os intervalos de cada cidade correspondendo ao número de habitantes. Só muda a forma da implementação dos sorteios.
    – Franchesco
    Commented 7/11/2014 às 12:58
  • 1
    Exato. Foi o que percebi. +1, ;)
    – Franchesco
    Commented 7/11/2014 às 13:01
6

Eu faria a escolha em duas fases:

1 - Sorteava um valor entre 1 e o número de habitantes da cidade mais populosa.

2 - Sorteava a cidade de entre aquelas que têm um número de habitantes igual ou superior ao valor sorteado anteriormente.

O primeiro sorteio favorece as cidades que tem mais habitantes. Quem tiver mais habitantes tem mais probabilidade de passar ao segundo sorteio.

Apesar de no segundo sorteio todas as cidades estarem em pé de igualdade foi o número de habitantes que ditou a sua presença neste sorteio.

0
5

Compilando as respostas até agora eu proponho o seguinte:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

std::vector<std::pair<int,std::string>> cities;

void add_city(const std::string &name, int pop) {
    if (cities.empty()) {
        cities.emplace_back(pop, name);
    }
    else {
        cities.emplace_back(pop + cities.back().first , name);
    }
}

int total_population() {
    return cities.empty() ? 0 : cities.back().first;
}

const std::string select_city() {
    const int total = total_population();       
    const int pos = std::rand() % total;        
    const auto iter = std::lower_bound(begin(cities), end(cities), std::make_pair(pos, std::string()));     
    return iter->second;
}

int main() {        
    add_city("A",   50);
    add_city("B",  500);
    add_city("C",  1000);

    for (unsigned i=0; i<15; ++i) {
        const std::string city = select_city();
        std::cout << city << ' ';
    }

    return 0;
}

A idéia é ter uma lista onde cada cidade é adicionada e seu valor de população é a soma das populações das cidades adicionadas anteriormente. Assim, para sortear uma cidade basta escolher um número aleatório considerando a população de todas as cidades, e em seguida procurar na lista utilizando busca binária onde aquele número se encaixa.

Resultado do teste, mostrando a proporção das cidades selecionadas:

C A B C B B B C C C C C B B C 
2

Eu faria de uma forma a buscar uma condição exata, que dependendo da qualidade do gerador de números aleatórios seria o ideal para este caso.

Eu simularia uma "roleta", tipo daquelas que se vira com as mãos (como em eventos ou em programas de TV), onde cada faixa do círculo indica um único indivíduo da população, considerando o total da população de todas as cidades somadas (este total é exatamente o total de faixas em que a roleta irá passar por uma ou mais vezes até parar em uma delas, indicando qual indivíduo de qual cidade parou (sorteou).

inserir a descrição da imagem aqui Eu

As faixas coloridas indicam a população total de cada cidade, enquanto que as faixas internas que dividem cada cidade, indicam cada um de seus indivíduos.

Se fosse possível construir fisicamente tal roleta com milhões ou bilhões de indivíduos, e ela tivesse exatamente o mesmo espaço entre as faixas e fosse "calibrada" ao girar, não favorecendo nem prejudicando apontar para qualquer um destes indivíduos, o sorteio seria perfeito, uma vez que "todos os indivíduos têm a idêntica possibilidade de ser sorteado" a cada vez que a roleta fosse girada.

Como construir e girar esta roleta matematicamente?

Eu fiz e testei o caso em uma planilha do Excel.

inserir a descrição da imagem aqui

Há a coluna "Cidades" (texto) e População (valor, com o total da população de cada cidade).

A célula C5 tem a soma total das populações, a coluna "% do Total", calcula a participação de cada população de cada cidade deste total da população (População da cidade / População Total).

A coluna "Acumulado" soma o valor da célula anterior da coluna "População" com a população da própria cidade. Ao final, chega-se ao mesmo Total da População que é apresentado na célula C5.

O campo "Girar roleta até" ... "vezes", deve receber um número inteiro de "voltas máximas" que a roleta pode dar sobre si mesma. Por exemplo, se iniciar do indivíduo 1 da cidade A, será considerada uma volta quando houver a passagem deste mesmo indivíduo desta cidade pelo marcador.

O campo "Resultado" informa exatamente quanto a roleta girou, ou seja, quantas casas (indivíduos) passaram pelo marcador até parar. O cálculo é feito assim:

=INT(ALEATÓRIO()*$C$5*($F$3-1))+$C$5

Pode-se discutir a eficiência da função "Aleatório" do Excel (veja na sequência da resposta que trato deste assunto), mas é essa que temos em mãos de forma prática por hora, e ela atende bem ao propósito da forma que foi aplicada aqui, como poderá ser confirmado adiante.

Repare na fórmula que o valor da população é somado ao final, isso garante que "pelo menos uma volta completa seja dada na roleta".

Por isso, do número de vezes de giro é subtraído 1, pois este valor é somado uma vez no final.

O campo "Parou em" indica onde o marcador parou, e sua fórmula é:

=(F6/$C$5-INT(F6/$C$5))*$C$5

Resultado sobre o total da população menos a parte inteira desta divisão, isto resultará somente na parte fracionária desta operação (somente casas decimais), que indica o "quanto a roleta andou após a última volta completa". Por exemplo, se desse 15,25 tirando a parte inteira ficaria 0,25 isso indica que após quinze voltas a roleta girou mais 25% de indivíduos. Ao multiplicar este percentual pela "População Total", chega-se exatamente em qual indivíduo de qual cidade a roleta parou.

A coluna "Parada da roleta" aponta para a cidade deste indivíduo, que neste caso, é a cidade sorteada. A formula é:

=SE(OU(E($F$8>E17;$F$8<=E18);E(F14=0;E17=""));"<=== " & " Cdade sorteada: "& B18;"")

Caso o valor pertença à faixa da população "acumulada" relativa a uma cidade, surge a mensagem apontando esta cidade e indicando seu nome.

O fundo vermelho é feito por meio da "formatação condicional das células", onde se a célula não for vazia, ele passa o fundo da célula para vermelho e a cor da letra para branco.

Se não for o intervalo de uma cidade, a fórmula retorna "" (aspas duplas), o que deixa a célula "vazia", e seu fundo fica como estava, em branco.

Ao apertar a tecla "F9", os cálculos são feitos com outros números, e o exemplo abaixo mostra o que acontece imediatamente após teclar "F9" (isto foi feito após o exemplo anterior), eventualmente pode ocorrer de resultar na mesma cidade na sequência, dificilmente ou raramente cairá no mesmo indivíduo (teria de sair exatamente o mesmo valor do sorteio anterior).

inserir a descrição da imagem aqui

Como saber se tudo isso funciona como o esperado?

Você pode fazer "passo a passo", ou "segurar" a tecla "F9", para que ocorra um sorteio atrás do outro, e verá que o sorteio sempre se concentrará nas cidades de maior população. Quantos mais vezes calcular, mais isso será observado.

Qual o problema de usar números aleatórios para selecionar valores em uma faixa de dados?

Os números "aleatórios" que são usados nas linguagens de programação ou em outras plataformas (como é o caso que descrevi), é que de fato estes números são "pseudoaleatórios", ou seja, buscam se aproximar do que realmente seria um "sorteio sem vícios"; porém, não é isso que acontece. Veja esta página da Universidade Federal Fluminense sobre o tema que esclarece muito bem o problema e acesse os links indicados.

COMO OS COMPUTADORES GERAM NÚMEROS ALEATÓRIOS?

Por se tratar de números gerados por meio de equações matemáticas (funções de cálculo) a partir de um número inicial (comumente tratado por "semente"), é gerada uma sequência de números exatamente na mesma sequência e sempre de mesmo valor, ou seja, a sequência e os resultados não se alteram (sempre que a "semente" que iniciou a gerar os resultados tiver o mesmo valor).

Para "contornar" este problema, existem comandos que "geram" um novo valor para esta "semente" (o valor inicial somente), passando-se assim, a usar outra sequência de resultados, porém, tratam-se de outros valores de mesmo comportamento.

O problema que isto ocasiona é que há uma "tendência" de concentração de resultados em certos pontos e pouca ou nenhuma incidência de resultados em outros (principalmente se estes números forem gerados poucas vezes).

Então é de se esperar que não sejam justos os resultados, podendo ocorrer, inclusive, de uma cidade não ser sorteada após inúmeras tentativas, mesmo não sendo a cidade de menor população (evidentemente dependerá do valor da "semente" e do número de vezes que se fizer o sorteio, se for um número significativamente alto, poderá ocorrer, mas com certeza haverá incidência desproporcional entre as demais cidades).

Por que a "roleta" proposta reduz significativamente este problema?

Como cada "sorteio" não é feito rigidamente dentro de uma faixa de dados (de uma única vez por sorteio), mas por meio das "voltas" da roleta, estas faixas são completamente ultrapassadas diversas vezes, o que faz com que o efeito de haver uma "tendência" seja reduzido significativamente. Para que o efeito desta "tendência" apareça neste caso, seria necessário ocorrer uma gigantesca coincidência, que independente das "voltas" que a roleta desse, os números "sorteados" apontassem exatamente para o mesmo indivíduo. Pelo elevado número de itens (população do país) tratados individualmente, este fato seria extremamente raro se ocorresse.

1
  • Caros, fiz questão de detalhar aqui esta solução pelo fato de como ela "melhora significativamente a distribuição dos resultados". É importante refletir sobre isso, principalmente quando se busca resultados próximos da realidade para um volume de dados como esse. Espero ter contribuído com todos.
    – Leo
    Commented 8/07/2016 às 18:15

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 .