Abbildungsvorschrift gesucht < Funktionalanalysis < Analysis < Hochschule < Mathe < Vorhilfe
|
Ich suche eine eineindeutige Abbildungsvorschrift, die jedem geordneten Septupel [mm] (a_{1},...,a_{7}), [/mm] welches OHNE Zurücklegen aus der Menge A={0,...,51} gezogen wurde, eine Zahl X aus [mm] \IN [/mm] zuordnet. Dabei versuche ich die Funktion so zu gestalten, dass es möglichst wenig "Lücken" in der Zuordnung zu X gibt. Im Optimalfall suche ich genau die Abbildungsvorschrift, die jeder der 133.784.560 Kombinationsmöglichkeiten von [mm] {a_{1},...,a_{7}} [/mm] aus A genau eine Zahl aus {1,...,133.784.560} zuordnet.
Mein Versuch besteht darin, die Kombinationsmöglichkeiten so zu systematisieren, dass schrittweise eine Zahl in Abhängigkeit des Maximums, des zweiten Maximums, etc. aus [mm] {a_{1},...,a_{7}} [/mm] entsteht.
Z.B. wird zunächst der Maximalwert [mm] a_{1} [/mm] aus {a1,...a7} betrachtet und hierfür eine "Grundzahl" ermittelt: G = [mm] \summe_{i=6}^{a_{1}-1},
[/mm]
da dies die Summe aller Kombinationsmöglichkeiten mit einem Maximalwert von [mm] a_{1}-1 [/mm] wiederspiegelt. Nun hänge ich aber an einem System, um die anderen sechs Werte ebenfalls so miteinzubeziehen, dass die Zuordnung am Ende eineindeutig wird.
Kann mir jemand helfen, die richtige Zuordnung zu finden, oder
kennt jemand vielleicht einen eleganten Weg, um eine solche Funktionsvorschrift zu erzeugen?
Vielen Dank im Vorfeld, auch für Hinweise!
|
|
| |
|
> Ich suche eine eineindeutige Abbildungsvorschrift, die
> jedem geordneten Septupel [mm](a_{1},...,a_{7}),[/mm] welches OHNE
> Zurücklegen aus der Menge A={0,...,51} gezogen wurde, eine
> Zahl X aus [mm]\IN[/mm] zuordnet. Dabei versuche ich die Funktion so
> zu gestalten, dass es möglichst wenig "Lücken" in der
> Zuordnung zu X gibt. Im Optimalfall suche ich genau die
> Abbildungsvorschrift, die jeder der 133.784.560
> Kombinationsmöglichkeiten von [mm]{a_{1},...,a_{7}}[/mm] aus A
> genau eine Zahl aus {1,...,133.784.560} zuordnet.
Hallo titeritero
ich sehe da einen Widerspruch in deiner Darstellung. Falls du
wirklich die geordneten Septupel (in der Kombinatorik
manchmal als 'Variationen' bezeichnet) meinst, so wäre deren
Anzahl viel größer, nämlich 674274182400.
Wenn es nur 133784560 Objekte sein sollen, so meinst du wohl
stattdessen die ungeordneten Septupel ('Kombinationen').
LG , Al-Chw.
> Mein Versuch besteht darin, die Kombinationsmöglichkeiten
> so zu systematisieren, dass schrittweise eine Zahl in
> Abhängigkeit des Maximums, des zweiten Maximums, etc. aus
> [mm]{a_{1},...,a_{7}}[/mm] entsteht.
>
> Z.B. wird zunächst der Maximalwert [mm]a_{1}[/mm] aus {a1,...a7}
> betrachtet und hierfür eine "Grundzahl" ermittelt: G =
> [mm]\summe_{i=6}^{a_{1}-1},[/mm]
> da dies die Summe aller Kombinationsmöglichkeiten mit
> einem Maximalwert von [mm]a_{1}-1[/mm] wiederspiegelt. Nun hänge
> ich aber an einem System, um die anderen sechs Werte
> ebenfalls so miteinzubeziehen, dass die Zuordnung am Ende
> eineindeutig wird.
>
> Kann mir jemand helfen, die richtige Zuordnung zu finden,
> oder
> kennt jemand vielleicht einen eleganten Weg, um eine
> solche Funktionsvorschrift zu erzeugen?
>
> Vielen Dank im Vorfeld, auch für Hinweise!
|
|
|
| |
|
Hallo, hier bin ich noch einmal.
Wie schon gemeldet, meinst du wohl nicht die geordneten,
sondern die ungeordneten Stichproben, mit anderen Worten
alle Teilmengen von genau k Elementen (in deinem Fall k=7)
aus einer Grundmenge von n Elementen (im Beispiel n=52).
Der Zuordnung dieser Teilmengen zu natürlichen Zahlen
kann man auch als eine Nummerierung der Teilmengen
auffassen. In der elementaren Kombinatorik ist es gebräuchlich,
die Begriffe zuerst an einfachen Beispielen auszuprobieren.
Da könnte eine Aufgabe beispielsweise so lauten:
Gib alle Teilmengen aus je drei Elementen der Grundmenge
G = {a,b,c,d,e,f} an.
Um alle derartigen Teilmengen aufzuschreiben und dabei
keine zu übersehen, aber auch keine mehrfach zu nennen,
geht man am besten mit etwas System vor. So ordnet man
am besten die Elemente jeder einzelnen Dreier-Teilmenge
untereinander alphabetisch (da ja die Reihenfolge der
Aufzählung der endlichen Menge im Prinzip beliebig ist,
darf man zum Zweck der Notation die alphabetische
Ordnung nehmen), und auch die so entstandenen "Wörter"
(nach Weglassung der Mengenklammern und Kommas)
ordnet man alphabetisch. Im Beispiel mit n=6 und k=3
erhalten wir so die Liste:
abc
abd
abe
abf
acd
ace
acf
ade
adf
aef
bcd
bce
bcf
bde
bdf
bef
cde
cde
cef
def
Nun kann man diese Anordnung im Detail untersuchen und
aus der Analyse (in der man geeignete Gruppierungen
vornimmt) rechnerisch analysieren. Damit kommt man
zu einer rekursiven Methode, um die "Nummer" jedes
einzelnen Wortes festzulegen. In obiger Liste kann man
zunächst etwa einmal sehen, dass die Gruppen zu den
möglichen Anfangsbuchstaben (a,b,c,d) jeweils aus
[mm] $\pmat{5 \cr 2}\ [/mm] = 10$
[mm] $\pmat{4 \cr 2}\ [/mm] = 6$
[mm] $\pmat{3 \cr 2}\ [/mm] = 3$
[mm] $\pmat{2 \cr 2}\ [/mm] = 1$
Elementen (Wörtern) bestehen.
Die Details habe ich mir jetzt noch nicht genau überlegt,
ich denke aber, dass du in deinem Text, wo du von einem
ersten bzw. zweiten Maximum etc. gesprochen hast, mögli-
cherweise etwas ähnliches gemeint, aber eben auch noch
nicht deutlich ausformuliert hast.
LG , Al-Chwarizmi
|
|
|
| |
|
Hallo
da mich das Thema auch ein Stück weit interessiert, habe ich
nun doch eine Formel entwickelt, nach der man jeder
Teilmenge T von k Elementen aus einer Grundmenge G mit n
Elementen eine eindeutige Nummer aus [mm] $\{ 1,2,3,\ .....\ \pmat{n \cr k}\ \}$
[/mm]
zuordnen kann.
Als Modell nehmen wir für die Grundmenge die Menge
G = [mm] $\{ 1,2,3,\ .....\ n \}$
[/mm]
Die Teilmenge, der eine Nummer zugeordnet werden soll,
sei die Menge [mm] $\{ p_1 , p_2 , p_3,\ .....\ p_k\ \}$ [/mm] , wobei $\ [mm] p_1 [/mm] < [mm] p_2 [/mm] < [mm] p_3 [/mm] < .....\ [mm] p_k [/mm] $
gelten soll. Die Nummer für diese Teilmenge berechnet
sich dann folgendermaßen:
$\ 1\ +\ [mm] \sum_{j\ =\ 1}^{k}\quad \sum_{i\ =\ p_{j-1}+1}^{p_j-1} \pmat{n-i \cr k-j}$
[/mm]
Dabei ist für [mm] p_0 [/mm] , wo es auftritt, der Wert 0 zu setzen.
Enthält die Teilmenge T unmittelbar aufeinander folgende
Werte wie etwa 5 und 6, so erhält man in der Formel eine
Summe der Form [mm] \sum_{6}^{5} [/mm] ..... , welche offenbar
keinen Summanden enthalten kann und daher zu ignorieren ist.
Ein Beispiel:
In der (alphabetisch geordneten) Liste aller Kombinationen
der 26 Buchstaben des Alphabets zu je 4 Elementen hat
die Kombination
DIOT
(mit [mm] p_1=4 [/mm] , [mm] p_2=9 [/mm] , [mm] p_3=15 [/mm] , [mm] p_4=20) [/mm] die Nummer
$\ 1\ +\ [mm] \sum_{i\ =\ 1}^{3}\ \pmat{26-i \cr 3}\ [/mm] +\ [mm] \sum_{i\ =\ 5}^{8}\ \pmat{26-i \cr 2}\ [/mm] +\ [mm] \sum_{i\ =\ 10}^{14}\ \pmat{26-i \cr 1}\ [/mm] +\ [mm] \sum_{i\ =\ 16}^{19}\ \pmat{26-i \cr 0}\ [/mm] \ =\ 6894$
|
|
|
|
