Kombinationsmöglichkeiten
Oliver Benning
wie f�lle ich ein Array mit vorgegebener L�nge n mit allen
Kombinationsm�glichkeiten der Werte aus einem weiteren Array? Die L�nge n
mu� erreicht werden.
Beispiel:
n ist 10
Das Werte-Array hat die Zahlen 1,2,3
Das Array soll dann nicht einfach folgende Kombinationen enthalten:
1,2,3
2,3,1
3,2,1
sondern die 10 (=n) Zeichen voll ausf�llen:
1111111111
2111111111
2211111111
2221111111
2222111111
...
1231111111
...
2311232311
..
usw.
Gibt es daf�r auch einen Algorithmus, bei der man mit der letzten generierte
Kombination die Generierung fortsetzen kann und nicht wieder beim Anfang
starten mu�?
Vielen Dank!
Oliver
Heinrich Moser
> wie f�lle ich ein Array mit vorgegebener L�nge n mit allen
> Kombinationsm�glichkeiten der Werte aus einem weiteren Array? Die
> L�nge n mu� erreicht werden.
>
> Beispiel:
>
> n ist 10
> Das Werte-Array hat die Zahlen 1,2,3
>
> Das Array soll dann nicht einfach folgende Kombinationen enthalten:
> 1,2,3
> 2,3,1
> 3,2,1
>
> sondern die 10 (=n) Zeichen voll ausf�llen:
> 1111111111
> 2111111111
> 2211111111
> 2221111111
>
> Gibt es daf�r auch einen Algorithmus, bei der man mit der letzten
> generierte Kombination die Generierung fortsetzen kann und nicht
> wieder beim Anfang starten mu�?
Wenn du die Arrays in folgender Reihenfolge erstellst
1111111111
1111111112
1111111113
1111111121
1111111122
1111111123
...
sollte der Algorithmus offensichtlich sein.
LG,
Heinzi
Oliver Benning
news:87d461d...@msgid.heinzi.at...
> Wenn du die Arrays in folgender Reihenfolge erstellst
>
> 1111111111
> 1111111112
> 1111111113
> 1111111121
> 1111111122
> 1111111123
> ...
> sollte der Algorithmus offensichtlich sein.
Ja, danke! Gehe ich richtig in der Annahme, da� da schnell gigantische Daten
zusammenkommen, wenn man z.B. n = 100 vorgibt und lediglich mit 0 und 1
f�llt, dann w�ren das schon 2 ^ 100 (=1267650600228229401496703205376)
Kombinationen?
Ich habe noch zwei Fragen dazu:
1. Nehmen wir mal an, ich f�lle nach Deinem Schema und habe dann irgendwann
folgende Kombination: 3213213213
Kann man jetzt direkt berechnen, um die wievielte Kombination es sich
handelt, ohne einen Z�hler (z++) mitlaufen zu lassen?
2. Kann man im Gegenzug aus dem Kombinations-Index die Kombination berechnen
(also direkt sagen: die Zahl an Stelle 6 ist 1111111123) und das nat�rlich
auch, ohne alles durchzugehen und dann einfach zu stoppen?
Heinrich Moser
"Oliver Benning" <oli...@treibhaus.ping.de> writes:
> "Heinrich Moser" <use...@heinzi.at> schrieb:
>> Wenn du die Arrays in folgender Reihenfolge erstellst
>>
>> 1111111111
>> 1111111112
>> 1111111113
>> 1111111121
>> 1111111122
>> 1111111123
>> ...
>> sollte der Algorithmus offensichtlich sein.
>
> Ja, danke! Gehe ich richtig in der Annahme, da� da schnell gigantische
> Daten zusammenkommen, wenn man z.B. n = 100 vorgibt und lediglich mit
> 0 und 1 f�llt, dann w�ren das schon 2 ^ 100
> (=1267650600228229401496703205376) Kombinationen?
Exakt. Dieses Ph�nomen wird auch als "kombinatorische Explosion"
bezeichnet.
> Ich habe noch zwei Fragen dazu:
>
> 1. Nehmen wir mal an, ich f�lle nach Deinem Schema und habe dann
> irgendwann folgende Kombination: 3213213213
> Kann man jetzt direkt berechnen, um die wievielte Kombination es sich
> handelt, ohne einen Z�hler (z++) mitlaufen zu lassen?
>
> 2. Kann man im Gegenzug aus dem Kombinations-Index die Kombination
> berechnen (also direkt sagen: die Zahl an Stelle 6 ist 1111111123) und
> das nat�rlich auch, ohne alles durchzugehen und dann einfach zu
> stoppen?
Wie Stefan schon angedeutet hat handelt es sich bei deinen "Arrays"
schlicht und einfach um die Darstellung einer Zahl in einem anderen
Stellenwertsystem; dein obiges Beispiel von 0 und 1 ergibt z.B. das
Bin�rsystem.
D.h. du willst eine Umwandlung vom Dezimalsystem in ein m-basiertes
System (und umgekehrt), wobei m die L�nge deines Werte-Arrays ist.
Hier findest du ein Beispiel f�r die Basis 8, das sich leicht
verallgemeinern lassen sollte:
http://de.wikipedia.org/wiki/Oktalsystem#Umwandlung_von_Dezimalzahlen_in_Oktalzahlen
LG,
Heinzi
Oliver Benning
news:Count-2009...@ram.dialup.fu-berlin.de...
> "Oliver Benning" <oli...@treibhaus.ping.de> writes:
>>1. Nehmen wir mal an, ich f�lle nach Deinem Schema und habe dann
>>irgendwann
>>folgende Kombination: 3213213213
>>Kann man jetzt direkt berechnen, um die wievielte Kombination es sich
>>handelt, ohne einen Z�hler (z++) mitlaufen zu lassen?
>
> um Numerale zwischen verschiedenen Stellenwertsystemen
> umzurechnen.
Wie heisst das Verfahren denn?
> Die Frage nach einem Z�hlverfahren - sogar f�r einen etwas
> allgemeineren Fall - hatte ich k�rzlich in einer anderen
> Gruppe so beantwortet:
In welcher Gruppe war das?