injektive Abbildung gesucht

18.11.2005, 13:24

Mazze

injektive Abbildung gesucht

Um den Aufwand meines Programms an dem ich grad arbeite etwas einzuschränken brauch ich ne Injektive Funktion wie folgt:

$\begin{eqnarray*} n \in \{1,2, ... ,20\} \end{eqnarray*}$

$\begin{eqnarray*} M_n = \{0,1, ... ,n-1\} \end{eqnarray*}$

$\begin{eqnarray*} T_n = (a_1,a_2, ..., a_n) \| a_i \in M_n \end{eqnarray*}$

Ich hätte jetzt gern eine injektive Abbildung

$\begin{eqnarray*} \{ T_n \} \to M' \subset \mathbb{N} \end{eqnarray*}$

wobei das größte Element aus M' gerade $\begin{eqnarray*} 2^{63} - 1 \end{eqnarray*}$ sein sollte. Ich will also Tupel der länge n über der Menge {0 ... n-1} injektiv auf eine Teilmenge der natürlichen Zahlen abbilden. Meine Idee dieses Tupel direkt als Zahl zu interpretieren wäre aber zu aufwändig. (int -> String operationen)

Jemand ne Idee?

edit

Das größte Element kann , muss aber nicht $\begin{eqnarray*} 2^{63} - 1 \end{eqnarray*}$ sein. Es darf kleiner sein darf aber nicht größer sein.

18.11.2005, 14:36

JochenX

Auf diesen Beitrag antworten »

ich verstehe deinen aufschrieb nicht ganz

ist Tn EIN festgewältes element?
oder ist Tn eher die menge, die alle tupel dieser art enthält?

18.11.2005, 14:50

Mazze

Auf diesen Beitrag antworten »

die Menge aller Tupel der Länge n.

18.11.2005, 15:13

JochenX

Auf diesen Beitrag antworten »

RE: injektive Abbildung gesucht

Zitat:

verändert
$\begin{eqnarray*} T_n = \{ (a_1,a_2, ..., a_n) \| a_i \in M_n \} \end{eqnarray*}$

Ich hätte jetzt gern eine injektive Abbildung

$\begin{eqnarray*} \{ T_n \} \to M' \subset \mathbb{N} \end{eqnarray*}$ .

dann ist die linke Menge EINELEMENTIG
oder soll das dann wiederum die menge sein, die für alle n=1 bis 20 Tn enthält? oder betrachtest du die n einzeln?

betrachtest du also ein festes n, DAZU die T_n und dann abbildungen von T_n (bzw der menge, die nur die menge T_n enthält) nach M'?

edit: also T20 allein hat schon mal nicht viel weiger elemente als dein geforderter maximalwert, aber es reicht

18.11.2005, 18:38

Mazze

Auf diesen Beitrag antworten »

ich geb ein n vor und dann werden alle n-tupel diesbezüglich betrachtet. D.h

für n = 2

$\begin{eqnarray*} \{T_2 \}= \{ (0,0),(0,1),(1,0),(1,1) \} \end{eqnarray*}$

n = 3

$\begin{eqnarray*} \{T_3 \}= \{ (0,0,0),(0,0,1),(0,1,0),(1,0,0),(0,1,1),(1,0,1),(1,1,0) ........... (2,2,2) \} \end{eqnarray*}$

ich hätte $\begin{eqnarray*} \{T_n\} \end{eqnarray*}$ wohl korrekter weise so definieren sollen

$\begin{eqnarray*} \{ (a_1,a_2, ... ,a_n) \| a_i \in M \} \end{eqnarray*}$

18.11.2005, 18:45

JochenX

Auf diesen Beitrag antworten »

okay, hatte mich sogar noch verlesen, dachte a_i aus M_i Hammer

dann muss ich dir etwas schlechtes mitteilen:
|T20|=20^(20) >> 2^63
da wirds nix mit injektion wie gewünscht......

für kleinere älle würde sich natürlich das auffassen der zahl in einer anderen zhlenbasis anbieten

also x aus T12, d.h. x ist kette von 12 zeichen, je aus 0 bis 11
könnte man das nicht als darstellung einer natürlichen zahl im 11ersystem auffassen?

mfg jochen

ps: und ich bleibe bei der schreibweise T_n statt {T_n}, was eine einelementige menge darstellt Augenzwinkern

edit: T_3 enthält nicht (3,3,3) ......

18.11.2005, 18:59

Mazze

Auf diesen Beitrag antworten »

Es ginge noch die Injektion auszuweiten auf die ganzen Zahlen im Bereich

$\begin{eqnarray*} (-2^{63},2^{63}) \end{eqnarray*}$

das wären $\begin{eqnarray*} 2^{64} \end{eqnarray*}$ zahlen. Ach ja, ziel der injektion ist es dazu noch das sie möglichst einfach zu berechnen sein sollte. Nicht das das ausrechnen des Funktionswerts selber schon quadratisch oder kubisch im Aufwand ist.

ich seh grad 20^20 is immernoch größer als 2^64

Hm, wird wohl Zeit mal 128 Bit Zahlen einzuführen.

Das heißt wohl das ich linear suchen muss anstatt direkt nen Index zu berechnen unglücklich

edit

t3 geändert

18.11.2005, 19:03

JochenX

Auf diesen Beitrag antworten »

hallo mazze, das umwandeln ins dzimalsystem aus dem n-er-system von deinem n-tupel ist ein aufwand, der O(n) beträgt

sei n=4, deine tupel (a1,a2,a3,a4)
dann wird dein tupel geschickt auf a4+4*a3+(4^2)*a2+(4^3)*a1
das ist eine einfache schleife, oder?

pseudocode:

k=0
for (i=0 bis i=n-1)
k=k+a_i*n^i;

(oder andersrum k=k+a_i*n^(n-1-i), dann passts zu meiner wahl oben)

edit: sorry bin erst mal weg
werde später noch mal reinschnuppern, aber auf jeden fall liegst du mit dem system nicht ganz falsch, denke ich

dicker wink Wink

18.11.2005, 19:15

Mazze

Auf diesen Beitrag antworten »

Es macht aber keinen Sinn für die verschiedenen n auch noch verschiedene Algorithmen anzuwenden. Da wird der code nur unübersichtlich groß.

Zitat:

das ist eine einfache schleife, oder?

Jop, der Aufwand das Bild zu berechnen wäre dann O(n).

18.11.2005, 19:53

Auf diesen Beitrag antworten »

Zitat:

Original von Mazze
ich seh grad 20^20 is immernoch größer als 2^64

Hm, wird wohl Zeit mal 128 Bit Zahlen einzuführen.

Wenn du soviel Bits spendieren kannst, dann genügt natürlich auch folgender schneller Code: Jedem $\begin{eqnarray*} a_k \end{eqnarray*}$ werden 5 Bit spendiert (reicht also sogar für 0..31 statt nur 0..19), macht maximal 5 x 20 = 100 < 128 Bits Speicherbedarf. Durch einfaches Maskieren und Bitshifts kannst du die Codes auch meist schneller extrahieren als durch langsamere Division mit Rest.

Neue Frage »

Antworten »

injektive Abbildung gesucht

Verwandte Themen