identifizierung einer ziehung < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:14 Di 08.05.2007 | | Autor: | brEULER |
hallo,
ich bin auf der suche nach einem effizientem verfahren um einer ziehung von k elementen aus einer menge mit n elementen eine eindeutige zahl zwischen 1 und [mm] \vektor{n \\ k} [/mm] zu zuweisen.
beispiel: eine lottoziehung (6 aus 49) :
1.mögliche ziehung : 1,2,3,4,5,6
2.mögliche ziehung : 1,2,3,4,5,7
[mm] \vdots
[/mm]
45.mögliche ziehung : 1,2,3,4,6,7
[mm] \vdots
[/mm]
???. mögliche ziehung : 12,17,23,35,47,49
[mm] \vdots
[/mm]
13983816. mögliche ziehung: 44,45,46,47,48,49
ich will jetzt zum beispiel wissen welche ziehung 12,17,23,35,47,49 ist.
gibt es da ein verfahren das zu bestimmten? ich habe leider kombinatorik nicht belegt :(
hat da einer ne idee?
PS: Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt. :)
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:30 Di 08.05.2007 | | Autor: | Ankh |
Alle Ziehungen ausrechnen und durchnummerieren, in einem Suchbaum speichern und bei Bedarf nachschauen.
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 23:42 Di 08.05.2007 | | Autor: | brEULER |
hehe, ich war auf der suche nach einer effektiven möglichkeit. (alle aufzählen und speichern hab ich schon gemacht .. allerdings in einer hashtabelle (schneller als suchbaum ;) .. irgendwann wird das ja auch ein platzproblem)
wenn das die effektivste bekannte ist methode ist, dann wär das sehr schade .. da muss es doch irgendwas geben !? *grübel*
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:17 Do 10.05.2007 | | Autor: | brEULER |
ok, wen's interessiert ... es ist natürlich möglich jeder ziehung eine zahl (ID) zuzuweise ohne vorher alle möglichkeiten zu iterieren und sich die IDs zu merken .. hab sowas wie ne perfekte hashfunktion für ziehungen gebastelt.
das prinzip ist folgendens:
wenn man die erste(kleinste) zahl der ziehung betrachtet kommen schon sehr viele andere ziehungen nicht mehr in frage und das selbe gilt für die zweite zahl. wenn man sich duch alle zahlen durchhangelt ist es am ende eindeutig ... ist eine zahl x an stelle i bekannt gilt: es gibt nurnoch [mm] \vektor{n-x \\ k-i} [/mm] möglichkeiten für den rest.
hier mal ein stück java code dazu für [mm] \vektor{n \\ k} [/mm] ziehungen. die elemente sind von 0 bis n-1 durchnummieriert:
public static int binom(int n, int k) {
int result = n;
if (k == 0) return 1;
if (2*k > n) return binom(n,n-k);
for (int i = 2; i <= k; i++)
result = (result * (n + 1 - i)) / i;
return result;
}
public static int id(int[] arr, int n, int k) {
Arrays.sort(arr);
int id = 0;
for (int i = 0; i < arr.length; i++) {
for (int x = arr[i]-1; x >= (i==0 ? 0 : arr[i-1]+1); x--)
id += binom(n-(x+1), k-(i+1));
}
return id;
}
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:20 Do 24.05.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
