Dotaz: Náhodné kombinace (prvky s různou pravděpodobností)

[ʚĭɞ 🍉]

Mám v programu množinu prvků, z nichž každý má přiřazeno nějaké ohodnocení. Potřebuji vygenerovat náhodnou kombinaci (s volitelně připuštěným opakováním) N prvků z té množiny (N přirozené a nemusí se rovnat počtu prvků množiny), přičemž pravděpodobnost, že se prvek množiny v kombinaci vyskytne, je ovlivněna tím ohodnocením prvku. To je právě věc, kterou mě nenapadá, jak jednoduše implementovat (program píšu v Pythonu).

Nakopne mě, prosím, někdo správným směrem?

---

---

Odpovědi

[Goheeca]

nakopnuti:

bud nahodny vyber z pole/monziny, kde pocet vyskytu nejakeho prvku je umerny vaze prvku
nebo udelat nejakou prevodni funkci

int prvky[N],vahy[N];
int rnd2index(int rnd) {
  int i,tmp = 0;
  for(i=0;i<N;i++) if((tmp+=vahy[i])>=rnd) break;
  return i;
}

rnd je generovano od 0 do suma(vahy)

[Goheeca]

vlastne od 1 do suma(vahy)
nebo nahradit >= za > a pak od 0 do suma(vahy)-1

[Goheeca]

hm je tam chyba ...
oprava:

int prvky[N],vahy[N];
int rnd2index(int rnd) {
  int i,tmp = 0;
  for(i=0;i<N;i++) {
    tmp+=vahy[i];
    if(tmp>rnd) break;
  }
  return i;
}

[ʚĭɞ 🍉]

Díky. Tu převodní funkci jsem moc nepobral, takže jsem nakonec (aspoň dočasně) použil tu variantu s množinou s počtem výskytů odpovídajícím váze, nicméně to může mít nezanedbatelnou paměťovou náročnost...

[chrono]

Skús sa pozrieť na Generating Random Integers With Arbitrary Probabilities. Je to na prvý pohľad dosť zložité, ale celý algoritmus je tam vysvetlený a je tam aj kód v pythone.

[ʚĭɞ 🍉]

Ha, díky moc, tohle už bude ono.

[Goheeca]

no myslel jsem to nejak takhle:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int suma(int j, int* p) {
	int i=0,tmp=0;
	for(;i<j;i++) tmp += *(p+i);
	return tmp;
}

int weightedrnd(int j, int* values, int* weights) {
	int i=0,tmp=0,sum=suma(j, weights),rnd=rand();
	for(;i<j;i++) {
		tmp += weights[i];
		if(tmp>rnd%sum) break;
	}
	return *(values+i);
}

int main(int argc, char** argv) {
	int i,*v,*w;
	if (argc<=2 || !argc%2) return -1;
	int n = argc/2-1;
	v = (int*) malloc(sizeof(int)*n);
	w = (int*) malloc(sizeof(int)*n);
	for(i=0;i<n;i++) {
		v[i] = atoi(argv[i*2+2]);
		w[i] = atoi(argv[i*2+3]);
		if (w[i]<=0) {        
			free(v);
			free(w);
			return -2;
		}
	}
	/*for(i=0;i<n;i++) printf ("v:%d w:%d\n", v[i], w[i]);*/
	srand(time(NULL));
	for(i=0;i<atoi(argv[1]);i++) printf ("%d ", weightedrnd(n,v,w));
	free(v);
	free(w);
	return 0;
}