Newsgroup: it.comp.programmare
Titolo: distribuzione di entita' omogenea su un array

ciao a tutti, scusate il subject, so che non e' chuiarissimo!
il problema che devo risolvere e' il seguente:
ho un po' di entita' (A,B,C,D...N) alle quali e' associato un peso
(PA,PB,PC,PD...PN)
la somma dei pesi e' , diciamo, T
devo distribuire *uniformemente* queste entita'  su un array di T posizioni.
esempio:
A-->6
B-->1
C-->3
ed ho un array di 100 posizioni, NON devo scrivere:
AAAAAABCCC
bensi' in modo UNIFORME:
ovviamente non e' sempre possibile, ma basta che CIRCA vada come voglio:
AACABACACA o infiniti modi ancora....
chi mi sa aiutare?
grazie!!!
--
Ciao by Allanon
Q: Why do programmers always mix up Christmas and Halloween?
A: Because 25 Dec = 31 Oct

 chi mi sa aiutare?
Puoi definire una "figura di merito"?  Cioe`, data una certa
permutazione di sei A, una B, e tre C, puoi darci un algoritmo
che produca un numero che ha una qualche correlazione alla
bonta` o alla cattiveria della posizione raggiunta?
Se non e` possibile definire quali posizioni siano migliori di
altre, non credo che sia possibile ottenere una posizione che
sia migliore di un'altra.
Se puoi definire una figura di merito, allora un buon approccio
puo` essere quello di generare posizioni "a caso" e tenere la
migliore.  A seconda di come si calcola la figura potrebbe
meritare di provare piccole perturbazioni alla "posizione a
caso" e tenerle se e solo se migliorano le cose, o altri approcci
ancora piu` avanzati sino al pieno "simulated annealing".
Supponiamo che la tua figura di merito (precisamente di demerito)
sia il conteggio delle coppie adiacenti: costa un punto ogni
volta che un piazzamento e` eguale a quello successivo, e vuoi
minimizzare i punti.  Ecco allora una semplice soluzione:
def figuraDiMerito(posizione):
    adiacenze = 0
    for i in range(len(posizione)-1):
        if posizione[i]==posizione[i+1]:
            adiacenze += 1
    return adiacenze
import random
def provaunpo(dizNumeriLettere, maxprove=100):
    base = []
    for lettera in dizNumeriLettere:
        base.extend([lettera]*dizNumeriLettere[lettera])
    merito = figuraDiMerito(base)
    prova = base[:]
    for i in range(maxprove):
        random.shuffle(prova)
        nuovoMerito = figuraDiMerito(prova)
        if nuovoMerito < merito:
            base[:] = prova
            merito = nuovoMerito
    return base
esempio = {'A':6, 'B':1, 'C':3}
for i in range(10):
    print ''.join(provaunpo(esempio))
Questa produce ad esempio il seguente output (in un certo run):
AACABACACA
AABACACACA
ACACAABACA
ACABACACAA
ABACAACACA
ABAACACACA
ABACACAACA
ABAACACACA
AACABACACA
ACAABACACA
Alex

     return base
sei stato chiarissimo e "azzeccato" come al solito.
grazie 1000! :-)


 grazie 1000! :-)
Prego!  Sono soddisfatto di vedere che nonostante la poca
conoscenza di Python non hai avuto problemi a seguire l'algoritmo
da me proposto (e si` che ho usato alcuni colpetti non pulitissimi,
come quel base[:]=prova invece del pulitissimo equivalente
base = copy.copy(prova) ...:-).
Altro che diagrammi di flusso, come recentemente proposto anche
su questo gruppo... Python e` pseudocodice eseguibile, l'ideale per
proporre _e provare_ algoritmi!-)
Alex

 base = copy.copy(prova) ...:-).
ehm, qui forse la mia ignoranza mi ha aiutato,
nel senso che x me e' molto piu' intuitivo leggere cio' che hai scritto (
[:]= )
che circa assomiglia visivamente al Pascal,
piuttosto che "copy.copy(prova)" che francamente trovo molto arcano!
certo, senza sapere che cavolo e' [:]= Magari e' del tutto diverso da quello
che mi aspetto!
cmq e' vero, Python e' molto intuitivo, anche se abbandonare i miei bei tipi
statici
mi provoca qualche apprensione. vedremo!
grazie ancora di tutto!


ovviamente non e' sempre possibile
E' una variazione dell'algoritmo di Bresenham.
Diciamo che hai:
	valori[N]
	pesi  [N]
allora aggiungi un valore
	curr  [N]
che inizializzi con pesi[], e un valore
	sum
pari alla somma di tutti i pesi.
Poi, per T=SUM(pesi) volte:
	trova i, tale che curr[i] e' massimo
	immetti valori[i]
	aumenta curr[] di pesi[], e diminuisci curr[i] di sum
Quindi:
#include <stdio.h>
#include <stdlib.h>
#define N       6
char simboli[N]="ABCDEF";
int  pesi[N]   ={ 6, 1, 3, 5, 4, 11 };
int  curr[N];
int  sum = 0;
#ifdef DEBUG
        int freq[N];
#endif
int main(int argc, char **argv)
{
            size_t i = 0;
        int T = 0;
        if (argc==2)
                T = atoi(argv[1]);
        if (T<=0)
                for (T=0, i=0; i < N; i++) T+=pesi[i];
        for (i=0; i < N; i++)
        {
                curr[i] = pesi[i];
                sum += pesi[i];
#ifdef DEBUG
                freq[i] = 0;
#endif
        }
        for (i=0; i < T; i++)
        {
                size_t j, jmax=0;
                int pmax = curr[0];
                for (j=0; j < N; j++)
                {
                        if (curr[j] >= pmax)
                                pmax = curr[jmax=j];
                        curr[j]+=pesi[j];
                }
                curr[jmax]-=sum;
#ifdef DEBUG
                freq[jmax] ++;
#endif
                printf("%c\n", simboli[jmax]);
        }
#ifdef DEBUG
        printf("T=%d, sum=%d\n", T, sum);
        for (i=0; i < N; i++)
        {
                printf("%c atteso %d, osservato %d\n",
                        simboli[i],
                        (pesi[i] * T) / sum,
                        freq[i]);
        }
#endif
        return 0;
}
Leonardo
-- 
".signature": bad command or file name

 E' una variazione dell'algoritmo di Bresenham.
Carino!  Una versione Python con un esempio d'uso potrebbe ad esempio 
essere:
from __future__ import generators
import sys, operator
def br(indict):
    curr = [ (indict[valore], valore) for valore in indict]
    sum = reduce(operator.add, indict.itervalues())
    for i in xrange(sum):
        __, nextValore = max(curr)
        yield nextValore
        temp = indict.copy()
        temp[nextValore] -= sum
        curr = [ (p+temp[valore], valore) for p, valore in curr ]
for v in br({'A':6, 'B':1, 'C':3}):
    print v,
print
Alex

 E' una variazione dell'algoritmo di Bresenham.
[cut]
grazie, lo provo subito! :-)


 E' una variazione dell'algoritmo di Bresenham.
[cut]
funziona alla perfezione, grazie!
e adesso mi metto pure a cercare di capirlo a fondo!
Ciao by Allanon