Lottoergebnis mit möglichst wenig Bits codieren

[Michael Koch]

Mal angenommen wir hätten eine Zeitmaschine, mit der wir Informationen aus der Zukunft in die Gegenwart übertragen können. Aber die Übertragung eines Bits ist kompliziert und teuer. Deshalb muss die Information möglichst stark (aber verlustfrei) komprimiert werden.
Wieviele Bits braucht man, um ein Lottoergebnis 6 aus 49 zu übertragen?

Der einfachste Ansatz:
Um eine Zahl im Intervall [1..49] zu codieren braucht mal 6 Bit, also braucht man insgesamt 6 * 6 = 36 Bits.

Ein besserer Ansatz:
Wir können annehmen, dass die 6 Zahlen bereits der Größe nach sortiert sind. Die erste Zahl muss im Intervall [1..44] liegen, und die folgenden Zahlen werden nicht direkt codiert, sondern als Differenz zur vorausgehenden Zahl. Die Differenz muss ebenfalls im Intervall [1..44] liegen. Also gibt es 44^6 Möglichkeiten und dafür braucht man 33 Bits.

Ich vermute aber, dass es noch bessere Lösungen gibt.

Gruß
Michael

[Martin Vaeth]

Michael Koch <astroel...@t-online.de> wrote:
> Wieviele Bits braucht man, um ein Lottoergebnis 6 aus 49 zu übertragen?

Falls man nur Bit zur Verfügung hat (was ja informationstechnisch
bekanntlich nicht optimal ist), sind 24 Bit notwendig und hinreichend:

Es gibt ja 6 aus 49 Möglichkeiten, also 13983816.
Um so viele verschiedene Zahlen binär darzustellen, sind 24 Bit
notwendig und hinreichend. (Man nummeriere die Möglichkeiten irgendwie
durch und betrachte die entsprechende Binärzahl.)

[Michael Koch]

Ja, das leuchtet mir ein dass 24 Bit ausreichen müssen. Ich weiss nur noch nicht, wie ich die Möglichkeiten durchnummerieren soll, bzw. wie man von einer Nummer zurück zu den 6 Zahlen kommt.

Michael

[Martin Vaeth]

Michael Koch <astroel...@t-online.de> schrieb:

>
> Ich weiss nur noch nicht, wie ich die Möglichkeiten durchnummerieren
> soll

Beispielsweise alle sortierten alphanumerisch.

1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 5 8
...
1 2 3 4 5 49
1 2 3 4 6 7
1 2 3 4 6 8
...
1 2 3 4 6 49
1 2 3 4 7 8
...
1 2 3 4 44 49
1 2 3 4 45 46
1 2 3 4 45 47
1 2 3 4 45 48
1 2 3 4 46 47
1 2 3 4 46 48
1 2 3 4 47 48
1 2 3 4 48 49
1 2 3 5 6 7
...
44 45 46 47 48 49

[Thomas 'PointedEars' Lahn]

Martin Vaeth wrote:

> Michael Koch <astroel...@t-online.de> wrote:
>> Wieviele Bits braucht man, um ein Lottoergebnis 6 aus 49 zu übertragen?
>
> Falls man nur Bit zur Verfügung hat (was ja informationstechnisch
> bekanntlich nicht optimal ist), sind 24 Bit notwendig und hinreichend:

Das halte ich für ein Gerücht. Ich denke, Du hast die Fragestellung falsch
verstanden.

> Es gibt ja 6 aus 49 Möglichkeiten, also 13983816.

Spielt für die Information des *Ergebnisses* keine Rolle.

> Um so viele verschiedene Zahlen binär darzustellen, sind 24 Bit
> notwendig und hinreichend. (Man nummeriere die Möglichkeiten irgendwie
> durch und betrachte die entsprechende Binärzahl.)

Für die Speicherung der gesamten Information sind 49 Bit notwendig, denn zur
Information gehört auch, welche Zahlen _nicht_ gezogen wurden. Die Bits der
Zahlen, die gezogen wurden, sind dann gesetzt (1 oder 0), alle anderen nicht
(0 oder jeweils 1).

Wenn man nicht mit einer Bitmaske arbeitet, sondern die Zahlen als
Ganzzahlen abspeichert, sind je Zahl mindestens 1 Bit (1) und höchstens
6 Bits (49) notwendig. Für einen Bitstrom müssten aber auch noch eine
eindeutige und von den Zahlen unterscheidbare Trennsequenz hinzugerechnet
werden.

Die Übertragung mit der höchsten Laufzeiteffizienz verwendet allerdings
dieselbe Bitbreite für jede Zahl, also mindestens 6 · 6 = 36 Bits.
Typischerweise würde man hier mindestens ein 8-Bit-Byte für jede Zahl
verwenden, also insgesamt 48 Bits. Das ist interessanterweise tatsächlich
ein Bit weniger als für die Speicherung mit Bitmaske.

--
PointedEars
<https://github.com/PointedEars> | <http://PointedEars.de/wsvn/>
Twitter: @PointedEars2
Please do not cc me. /Bitte keine Kopien per E-Mail.

[Thomas 'PointedEars' Lahn]

Thomas 'PointedEars' Lahn wrote:

> Martin Vaeth wrote:
>> Um so viele verschiedene Zahlen binär darzustellen, sind 24 Bit
>> notwendig und hinreichend. (Man nummeriere die Möglichkeiten irgendwie
>> durch und betrachte die entsprechende Binärzahl.)
>
> Für die Speicherung der gesamten Information sind 49 Bit notwendig, denn
> zur Information gehört auch, welche Zahlen _nicht_ gezogen wurden. Die
> Bits der Zahlen, die gezogen wurden, sind dann gesetzt (1 oder 0), alle
> anderen nicht (0 oder jeweils 1).

Das ist tatsächlich nicht gesamte Information, wenn man ausserdem noch die
Ziehungsreihenfolge speichern will. Das gelingt nur mit den anderen von mir
beschriebenen Methoden.

Wie man die Lottozahlen inklusive Ziehungsreihenfolge mit nur 24 Bit
abbilden können soll, ist mir daher erst recht schleierhaft.

[Stefan Schmitz]

Am 27.11.2022 um 20:09 schrieb Thomas 'PointedEars' Lahn:
> Thomas 'PointedEars' Lahn wrote:
>
>> Martin Vaeth wrote:
>>> Um so viele verschiedene Zahlen binär darzustellen, sind 24 Bit
>>> notwendig und hinreichend. (Man nummeriere die Möglichkeiten irgendwie
>>> durch und betrachte die entsprechende Binärzahl.)
>>
>> Für die Speicherung der gesamten Information sind 49 Bit notwendig, denn
>> zur Information gehört auch, welche Zahlen _nicht_ gezogen wurden. D

Das ergibt sich daraus, welche der 49 über 6 Kombinationen herauskommt.

>> Bits der Zahlen, die gezogen wurden, sind dann gesetzt (1 oder 0), alle
>> anderen nicht (0 oder jeweils 1).
>
> Das ist tatsächlich nicht gesamte Information, wenn man ausserdem noch die
> Ziehungsreihenfolge speichern will. Das gelingt nur mit den anderen von mir
> beschriebenen Methoden.

Außer während der Ziehung selbst ist die Reihenfolge völlig egal. In
jeder Veröffentlichung sind die Zahlen sortiert.

[Thomas 'PointedEars' Lahn]

Stefan Schmitz wrote:

> Am 27.11.2022 um 20:09 schrieb Thomas 'PointedEars' Lahn:
>> Thomas 'PointedEars' Lahn wrote:
>>> Martin Vaeth wrote:
>>>> Um so viele verschiedene Zahlen binär darzustellen, sind 24 Bit
>>>> notwendig und hinreichend. (Man nummeriere die Möglichkeiten irgendwie
>>>> durch und betrachte die entsprechende Binärzahl.)
>>>
>>> Für die Speicherung der gesamten Information sind 49 Bit notwendig, denn
>>> zur Information gehört auch, welche Zahlen _nicht_ gezogen wurden. D
>
> Das ergibt sich daraus, welche der 49 über 6 Kombinationen herauskommt.

Das musst Du aber codieren. Du musst genau codieren, *welche* der
Kombinationen das Endergebnis war. Ich kenne dafür nur zwei Möglichkeiten:
Bits setzen, wobei jedes Bit für eine der möglichen Zahlen im Endergebnis
steht (man bräuchte dann also 49 Bits), oder die Zahlen selbst speichern.
Letztere Möglichkeit hat den Vorteil, auch die Reihenfolge zu speichern,
benötigt aber im Worst Case (hier ausnahmsweise nicht unbedingt) mehr
Speicherplatz.

In beiden Fällen reichen 24 Bits dafür im allgemeinen nicht aus.

>>> Bits der Zahlen, die gezogen wurden, sind dann gesetzt (1 oder 0), alle
>>> anderen nicht (0 oder jeweils 1).
>>
>> Das ist tatsächlich nicht gesamte Information, wenn man ausserdem noch
>> die
>> Ziehungsreihenfolge speichern will. Das gelingt nur mit den anderen von
>> mir beschriebenen Methoden.
>
> Außer während der Ziehung selbst ist die Reihenfolge völlig egal.

Ist sie natürlich nicht.

> In jeder Veröffentlichung sind die Zahlen sortiert.

Nochmal: Niemand interessiert sich für die Anzahl der Möglichkeiten. Gemäss
OP (den ich zugegebenermassen aufgrund Scorefile nur als Zitat gelesen habe)
geht es darum, das *Endergebnis* (verlustfrei) zu *übertragen*.

[Thomas 'PointedEars' Lahn]

Stefan Schmitz wrote:

> Am 27.11.2022 um 20:09 schrieb Thomas 'PointedEars' Lahn:
>> Thomas 'PointedEars' Lahn wrote:
>>> Martin Vaeth wrote:
>>>> Um so viele verschiedene Zahlen binär darzustellen, sind 24 Bit
>>>> notwendig und hinreichend. (Man nummeriere die Möglichkeiten irgendwie
>>>> durch und betrachte die entsprechende Binärzahl.)
>>>
>>> Für die Speicherung der gesamten Information sind 49 Bit notwendig, denn
>>> zur Information gehört auch, welche Zahlen _nicht_ gezogen wurden. D
>
> Das ergibt sich daraus, welche der 49 über 6 Kombinationen herauskommt.

Das musst Du aber codieren. Du musst genau codieren, *welche* der
Kombinationen das Endergebnis war. Ich kenne dafür nur zwei Möglichkeiten:
Bits setzen, wobei jedes Bit für eine der möglichen Zahlen im Endergebnis
steht (man bräuchte dann also 49 Bits), oder die Zahlen selbst speichern.
Letztere Möglichkeit hat den Vorteil, auch die Reihenfolge zu speichern,
benötigt aber im Worst Case (hier ausnahmsweise nicht unbedingt) mehr
Speicherplatz.

In beiden Fällen reichen 24 Bits dafür im allgemeinen nicht aus.

>>> Bits der Zahlen, die gezogen wurden, sind dann gesetzt (1 oder 0), alle
>>> anderen nicht (0 oder jeweils 1).
>>
>> Das ist tatsächlich nicht gesamte Information, wenn man ausserdem noch
>> die
>> Ziehungsreihenfolge speichern will. Das gelingt nur mit den anderen von
>> mir beschriebenen Methoden.
>
> Außer während der Ziehung selbst ist die Reihenfolge völlig egal.

Ist sie natürlich nicht.

> In jeder Veröffentlichung sind die Zahlen sortiert.

Eben.

[Fritz Feldhase]

On Sunday, November 27, 2022 at 9:33:08 PM UTC+1, Thomas 'PointedEars' Lahn wrote:

> Stefan Schmitz wrote:
> >
> > Außer während der Ziehung selbst ist die Reihenfolge völlig egal.
> >
> Ist sie natürlich nicht.

Für das "Lotoergebnis" schon. Siehe z. B.: https://www.lotterie.de/Lotto/lottoergebnisse/

Denn:

> > In jeder Veröffentlichung sind die Zahlen sortiert.

Mit 24 Bit kann man dann jedes mögliche Ergebnis "kommunizieren".

> > Das musst Du aber codieren. Du musst genau codieren, *welche* der
> > Kombinationen das Endergebnis war.

In der Tat. Im Thread ist eine Methode dazu angegeben worden. (Wie gesagt, für das/ein "Lotoergebniss" kann eine noch der Größe geordnete Folge von 6 "Zahlen" [aus dem Intervall 1 bis 49] angenommen werden. Siehe https://www.lotterie.de/Lotto/lottoergebnisse/)

> Nochmal: Niemand interessiert sich für die Anzahl der Möglichkeiten.

Naja, eigentlich schon. Wenn die Anzahl der Möglichkeiten (von irgendwas) kleiner-gleich als 2^24 ist (und das ist in diesem Fall gegeben), kann ich "eine der Möglichkeiten" mit 24 Bit "kommunizieren". Man muss dazu nur die möglichen Fälle/Werte irgenwie in eine Reihenfolge bringen und von 0 - (2^24 - 1) durchnummerieren. Dieser "Index" reicht dann, um die besagte Auswahl/den besagten Fall/Wert zu kommunizieren. Das wäre die von Dir geforderte Codierung. Zur Decodierung braucht der Empfänger dann natürlich eine gleichartig aufgebaute "Werteliste" (mit deren Hilfe er dann mittels des (in binärere Form) übermittelten Index den besagten Fall/Wert "eruieren" kann).

Nein?

[Michael Koch]

Völlig richtig. 24 Bit genügen. Die Ziehungsreihenfolge ist irrelevant. Es ist ja auch egal, in welcher Reihenfolge die 6 Kreuze auf dem Zettel gemacht werden.

Michael

[Ralf Goertz]

Am Sun, 27 Nov 2022 21:35:05 +0100
schrieb Thomas 'PointedEars' Lahn <Point...@web.de>:

> Stefan Schmitz wrote:
>
> > Am 27.11.2022 um 20:09 schrieb Thomas 'PointedEars' Lahn:
> >> Thomas 'PointedEars' Lahn wrote:
> >>> Martin Vaeth wrote:
> >>>> Um so viele verschiedene Zahlen binär darzustellen, sind 24 Bit
> >>>> notwendig und hinreichend. (Man nummeriere die Möglichkeiten
> >>>> irgendwie durch und betrachte die entsprechende Binärzahl.)
> >>>
> >>> Für die Speicherung der gesamten Information sind 49 Bit
> >>> notwendig, denn zur Information gehört auch, welche Zahlen
> >>> _nicht_ gezogen wurden. D
> >
> > Das ergibt sich daraus, welche der 49 über 6 Kombinationen
> > herauskommt.
>
> Das musst Du aber codieren. Du musst genau codieren, *welche* der
> Kombinationen das Endergebnis war. Ich kenne dafür nur zwei
> Möglichkeiten: Bits setzen, wobei jedes Bit für eine der möglichen
> Zahlen im Endergebnis steht (man bräuchte dann also 49 Bits), oder
> die Zahlen selbst speichern. Letztere Möglichkeit hat den Vorteil,
> auch die Reihenfolge zu speichern, benötigt aber im Worst Case (hier
> ausnahmsweise nicht unbedingt) mehr Speicherplatz.
>
> In beiden Fällen reichen 24 Bits dafür im allgemeinen nicht aus.

Es ist doch ganz einfach, die möglichen Kombinationen durchzunummerieren
und dann den Index zu übertragen, dann kommst du mit den 24 Bit aus.
Hier ein kleines C++-Programm, dass das erledigt. Code ist die Zahl
zwischen 0 und 13983815, die die entsprechende Kombination kodiert:


#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
vector<int> v(49);
fill_n(v.begin(),6,-1);
int code=0;
do {
cout<<"code "<<code++<<", drawn numbers:";
for (int i=0;i<v.size();++i) {
if (v[i]) cout<<" "<<i+1;
}
cout<<'\n';
} while (next_permutation(v.begin(),v.end()));
return 0;

}

> >>> Bits der Zahlen, die gezogen wurden, sind dann gesetzt (1 oder
> >>> 0), alle anderen nicht (0 oder jeweils 1).
> >>
> >> Das ist tatsächlich nicht gesamte Information, wenn man ausserdem
> >> noch die
> >> Ziehungsreihenfolge speichern will. Das gelingt nur mit den
> >> anderen von mir beschriebenen Methoden.
> >
> > Außer während der Ziehung selbst ist die Reihenfolge völlig egal.
>
> Ist sie natürlich nicht.

Wofür brauchst du die Reihenfolge? Ob 1,3,5,6,7,10 oder irgendeine
Permutation davon gezogen wurde ist doch wurst.

> > In jeder Veröffentlichung sind die Zahlen sortiert.
>
> Eben.

Eben. Wenn sortiert, erkennst du die Reihenfolge nicht mehr.

[Michael Koch]

Ralf Goertz schrieb am Montag, 28. November 2022 um 12:48:50 UTC+1:

> Es ist doch ganz einfach, die möglichen Kombinationen durchzunummerieren
> und dann den Index zu übertragen, dann kommst du mit den 24 Bit aus.
> Hier ein kleines C++-Programm, dass das erledigt. Code ist die Zahl
> zwischen 0 und 13983815, die die entsprechende Kombination kodiert:
>
>
> #include <iostream>
> #include <algorithm>
> #include <vector>
>
> using namespace std;
>
> int main() {
> vector<int> v(49);
> fill_n(v.begin(),6,-1);
> int code=0;
> do {
> cout<<"code "<<code++<<", drawn numbers:";
> for (int i=0;i<v.size();++i) {
> if (v[i]) cout<<" "<<i+1;
> }
> cout<<'\n';
> } while (next_permutation(v.begin(),v.end()));
> return 0;
> }
>

Uff, was für dich "ganz einfach" ist, da müsste ich jetzt erstmal stundenlang nachvollziehen was in den ausgelagerten Bibliotheken eigentlich genau gemacht wird.

Michael

[Paul Paulsen]

warum ist das nicht wichtig ?

wie soll man dann denn unterscheiden ?

- die gesuchte 1. Zahl ist kleiner 49, aber größer 10,
- die gesuchte 2. Zahl ist kleiner 49, aber kleiner 10,
...

- im 1. Fall hast Du >= 10 * 49 Möglichkeiten (also: 10 - 49 ).
- im 2. Fall hast Du <= 10 * 49 Möglichkeiten (also: 1 - 10 ).

und 10 - 49 Permutationen anstell von
1 - 10 Permutationen

sind schon nen gewaltiger Unterschied.

[Paul Paulsen]

Am 28.11.2022 um 20:07 schrieb Michael Koch:

> Uff, was für dich "ganz einfach" ist, da müsste ich jetzt erstmal stundenlang nachvollziehen was in den ausgelagerten Bibliotheken eigentlich genau gemacht wird.

ganz einfach gehalten:

Die Buchstaben(indexe) stehen für n aus 49.
A = 1
B = 2
C = 3
D = 4
E = 5
F = 6

- die Schleifen-Tiefe wird auf einen Stack gelegt
- der Stack hat eine bestimmte Größe (Tiefe) - hier: 6
- jeder Stack besteht 6 weiteren Schleifen (1 bis 49)
- die 6 Schleifen werden jeweils mit jeden Durchlauf um
eins (1) erhöht, bis 49 erreicht ist.
dann wird geschaut, in welcher Tiefe man sich befindet
und es wird ein "break" eingeleitet, der zur nächst-
höheren Stack-Schleife weiterleitet.
- dann werden wieder 6 weitere Schleifen durchlaufen -
jeweils (1 bis 49)
usw...
- bis man an Stack-Position 1 angelangt ist, und der
Programm-Algorythmus auf Stack - break (-1) = 0 stößt
und bedingt durch das "letzte" break, das Programm
beendet, bzw. unter den Schleifen-Kode weiterführt (zum
Beipsiel Auswertungen/Texte....):

Schleife_A von 1 bis 49 <-----------+
Schleife_B von 1 bis 49 <---------+ |
Schleife_C von 1 bis 49 <-------+ | |
Schleife_D von 1 bis 49 <-----+ | | |
Schleife_E von 1 bis 49 <---+ | | | |
Schleife_F von 1 bis 49 <-+ | | | | |
| | | | | |
for 1 .. 6 >---------+ | | | | |
break | | | | |
Schleife_F | | | | |
for 1 .. 6 >-----------+ | | | |
break | | | |
Schleife_E | | | |
for 1 .. 6 >-------------+ | | |
break | | |
Schleife_D | | |
for 1 .. 6 >---------------+ | |
break | |
Schleife_C | |
for 1 .. 6 >-----------------+ |
break |
Schleife_B |
for 1 .. 6 >-------------------+
break
Schleife_A

Hope this Helps
paule32

[Martin Vaeth]

Ralf Goertz <m...@myprovider.invalid> schrieb:

>
> Es ist doch ganz einfach, die möglichen Kombinationen durchzunummerieren
> und dann den Index zu übertragen, dann kommst du mit den 24 Bit aus.
> Hier ein kleines C++-Programm, dass das erledigt. Code ist die Zahl
> zwischen 0 und 13983815, die die entsprechende Kombination kodiert:
>
>
> #include <iostream>
> #include <algorithm>
> #include <vector>
>
> using namespace std;
>
> int main() {
> vector<int> v(49);
> fill_n(v.begin(),6,-1);
> int code=0;
> do {
> cout<<"code "<<code++<<", drawn numbers:";
> for (int i=0;i<v.size();++i) {
> if (v[i]) cout<<" "<<i+1;
> }
> cout<<'\n';
> } while (next_permutation(v.begin(),v.end()));
> return 0;
> }

Da std::next_permutation die Permutationen lexikographisch ordnet,
ist dies übrigens exakt die Kodierung, die ich in einem anderen
Posting vorgeschlagen hatte. Interessanter ist es allerdings, diese
Kodierung von "k aus n" in beide Richtungen in linearer statt
exponentieller Zeit zu berechnen:
https://en.wikipedia.org/wiki/Combinatorial_number_system

Interessant wäre vielleicht auch die Lösung des allgemeineren Problems:
Finde die n-te Permutation (in lexikographischer Ordnung) bzw.
n aus der Permutation in linearer Zeit.

Für den Fall, dass es nur zwei verschiedene Zeichen gibt, sind wir
bei obigem Problem, und für den Fall, dass alle Zeichen verschieden
sind, geht https://en.wikipedia.org/wiki/Factorial_number_system

Aber für den allgemeinen Fall, dass j_1, j_2, ..., j_l
(mit j_1+...+j_l=n) Zeichen gleich sind!?

Alles schon beantwortet:
https://math.stackexchange.com/questions/3276390/
multinomial-permutation-indexing

[Ralf Goertz]

Am Mon, 28 Nov 2022 11:07:00 -0800 (PST)
schrieb Michael Koch <astroel...@t-online.de>:

> Ralf Goertz schrieb am Montag, 28. November 2022 um 12:48:50 UTC+1:
>
> > Es ist doch ganz einfach, die möglichen Kombinationen
> > durchzunummerieren und dann den Index zu übertragen, dann kommst du
> > mit den 24 Bit aus. Hier ein kleines C++-Programm, dass das
> > erledigt. Code ist die Zahl zwischen 0 und 13983815, die die
> > entsprechende Kombination kodiert:
>

> Uff, was für dich "ganz einfach" ist, da müsste ich jetzt erstmal
> stundenlang nachvollziehen was in den ausgelagerten Bibliotheken
> eigentlich genau gemacht wird.

Ja, sorry, da ich solches Durchlaufen aller möglichen Kombinationen von
k Elementen aus einer Menge von Elementen häufig brauche, geht es mir
leicht von der Hand. Ich zeige die Idee mal anhand eines kleineren
Beispiels n=5, k=2. Ich habe das Programm dazu ein bisschen angepasst,
um auch das Feld v anzuzeigen (Markierung 4):

#include <iostream>
#include <algorithm>
#include <vector>

#include <iterator>

using namespace std;

int main() {

vector<int> v(5); //1
fill_n(v.begin(),2,-1); //2

int code=0;
do {
cout<<"code "<<code++<<", drawn numbers:";
for (int i=0;i<v.size();++i) {

if (v[i]) cout<<" "<<i+1; //3
}
cout<<". array: ";
copy(v.begin(),v.end(),ostream_iterator<int>(cout," ")); //4

cout<<'\n';
} while (next_permutation(v.begin(),v.end()));
return 0;
}

v (Markierung 1) ist ein Feld mit 5 Elementen, das zunächst mit Nullen
initialisiert wird. Dann werden in (2) die ersten beiden Elemente auf -1
gesetzt (ich brauche eine Zahl, die kleiner ist als 0 für
next_permutation()). Diese zwei repräsentieren die Kombination {0,1}
(bei der Ausgabe (3) addiere ich 1, damit wir uns im Bereich 1,…,n
bewegen. Der Clou des Algortihmus ist die Funktion (ich glaube, sie
stammt aus „The Art of Computer Programming“ von Donald Knuth)
next_permutation(). Sie berechnet, wie Martin angemerkt hat, aus der
aktuellen Permutation die lexikographisch nächstgrößere und funktioniert
sogar dann richtig, wenn wir identische Elemente im Feld haben (hier
zwei -1 und drei 0). Falls wir bei der größten Permutation angekommen
sind, wird false zurückgeliefert und die Schleife beendet. Der
Schleifenzähler „code“ ist dann der Wert, der die Information über die
Kombination in der kleinstmöglichen Bittiefe enthält. Die Ausgabe des
obigen Programms ist übrigens:

code 0, drawn numbers: 1 2. array: -1 -1 0 0 0
code 1, drawn numbers: 1 3. array: -1 0 -1 0 0
code 2, drawn numbers: 1 4. array: -1 0 0 -1 0
code 3, drawn numbers: 1 5. array: -1 0 0 0 -1
code 4, drawn numbers: 2 3. array: 0 -1 -1 0 0
code 5, drawn numbers: 2 4. array: 0 -1 0 -1 0
code 6, drawn numbers: 2 5. array: 0 -1 0 0 -1
code 7, drawn numbers: 3 4. array: 0 0 -1 -1 0
code 8, drawn numbers: 3 5. array: 0 0 -1 0 -1
code 9, drawn numbers: 4 5. array: 0 0 0 -1 -1

[Michael Koch]

Danke für deine Erläuterungen. So allmählich wird mir klar wie das Programm funktioniert.

Michael

[Ralf Goertz]

Am Mon, 28 Nov 2022 20:17:10 -0000 (UTC)
schrieb Martin Vaeth <mar...@mvath.de>:

> Ralf Goertz <m...@myprovider.invalid> schrieb:
> >
> > Es ist doch ganz einfach, die möglichen Kombinationen
> > durchzunummerieren und dann den Index zu übertragen, dann kommst du
> > mit den 24 Bit aus. Hier ein kleines C++-Programm, dass das
> > erledigt. Code ist die Zahl zwischen 0 und 13983815, die die
> > entsprechende Kombination kodiert:
> >
> >
>

> Da std::next_permutation die Permutationen lexikographisch ordnet,
> ist dies übrigens exakt die Kodierung, die ich in einem anderen
> Posting vorgeschlagen hatte. Interessanter ist es allerdings, diese
> Kodierung von "k aus n" in beide Richtungen in linearer statt
> exponentieller Zeit zu berechnen:
> https://en.wikipedia.org/wiki/Combinatorial_number_system

Cool, das kannte ich nicht. Spannend finde ich, dass man gar nicht
wissen muss, wie groß die Menge ist, aus der die Elemente stammen. In
Pari wäre das folgende Funktion:


lehmer=vec->{
my(v=vecsort(vec));
my(s=0);
for (i=1,length(v),
s=s+binomial(v[i],i)
);
return(s)
}

Mit
x=[[0,1], [0,2], [0,3], [0,4], [1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]
(die zweielementigen Kombinationen aus der Menge von {0,…,4} in
lexikographischer Ordnung) ergibt

for (k=1,10,print(lehmer(x[k])))
0
1
3
6
2
4
7
5
8
9

also insbesondere anders als die lexikographische Reihenfolge.

[Fritz Feldhase]

On Tuesday, November 29, 2022 at 10:26:46 AM UTC+1, Ralf Goertz wrote: [...]

ZIemlich brachial, aber geht auch (in Python) [Achtung: Google wird wohl die Spaces schlucken]:

def encode(lottoresult):
n = 0
for n1 in range(1, 44 + 1):
for n2 in range(n1 + 1, 45 + 1):
for n3 in range(n2 + 1, 46 + 1):
for n4 in range(n3 + 1, 47 + 1):
for n5 in range(n4 + 1, 48 + 1):
for n6 in range(n5 + 1, 49 + 1):
n += 1
if [n1, n2, n3, n4, n5, n6] == lottoresult:
return n;

def decode(idx):
n = 0
for n1 in range(1, 44 + 1):
for n2 in range(n1 + 1, 45 + 1):
for n3 in range(n2 + 1, 46 + 1):
for n4 in range(n3 + 1, 47 + 1):
for n5 in range(n4 + 1, 48 + 1):
for n6 in range(n5 + 1, 49 + 1):
n += 1
if n == idx:
return [n1, n2, n3, n4, n5, n6];

lottoergebnis = [2, 5, 9, 14, 23, 45]

index = encode(lottoergebnis)
print(index)

ergebnis = decode(index)
print(ergebnis)

[Paul Paulsen]

auch ganz nett !

was ich an Python so nie verstanden habe, das dort
immer nen Tab-Leerzeichen vorhanden sein muss.


--
Diese E-Mail wurde von Avast-Antivirussoftware auf Viren geprüft.
www.avast.com

[Tom Bola]

Ralf Goertz schrieb:

> Am Mon, 28 Nov 2022 20:17:10 -0000 (UTC)
> schrieb Martin Vaeth <mar...@mvath.de>:
>> Ralf Goertz <m...@myprovider.invalid> schrieb:

>> https://en.wikipedia.org/wiki/Combinatorial_number_system
>
> Cool, das kannte ich nicht.

Ja wirklich cool, kannte ich ebenfalls nicht...

[Thomas 'PointedEars' Lahn]

Paul Paulsen wrote:

> was ich an Python so nie verstanden habe, das dort
> immer nen Tab-Leerzeichen vorhanden sein muss.

Führende Tabulator-Zeichen oder eine einheitliche Anzahl (Empfehlung:
Vielfache von 4) führender Leerzeichen wird/werden in Python zur Definition
eines Anweisungsblocks benutzt. Dies ersetzt die in C-ähnlichen Sprachen
verwendete Kombination aus “{” und “}”.

[Stefan Schmitz]

Am 02.12.2022 um 16:51 schrieb Stefan Ram:
> r...@zedat.fu-berlin.de (Stefan Ram) writes:
>> Das sind echt weniger als 24 Bit! Will man zum Beispiel zehn
>> solcher Information übermitteln, braucht man nicht 240,
>> sondern nur 237 Bit!
>
> D.h.: wenn man sie in einer einzigen Nachricht übermitteln will.
>
> Siehe auch
>
> https://www.purl.org/stefan_ram/pub/bit
>
> , insbesondere den Abschnitt "Kann ein Speicher 1,58 Bit enthalten?".

Und wie gelangt man dann an die einzelne Information?

[Thomas 'PointedEars' Lahn]

Paul Paulsen wrote:

> warum ist das nicht wichtig ?

Dein Posting ist ohne Nachschauen unverständlich. Bitte zitiere das
Wesentliche von dem, auf das Du Dich beziehst.

<https://einklich.net/usenet/zitier>

Worauf willst Du hinaus?

Permutationen/Kombinationen einer Menge kann man geeignet sortieren. Daher
kann man sie auch indizieren, und für den *Index* braucht man hier
tatsächlich nur 24 Bit. Ein möglicher Ansatz:

Index i :
-----------+------------------
0 : 1 2 3 4 5 6
1 : 1 2 3 4 5 7
2 : 1 2 3 4 5 8
3 : 1 2 3 4 5 9
4 : 1 2 3 4 5 10
5 : 1 2 3 4 5 11
6 : 1 2 3 4 5 12
…
44 : 1 2 3 4 6 5
45 : 1 2 3 4 6 7
…
13 983 815 : 49 48 47 46 45 44

Mit 24 Bit kann man 2²⁴ = 16 777 216 Zustände darstellen, also mehr als die
Anzahl Kombinationen in diesem Fall.

Allerdings ist das trotzdem nicht die effizienteste Form der Übertragung
eines Lottoergebnisses. Erstens, weil Sender und Empfänger die Code-Tabelle
vorhalten oder generieren müssen. So stehen 49 bit (Bitmaske) oder 48 bit
(Zahlenstrom) hier mindestens 2 · 13 983 816 · 48 Bit ≈ 1.34 Mbit ≈ 171 MiB
für die Code-Tabelle gegenüber.

Demgegenüber spart man bei der Übertragung unter Verwendung der Code-Tabelle
(falls man die Tabelle nicht auch übertragen muss) nur 24 bit gegenüber dem
Zahlenstrom und 25 bit gegenüber der Bitmaske.

Es ist also bereitd deshalb ein Trugschluss anzunehmen, mit der Indizierung
der Kombinationen würde man etwas einsparen und so das im Betreff genannte
Ziel erreichen. Auch wenn das Mapping eines Ergebnisses auf einen Index
durch geeignete Datenstrukturen wie Bäume relativ effizient ist [𝓞(1)].

Zweitens, wie mir gerade auffällt, weil sich in dieser Tabelle (bzw. dem
daraus generierten Baum) Duplikate von Ziehungsergebnissen gerade deshalb
ergeben, weil die Reihenfolge der Zahlen in der Veröffentlichung, in der bei
„6 aus 49“ aufsteigend sortiert wird, keine Rolle spielt. Zum Beispiel wäre
die Veröffentlichung für die Ziehung mit dem Index 0 und 44 identisch: 1 2 3
4 5 6. Ausser man schliesst das von vornherein aus, dann wird aber der
Prozess, die Tabelle/den Baum zu generieren, ineffizienter.

[Martin Vaeth]

Thomas 'PointedEars' Lahn <Point...@web.de> schrieb:

>
> Allerdings ist das trotzdem nicht die effizienteste Form der Übertragung
> eines Lottoergebnisses.

Doch. Unter der Voraussetzung, dass Du nicht a-priori Wissen über das
Lottorgebnis hast, ist es das.

> Erstens, weil Sender und Empfänger die Code-Tabelle vorhalten oder
> generieren müssen.

Falsch, und zwar aus zwei Gründen.

Erstens, weil sich Sender und Empfänger auf eine Codierung einigen
müssen, und zwar unabhängig davon, welche Codierung letztlich gewählt
wird. Dass die eine oder andere Codierung leichter erratbar scheint,
liegt nur daran, dass wir diese Codierung öfter benutzen, und das hat
also nur mit a-priori Wissen über eine Codierung etwas zu tun.

Ich würde mal behaupten, wenn ich eine Information von 24 Bit und eine
von 48 oder 49 bit erhalte und wüsste, dass es um Lottozahlen geht,
könnte ich in allen 3 Fällen die Codierung aufgrund des a-priori
Wissens ziemlich wahrscheinlich erraten, wobei das eben nur ein Raten
ist und falsch sein kann (z.B. high-endian vs. low-endian, findet ev.
eine Vertauschung der Endianness auf Byte-Ebene (8 bit) und/oder
Wort-Ebene (16 bit) und/oder 32 bit statt)? Wie gesagt: Ohne genaue
Kenntnis der Codierung ist letztlich keine Decodierung möglich.

Zweitens müssen weder Sender noch Empfänger eine Code-Tabelle vorhalten
noch generieren: Verfahren zur direkten Codierung und Decodierung (ohne
Berechnung "vorheriger" Codes) wurde bereits verlinkt.
Aber selbst wenn es kein *effizientes* solches Verfahren gäbe, genügt
die Information *welche* Codierung benutzt wird: Man braucht halt dann
ggf. nur entsprechend lange für die Codierung und Decodierung.

> So stehen 49 bit (Bitmaske) oder 48 bit
> (Zahlenstrom) hier mindestens 2 · 13 983 816 · 48 Bit ≈ 1.34 Mbit ≈ 171 MiB
> für die Code-Tabelle gegenüber.

Beides ist Unsinn, weil Du die Nicht-Übertragung der Codierung mit einer
Übertragung der Codierung vergleichst, letzteres auch noch auf denkbar
ungeschickte Weise durchführen willst.

> Es ist also bereitd deshalb ein Trugschluss anzunehmen, mit der Indizierung
> der Kombinationen würde man etwas einsparen

Der einzige, der hier einem Trugschluss aufsitzt bist Du.

Wobei man natürlich schon darauf hinweisen kann und muss, dass sich ein
solches Verfahren i.a. nicht dazu eignet, allgemein 49-bit Information
auf 24-Bit zu komprimieren: Dies geht in diesem Fall eben nur deswegen,
weil man gewisse a-priori Informationen über die 49-bit hat - in diesem
Fall eben die Information, dass von den 49 Bit genau 6 gesetzt sind.

Wenn man solche Zusatzinformationen zusätzlich verkodieren muss, kann
man letztlich i.A. genau gar nichts komprimieren. Das Stichwort hierzu
lautet Kolmogorov-Komplexität. Interessanterweise haben die meisten in
der Praxis benutzten Daten nur eine relativ geringe
Kolmogorov-Komplexität - weshalb sie sich gut komprimieren lassen -
wohingegen aus den theoretisch möglichen Daten die meisten nahezu
volle Kolmogorov-Komplexität haben müssten.

> Auch wenn das Mapping eines Ergebnisses auf einen Index
> durch geeignete Datenstrukturen wie Bäume relativ effizient ist [𝓞(1)].

Mit Bäumen haben die effizienten Algorithmen nichts zu tun,
und die Laufzeit von Algorithmen mit Bäumen wöre auch nicht konstant -
außer, man stellt sich auf den Standpunkt, dass es nicht um ein
Problem mit variables Eingabelänge geht, weil man ja *ausschließlich*
"6 aus 49" betrachte will:
In dem Fall hat natürlich *jeder* Algorithmus konstante Laufzeit.

> Zweitens, wie mir gerade auffällt, weil sich in dieser Tabelle (bzw. dem
> daraus generierten Baum) Duplikate von Ziehungsergebnissen gerade deshalb
> ergeben, weil die Reihenfolge der Zahlen in der Veröffentlichung, in der bei
> „6 aus 49“ aufsteigend sortiert wird, keine Rolle spielt.

Genau aus diesem Grund kommt man ja mit 24 Bit aus. Wenn Du Deine
Tabelle nicht so verstanden haben solltest, hast Du einen Fehler
gemacht: Dann hat sie nämlich eine Länge von 49!/43! bzw. 49^6
(falls Du sogar doppelte Zahlen erlauben wolltest), und wenn diese
Information relevant sein sollte und mitübertragen werden muss,
wären die codierten Daten in beiden Fällen 34 Bit lang (die Länge
ist wegen der Aufrundung auf ganze Bit zufälligerweise gleich).

> Ausser man schliesst das von vornherein aus, dann wird aber der
> Prozess, die Tabelle/den Baum zu generieren, ineffizienter.

Wird es nicht, wenn man es klug macht, und wie gesagt, muss man
gar keine Tabelle generieren.

[Martin Vaeth]

Stefan Ram <r...@zedat.fu-berlin.de> schrieb:
> 23.73725477120831... bit.

>
> Das sind echt weniger als 24 Bit!

Nein. (Wenn man nur Bit zur Verfügung hat, was ich ganz
zu Beginn meiner Antwort auch nochmals explizit betont hatte.)

> Will man zum Beispiel zehn solcher Information übermitteln

Will man aber nicht: Das Problem lautete, *ein* Lottoergbnis
mit möglichst wenig Bits zu codieren, und nicht zehn solche,
oder es mit anderen Daten zu kombinieren.
Dass man von der Optimalzahl für das erste Problem nur
begrenzt auf die Optimalzahl für andere Probleme schließen
kann, ist nicht überraschend.

> Die Kodierung muß man nicht kennen, um die Frage zu
> beantworten. Aber das folgende Programm liefert eine
> Möglichkeit.

In exponentieller Laufzeit (im allgemeinen "d aus n"-Fall);
wurde bereits gepostet, sowohl in Worten also auch in C++,
ebenso wie Links zu Algorithmen, die nur lineare Laufzeit
benötigen, und zu linearen Algorithmen für allgemeinere
Probleme.

[Fritz Feldhase]

On Saturday, December 3, 2022 at 12:41:24 PM UTC+1, Thomas 'PointedEars' Lahn wrote:

> Ein möglicher Ansatz:
>
> Index i :
> -----------+------------------
> 0 : 1 2 3 4 5 6
> 1 : 1 2 3 4 5 7
> 2 : 1 2 3 4 5 8
> 3 : 1 2 3 4 5 9
> 4 : 1 2 3 4 5 10
> 5 : 1 2 3 4 5 11
> 6 : 1 2 3 4 5 12
> …
> 44 : 1 2 3 4 6 5
> 45 : 1 2 3 4 6 7
> …
> 13 983 815 : 49 48 47 46 45 44

Kann eigentlich nicht sein, da bei Deiner "Indizierung" Lottoergebnisse offenbar 2-mal auftreten können.

Ich zähle so:

0 : 1 2 3 4 5 6
1 : 1 2 3 4 5 7
2 : 1 2 3 4 5 8
3 : 1 2 3 4 5 9
4 : 1 2 3 4 5 10
5 : 1 2 3 4 5 11
6 : 1 2 3 4 5 12
…

43 : 1 2 3 4 5 49
44 : 1 2 3 4 6 7
:
13983815 : 49 48 47 46 45 44

Komme also auf die gleich Anzahl an Lottoergebnissen (13983815), aber OHNE dass in meiner Tabelle welche doppelt auftreten.

> Mit 24 Bit kann man 2²⁴ = 16 777 216 Zustände darstellen, also mehr als die
> Anzahl Kombinationen in diesem Fall.

Jep.

> Allerdings [...]

Sender und Empfänger müssen sich erst mal auf ein "Austauschformat" (eine Codierung) einigen. Das wird hier nicht berücksichtigt. Und zwar aus gutem Grund, wie ich denke. Diese "Einigung" benötigt offensichtlich lediglich eine konstante/endliche Anzahl an "Bits" (siehe die Sourcecodes und Erklärungen in diesem Thread). DANACH kann ein Lottoergebnis mithilfe der besagten 24 Bits _übertragen_ werden.

Je mehr Lottoergebnisse nun (im Laufe der Zeit) übertragen werden, um so weniger fällt die oben erwähnte (konstante) Datenmenge (die für den initialen Austausch bezüglich der Codierung benötigt wird) ins Gewicht. Wenn N die Anzahl der übertragenen Lottoergebnisse ist, nähert sich die Gesamtzahl der "benötigten Bits" (mit wachsendem N) immer mehr N * 24 Bit an. Anders formuliert lim_(N->oo) "Gesamtzahl der benötigten Bits"/N = 24.

Dass die Codierung/Decodierung der Lottoergebnisse mit einem gewissen "Aufwand" verbunden ist, ist natürlich richtig. Nur hat das nichts mit der eigentlichen Problemstellung (siehe OP) zu tun.

[Thomas 'PointedEars' Lahn]

Martin Vaeth wrote:

> Thomas 'PointedEars' Lahn <Point...@web.de> schrieb:
>> Allerdings ist das trotzdem nicht die effizienteste Form der Übertragung
>> eines Lottoergebnisses.
>
> Doch. Unter der Voraussetzung, dass Du nicht a-priori Wissen über das
> Lottorgebnis hast, ist es das.

A-priori Wissen ist immer vorhanden, es handelt sich ja nach Vorgabe um
Lotto „6 aus 49“: Es können genau 6 Zahlen jeweils von 1 bis 49 vorkommen
und keine Zahl kann mehrfach vorkommen.

>> Erstens, weil Sender und Empfänger die Code-Tabelle vorhalten oder
>> generieren müssen.
>
> Falsch, und zwar aus zwei Gründen.
>
> Erstens, weil sich Sender und Empfänger auf eine Codierung einigen
> müssen, und zwar unabhängig davon, welche Codierung letztlich gewählt
> wird. Dass die eine oder andere Codierung leichter erratbar scheint,
> liegt nur daran, dass wir diese Codierung öfter benutzen, und das hat
> also nur mit a-priori Wissen über eine Codierung etwas zu tun.

Es geht aber nicht darum, wie leicht eine Codierung erratbar ist, sondern
wie effizient die Codierung, Übertragung und Decodierung der Information
ist.

> Zweitens müssen weder Sender noch Empfänger eine Code-Tabelle vorhalten
> noch generieren: Verfahren zur direkten Codierung und Decodierung (ohne
> Berechnung "vorheriger" Codes) wurde bereits verlinkt.

Gut, wenn das möglich ist, dann ist Laufzeit- und Speichereffizienz keines
der Probleme mit diesem Ansatz mehr. Sender und Empfänger müssen aber
dieselbe Software benutzen (können). Bei der Übertragung der Bitmaske oder
reinen Zahlen ist das nicht nötig.

> Aber selbst wenn es kein *effizientes* solches Verfahren gäbe, genügt
> die Information *welche* Codierung benutzt wird: Man braucht halt dann
> ggf. nur entsprechend lange für die Codierung und Decodierung.

Genau das habe ich als Problem identifiziert und diskutiert.

>> So stehen 49 bit (Bitmaske) oder 48 bit (Zahlenstrom) hier mindestens 2 ·
>> 13 983 816 · 48 Bit ≈ 1.34 Mbit ≈ 171 MiB für die Code-Tabelle gegenüber.
>
> Beides ist Unsinn, weil Du die Nicht-Übertragung der Codierung mit einer
> Übertragung der Codierung vergleichst,

Nein; ich denke nur praktisch und berücksichtige alle Aspekte der
Implementierung; wohingegen Du meinst, es käme nur auf das übertragene
Datenvolumen an.

> letzteres auch noch auf denkbar ungeschickte Weise durchführen willst.

Ob das so ungeschickt ist, hängt von den Gegebenheiten ab.

>> Es ist also bereitd deshalb ein Trugschluss anzunehmen, mit der
>> Indizierung der Kombinationen würde man etwas einsparen
>
> Der einzige, der hier einem Trugschluss aufsitzt bist Du.

Das denke ich nicht.

>> Auch wenn das Mapping eines Ergebnisses auf einen Index
>> durch geeignete Datenstrukturen wie Bäume relativ effizient ist [𝓞(1)].
>
> Mit Bäumen haben die effizienten Algorithmen nichts zu tun,

Das kommt auf die Algorithmen an. Es ist möglich, mit Bäumen ein solches
Mapping effizient durchzuführen.

> und die Laufzeit von Algorithmen mit Bäumen wöre auch nicht konstant -
> außer, man stellt sich auf den Standpunkt, dass es nicht um ein
> Problem mit variables Eingabelänge geht, weil man ja *ausschließlich*
> "6 aus 49" betrachte will:
> In dem Fall hat natürlich *jeder* Algorithmus konstante Laufzeit.

Konstant ja (die Anzahl der Daten ist ja endlich), aber nicht jeder
Suchalgorithmus hat dieselbe Komplexität.

>> Zweitens, wie mir gerade auffällt, weil sich in dieser Tabelle (bzw. dem
>> daraus generierten Baum) Duplikate von Ziehungsergebnissen gerade deshalb
>> ergeben, weil die Reihenfolge der Zahlen in der Veröffentlichung, in der
>> bei „6 aus 49“ aufsteigend sortiert wird, keine Rolle spielt.
>
> Genau aus diesem Grund kommt man ja mit 24 Bit aus. Wenn Du Deine
> Tabelle nicht so verstanden haben solltest, hast Du einen Fehler
> gemacht: Dann hat sie nämlich eine Länge von 49!/43! bzw. 49^6
> (falls Du sogar doppelte Zahlen erlauben wolltest),

Will ich nicht, wie aus meinm Beispiel hervorgeht.

> und wenn diese Information relevant sein sollte und mitübertragen werden
> muss,

Das hatte ich als optional bezeichnet.

> wären die codierten Daten in beiden Fällen 34 Bit lang

Wie kommst Du darauf?

[Thomas 'PointedEars' Lahn]

Fritz Feldhase wrote:
^^^^^^^^^^^^^^
Ist das Dein richtiger Name?

> On Saturday, December 3, 2022 at 12:41:24 PM UTC+1, Thomas 'PointedEars'
> Lahn wrote:
>> Ein möglicher Ansatz:
>>
>> Index i :
>> -----------+------------------
>> 0 : 1 2 3 4 5 6
>> 1 : 1 2 3 4 5 7
>> 2 : 1 2 3 4 5 8
>> 3 : 1 2 3 4 5 9
>> 4 : 1 2 3 4 5 10
>> 5 : 1 2 3 4 5 11
>> 6 : 1 2 3 4 5 12
>> …
>> 44 : 1 2 3 4 6 5
>> 45 : 1 2 3 4 6 7
>> …
>> 13 983 815 : 49 48 47 46 45 44
>
> Kann eigentlich nicht sein, da bei Deiner "Indizierung" Lottoergebnisse
> offenbar 2-mal auftreten können.

Stimmt; das sind alle _Variationen_ [n!/(n − k)!]; ich hatte die Bedeutung
des Binomialkoeffizienten hier falsch verstanden, weswegen mein maximaler
Index falsch ist:

<https://de.wikipedia.org/wiki/Kombination_(Kombinatorik)>

Ich hatte aber weiter unten darauf hingewiesen, dass in dieser Tabelle
Lottoergebnisse, die sich nur in der Ziehungsreihenfolge von anderen
unterscheiden, noch enthalten sind.

> Ich zähle so:
>
> 0 : 1 2 3 4 5 6
> 1 : 1 2 3 4 5 7
> 2 : 1 2 3 4 5 8
> 3 : 1 2 3 4 5 9
> 4 : 1 2 3 4 5 10
> 5 : 1 2 3 4 5 11
> 6 : 1 2 3 4 5 12
> …
> 43 : 1 2 3 4 5 49
> 44 : 1 2 3 4 6 7
> :
> 13983815 : 49 48 47 46 45 44
>
> Komme also auf die gleich Anzahl an Lottoergebnissen (13983815), aber OHNE
> dass in meiner Tabelle welche doppelt auftreten.

Ja. Dann geht aber die Information über die Ziehungsreihenfolge verloren.

[Carlo XYZ]

Thomas 'PointedEars' Lahn wrote on 04.12.22 00:47:

> Fritz Feldhase wrote:
> ^^^^^^^^^^^^^^
> Ist das Dein richtiger Name?

Netcops sind hier unerwünscht. Piss off.

[Martin Vaeth]

Thomas 'PointedEars' Lahn <Point...@web.de> schrieb:
> Martin Vaeth wrote:
>
>> Thomas 'PointedEars' Lahn <Point...@web.de> schrieb:
>>> Allerdings ist das trotzdem nicht die effizienteste Form der Übertragung
>>> eines Lottoergebnisses.
>>
>> Doch. Unter der Voraussetzung, dass Du nicht a-priori Wissen über das
>> Lottorgebnis hast, ist es das.
>
> A-priori Wissen ist immer vorhanden, es handelt sich ja nach Vorgabe um
> Lotto „6 aus 49“

Damit hat man das a-priori-Wissen strenggenomme eben noch nicht exakt
spezifiziert.

> Es geht aber nicht darum, wie leicht eine Codierung erratbar ist, sondern
> wie effizient die Codierung, Übertragung und Decodierung der Information
> ist

Eben. Und wenn man sich darauf einigt, dass es genau darum geht, ist
die Spezifizierung der Codierung Teil des a-priori Wissens, wie auch
immer die Codierung aussieht.

> Sender und Empfänger müssen aber dieselbe Software benutzen (können).

Nein. Sender und Empfänger müsse beide die Codierung kennen.
Welche Software sie zum codieren oder decodieren benutzen, ist
vollkommen egal.

> Bei der Übertragung der Bitmaske oder reinen Zahlen ist das nicht nötig.

Doch. Selbstverständlich ist das da genauso nötig. Stell Dir vor, Du
erhälst einige Bytes aus der Zukunft und erfährst nur, dass es die
Lottozahlen enthält. Das könnte der Bitstream sein, die Zahlen in
49-er Basis als eine große Binärzahl codiert, die Zahlen in 64-er Basis,
pro Byte eine Zahl beginnend bei 0, pro Byte eine Zahl beginnend bei 1,
usw.
Klar, aufgrund der Länge und ggf. großer Redundanz kannst Du die
Codierung mit gewisser Wahrscheinlichkeit erraten, aber oben haben
wir uns ja darauf geeinigt, dass es nicht darum geht, wie leicht
es zu erraten ist, sondern wie effizient es ist.
Bei Bitmaske und reinen Zahlen das eben genau *nicht* ineffizient,
sogar so ineffizient, dass in den redundanten Informationen implizit
so viel drin steckt, dass Du mit großer Wahrscheinlichkeit die
Codierung *erraten* kannst. Aber eben auch nicht sicher:
Wenn Du 8 Bytes hast, und es sind genau 6 Bit gesetzt, ist die
Wahrscheinlichkeit für einen Bytestream hoch, aber Du musst Du immer
noch raten, welches Bit für welche Zahl steht. (Es gibt da zwar nur
einige "kanonische" Möglichkeiten, aber immer noch einige.)

>> Beides ist Unsinn, weil Du die Nicht-Übertragung der Codierung mit einer
>> Übertragung der Codierung vergleichst,
>
> Nein; ich denke nur praktisch und berücksichtige alle Aspekte der
> Implementierung

Eben nicht: Du diskutierst die Übertragung der Weise der Codierung
eben nur in einem Fall und nimmst fälschlicherweise an, dass Du das
im anderen Fall nicht tun müsstest.

Tatsächlich lässt sich die Frage der Übertragung der *Codierung* aber
höchstens dann "in Bit" beantworten, wenn man das Vorwissen von
Sender und Empfänger *exakt* spezifiziert. Deswegen ist die
Kolmogorov-Komplexität auch nur bis auf eine addititve
Konstante definiert, die dann ggf. von weiteren Spezifizierungen
abhängt.

> wohingegen Du meinst, es käme nur auf das übertragene
> Datenvolumen an.

Weil das die einzig sinnvolle Frage in diesem Zusammenhang ist.

>> letzteres auch noch auf denkbar ungeschickte Weise durchführen willst.
>
> Ob das so ungeschickt ist, hängt von den Gegebenheiten ab.

Jein: Wie oben erwähnt hängt die Frage der "geschicktesten"
Übertragung der Codierung natürlich von der exakten Spezifikation
des a-priori Wissens des Empfängers ab. Wenn das allerdings
die geschickteste Form sein sollte, und es für andere Codierungen
kürzer als mit einer Tabelle von ähnlicher Länge ginge: Man kann
natürlich so eine Spezifikation machen, aber das hat mit der
von Dir vorgeschobenen "Praxisnähe" natürlich nichts zu tun.

>> Der einzige, der hier einem Trugschluss aufsitzt bist Du.

Ich bitte um Entschuldigung für die unangemessene ad-hominem
Formulierung.

>>> Auch wenn das Mapping eines Ergebnisses auf einen Index
>>> durch geeignete Datenstrukturen wie Bäume relativ effizient ist [𝓞(1)].
>>
>> Mit Bäumen haben die effizienten Algorithmen nichts zu tun,
>
> Das kommt auf die Algorithmen an. Es ist möglich, mit Bäumen ein
> solches Mapping effizient durchzuführen.

Es ist natürlich immer möglich, Bäume künstlich einzuführen, aber
bei der gegebenen Abbildung tauchen sie m.E. nicht natürlich auf.

>> In dem Fall hat natürlich *jeder* Algorithmus konstante Laufzeit.
>
> Konstant ja (die Anzahl der Daten ist ja endlich), aber nicht jeder
> Suchalgorithmus hat dieselbe Komplexität.

Eben. Der Begriff der Komplexität ist halt nur für nicht-konstante
Daten sinnvoll, und sobald man natürlich Parameter einführt ("k aus n"
o.ä.), haben Baum-basierte Algorithmen eben nicht mehr - wie von Dir
behauptet - konstante Komplexität.

>> Dann hat sie nämlich eine Länge von 49!/43! bzw. 49^6
>> (falls Du sogar doppelte Zahlen erlauben wolltest),
>
> Will ich nicht, wie aus meinm Beispiel hervorgeht.

Also der erste Fall: Ziehen von 6 aus 49 ohne Zurücklegen
*mit* Berücksichtigung der Reihenfolge hat 49*…*44 = 49!/43!
Möglichkeiten. (Bei doppelten Zahlen wären es sogar 49^6).

Wenn Du die "falsch" geordneten Kombinationen (bzw. zusätzlich
die Kombinationen mit Doppelten) nicht *vorher* aus Deiner
Tabelle entfernst, ist das die Länge der Tabelle und damit
die maximal nötige Zahl zur Übertragung, falls Du diese Tabelle
als Grundlage der Codierung benutzt.

>> wären die codierten Daten in beiden Fällen 34 Bit lang
>
> Wie kommst Du darauf?

log_2(49!/43!) bzw. log_2(49^6) = 6 log_2(6)
haben aufgerundet beide den Wert 34.

[Martin Vaeth]

Martin Vaeth <mar...@mvath.de> schrieb:

So viele Typos hatte ich hoffentlich noch nie in einem Posting.
Ich korrigiere nur ein paar Stellen, bei der ein Typo die Aussage
in ihr Gegenteil verkehrt oder ganz unverständlich gemacht hat.

> [...] sondern wie effizient es ist.

> Bei Bitmaske und reinen Zahlen das eben genau *nicht* ineffizient,

gemeint war: "*nicht* effizient"

> Eben. Der Begriff der Komplexität ist halt nur für nicht-konstante
> Daten sinnvoll, und sobald man natürlich Parameter einführt

gemeint war: "natürlich_e_ Parameter"

> log_2(49!/43!) bzw. log_2(49^6) = 6 log_2(6)

gemeint war: "= 6 log_2(49)"

[Fritz Feldhase]

On Sunday, December 4, 2022 at 12:47:07 AM UTC+1, Thomas 'PointedEars' Lahn wrote:

> > Ich zähle so:
> >
> > 0 : 1 2 3 4 5 6
> > 1 : 1 2 3 4 5 7
> > 2 : 1 2 3 4 5 8
> > 3 : 1 2 3 4 5 9
> > 4 : 1 2 3 4 5 10
> > 5 : 1 2 3 4 5 11
> > 6 : 1 2 3 4 5 12
> > …
> > 43 : 1 2 3 4 5 49
> > 44 : 1 2 3 4 6 7
> > :
> > 13983815 : 49 48 47 46 45 44
> >

> > Komme also auf die gleich Anzahl an Lottoergebnissen (13983816 [korr.]), aber OHNE

> > dass in meiner Tabelle welche doppelt auftreten.
> >
> Ja. Dann geht aber die Information über die Ziehungsreihenfolge verloren.

Ja. Wie schon erwähnt, spielt diese beim "Lotto_ergebnis_" keine Rolle.

Siehe: https://www.lotterie.de/Lotto/lottoergebnisse/zq_lotto.jsp

Hier geht es offenbar lediglich um die "Gewinnzahlen".