Zufällige Teilmenge auswählen

[phil2000]

Hallo!

Folgendes Problem: Ich habe eine Dokumentenmenge, aus der 30% der Dokumente zufällig ausgewählt werden sollen. Wenn ich hergehe und mit einer (auf die Grösse der Dokmenge angepassten) rand-Funktion sequentiell zufällig auswähle, stosse ich im Verlauf mit hoher Wahrscheinlichkeit auf Dokumente, die ich schon ausgewählt habe. Das ist schlecht.
Daher meine Frage: Kennt jemand eine Möglichkeit, solche Konflikte zu vermeiden, indem man etwa die komplette Teilmenge in einem Schritt auswählt?

Vielen Dank

[tneukom [GAST]]

|Dokumente| = n
x ist eine Zufallszahl mit n bit länge
Dokument[n] ist in Teilmenge enthalten wenn x[n] = 1 ist

[tneukom [GAST]]

ARG 30% überlesen. Warum machst du nicht einfach eine funktion die mit 30% Wahrscheindlichkeit true zurückgibt. Und rufst die für jedes Dokument auf, falls die Funktion true zurückgibt ist das Dokument in der Teilmenge enthalten sonst nicht.

bool rand30()
{
float x = (float) rand() / (float) MAXRAND;
return x < 0.3 ? true : false;
}

[phil2000]

tneukom [GAST] schrieb:

ARG 30% überlesen. Warum machst du nicht einfach eine funktion die mit 30% Wahrscheindlichkeit true zurückgibt. Und rufst die für jedes Dokument auf, falls die Funktion true zurückgibt ist das Dokument in der Teilmenge enthalten sonst nicht.

Das geht leider nicht, da ich genau 30% der Dokumente brauche. Nach dieser Funktion könnten es aber theoretisch alle sein (falls x in allen Fällen <0.3) oder auch keine (falls x immer >0.3)

[Maschi]

Da bleibt dir wohl nur folgendes übrig...

while(/*prozentzahl nicht erreicht*/)
{
   // wähle zufällig ein dokument
   if(/*dokument schon gelesen*/)
     continue;
   // lese dokument
   // markiere dokument als gelesen und erhöhe anzahl der gelesenen dokumente
}

[b7f7]

Für Jedes Doc
testen ob rand[0..1]<1/3
ja -> Auf nen Haufen

[volkard]

Maschi schrieb:

Da bleibt dir wohl nur folgendes übrig...

while(/*prozentzahl nicht erreicht*/)
{
   // wähle zufällig ein dokument
   if(/*dokument schon gelesen*/)
     continue;
   // lese dokument
   // markiere dokument als gelesen und erhöhe anzahl der gelesenen dokumente
}

ok, das ist zwar der einzige weg, aber er ist nicht mehr alleine.
er hat den nachteil, daß die antwortzeit nicht garantiert ist.
und in lagen, wo man mal 99% haben mag, wird er sogar langsam langsam.
deswegen haben findige forscher einen zweiten einzigen weg erforscht (gefunden), der das leidige problem los wird.
man random_shuffled das feld und nimmt davon die ersten 30%.
manche leutchen mögen natürlich nicht, daß dabei das ganze feld geshuffled wird und demonstrieren dagegen.
denen zuliebe haben nette forscher sogar den shuffler anpassen können, daß er nur die ersten 30% holt.
in anlehnung an den ersten einzigen weg:

while(/*prozentzahl nicht erreicht*/)
{
   // wähle zufällig ein dokument von den hinteren
   // hole es nach vorne
}

[volkard]

b7f7 schrieb:

Für Jedes Doc
testen ob rand[0..1]<1/3
ja -> Auf nen Haufen

das ist die variante, wenn man nicht genau 30% braucht, sondern durchschnittlich 30%.
da kenne ich auch noch ne feine variante.

man berechnet vorher mit dem ∫-zeichen, wie oft man ein zufälliges dokument marieren muss, um am ende (trotz zufälliger doppelmarkierungen) durchschnittlich 30% markiert zu haben. und markiert man einfach so oft ein zufälliges dokument (ggf in einem externen bitfeld) und nimmt dann alle markierten.

[b7f7]

volkard schrieb:

b7f7 schrieb:

Für Jedes Doc
testen ob rand[0..1]<1/3
ja -> Auf nen Haufen

das ist die variante, wenn man nicht genau 30% braucht, sondern durchschnittlich 30%.
da kenne ich auch noch ne feine variante.

man berechnet vorher mit dem ∫-zeichen, wie oft man ein zufälliges dokument marieren muss, um am ende (trotz zufälliger doppelmarkierungen) durchschnittlich 30% markiert zu haben. und markiert man einfach so oft ein zufälliges dokument (ggf in einem externen bitfeld) und nimmt dann alle markierten.

die methode ist fein und exakt, wenn n->infinity
man fülle einen eimer mit 30% schwarzen (bitte nicht politisch auffassen) und 70% weissen kugeln.
nun nimmt man kugel nach kugel un pakt sie in ein rohr mit dem durchmesser <2*Kugeldurchmesser
man lasse danach kugel nach kugel aus dem rohr
je nachdem ob die kugel weiss oder schwarz ist legt man die dokumente auf 2 haufen.