Re: punti a coordinate intere nell'intersezione fra due iper-solidi

From: Paolo Russo <paolrus_at_libero.it>
Date: 1 Mar 2002 0:17:18 +0100

[Johannes Wentu:]
>In pratica sono interessato a tutte le intersezioni possibili fra i due
>ipersolidi perch� devo sapere tutti i modi possibili di disporre N
>oggetti in M urne ma con N che va da 1 a M.

Temo che il fatto che le urne siano limitate renda
improbabile l'esistenza di una formula matematica tanto
semplice (senza if, insomma) che ne tenga conto.
Il massimo che sono riuscito a ottenere e` il programmino
quick'n'dirty che allego in fondo. Tiene conto dei limiti e
la complessita` computazionale e` cubica (per l'esattezza
credo vada circa con MN^2). Comunque, in un colpo solo
calcola il numero di disposizioni per tutti gli N fino al
massimo dato. Spero che sia corretto; ho verificato i
risultati, per numeri piccoli, confrontandoli con una
versione che faceva i calcoli in modo piu' pedissequo,
contando una ad una le combinazioni possibili.
Spero che tu conosca il C...

>PS: qualcuno mi ha parlato dei numeri di seconda specie di Stirling...
>ma non mi sembrano ancora la soluzione definitiva.

Non so cosa siano. Non so molto di matematica.

Ciao
Paolo Russo


#define MAX_BOX 100 /* actually max+1 */
#define MAX_K 100 /* actually max+1 */

unsigned long Max[MAX_BOX];
unsigned long maxk;
unsigned long number;
unsigned long a[MAX_K],b[MAX_K];

MakeComb()
{
register unsigned long s;
register int j,m,k;
int i;
for (j=0; j<=maxk; j++) a[j]=0;
a[0]=1;
for (i=0; i<number; i++) {
    for (j=0; j<=maxk; j++) {
        m=Max[i];
        if (m>j) m=j;
        for (s=0,k=0; k<=m; k++) s+=a[j-k];
        b[j]=s;
        }
    for (j=0; j<=maxk; j++) a[j]=b[j];
    }
}

main(argc,argv)
    int argc;
    char **argv;
{
register unsigned long i;
if (argc<3) {
    printf("Syntax: COMB maxK {max1 max2 ... maxN}\n");
    printf("(K objects in N boxes)\n");
    return 0;
    }
maxk=atoi(argv[1]);
number=argc-2;
for (i=0; i<number; i++) Max[i]=atoi(argv[i+2]);
MakeComb();
for (i=0; i<=maxk; i++) printf("k=%lu: comb=%lu\n",i,a[i]);
}
Received on Fri Mar 01 2002 - 00:17:18 CET