Hallo,

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" <usenet*heinzi.at> schrieb im Newsbeitrag
news:87d461d0w6.fsf*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?

"Oliver Benning" <oliver*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?

Ja, und zwar nach dem Verfahren, daß man auch sonst benutzt,
um Numerale zwischen verschiedenen Stellenwertsystemen
umzurechnen.

Die Frage nach einem Zählverfahren - sogar für einen etwas
allgemeineren Fall - hatte ich kürzlich in einer anderen
Gruppe so beantwortet:

Dominic <annoyingmouse*gmail.com> writes:
>+-+-+-+ Possible: abc, abC, abz, abZ, aBc, aBC, aBz, aBZ,
>|a|b|c| ayc, ayC, ayz, ayZ, aYc, aYC, aYz, aYZ,
>+-+-+-+ Abc, AbC, Abz, AbZ, ABc, ABC, ABz, ABZ,
>|A|B|C| Ayc, AyC, Ayz, AyZ, AYc, AYC, AYz, AYZ,
>+-+-+-+ xbc, xbC, xbz, xbZ, xBc, xBC, xBz, xBZ,
>|x|y|z| xyc, xyC, xyz, xyZ, xYc, xYC, xYz, xYZ,
>+-+-+-+ Xbc, XbC, Xbz, XbZ, XBc, XBC, XBz, XBZ,
>|X|Y|Z| Xyc, XyC, Xyz, XyZ, XYc, XYC, XYz, XYZ
>+-+-+-+ 16 * 4 = 64 possibles

Source code to generate this is available from:

http://www.purl.org/stefan_ram/java/Count.java

The main method and the output is:

public class Count
{
public static void main( final java.lang.String[] args )
{
{ final Digit<java.lang.Character> digit
= new Digit<java.lang.Character>
( new java.lang.Character[]{ 'a', 'A', 'x', 'X' });

final Digit<java.lang.Character> digit1
= new Digit<java.lang.Character>
( new java.lang.Character[]{ 'b', 'B', 'y', 'Y' });

final Digit<java.lang.Character> digit2
= new Digit<java.lang.Character>
( new java.lang.Character[]{ 'c', 'C', 'z', 'Z' });

final Numeral numeral
= new Numeral
( new ResetableAdvanceableValue[]{ digit2, digit1, digit });

int i = 0;
do { java.lang.System.out.printf( "%2d:%s, ", i++, numeral ); }
while( numeral.advance() ); }}}

0:[a, b, c], 1:[a, b, C], 2:[a, b, z], 3:[a, b, Z], 4:[a, B, c], 5:[a, B,
C], 6:[a, B, z], 7:[a, B, Z], 8:[a, y, c], 9:[a, y, C], 10:[a, y, z], 11:[a,
y, Z], 12:[a, Y, c], 13:[a, Y, C], 14:[a, Y, z], 15:[a, Y, Z], 16:[A, b, c], 17
:[A, b, C], 18:[A, b, z], 19:[A, b, Z], 20:[A, B, c], 21:[A, B, C], 22:[A, B, z]
, 23:[A, B, Z], 24:[A, y, c], 25:[A, y, C], 26:[A, y, z], 27:[A, y, Z], 28:[A, Y
, c], 29:[A, Y, C], 30:[A, Y, z], 31:[A, Y, Z], 32:[x, b, c], 33:[x, b, C], 34:[
x, b, z], 35:[x, b, Z], 36:[x, B, c], 37:[x, B, C], 38:[x, B, z], 39:[x, B, Z],
40:[x, y, c], 41:[x, y, C], 42:[x, y, z], 43:[x, y, Z], 44:[x, Y, c], 45:[x, Y,
C], 46:[x, Y, z], 47:[x, Y, Z], 48:[X, b, c], 49:[X, b, C], 50:[X, b, z], 51:[X,
b, Z], 52:[X, B, c], 53:[X, B, C], 54:[X, B, z], 55:[X, B, Z], 56:[X, y, c], 57
:[X, y, C], 58:[X, y, z], 59:[X, y, Z], 60:[X, Y, c], 61:[X, Y, C], 62:[X, Y, z]
, 63:[X, Y, Z],

Hi!

"Oliver Benning" <oliver*treibhaus.ping.de> writes:
> "Heinrich Moser" <usenet*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/Oktalsy..._Oktalz ahlen

LG,
Heinzi

"Stefan Ram" <ram*zedat.fu-berlin.de> schrieb im Newsbeitrag
news:Count-20090908163523*ram.dialup.fu-berlin.de...
> "Oliver Benning" <oliver*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?
>
> Ja, und zwar nach dem Verfahren, daß man auch sonst benutzt,
> 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?

"Oliver Benning" <oliver*treibhaus.ping.de> writes:
>"Stefan Ram" <ram*zedat.fu-berlin.de> schrieb im Newsbeitrag
>>Ja, und zwar nach dem Verfahren, daß man auch sonst benutzt,
>>um Numerale zwischen verschiedenen Stellenwertsystemen
>>umzurechnen.
>Wie heisst das Verfahren denn?

In Java heißt es beispielsweise
»java.lang.Integer.toString(int, int)«.

Quelltext:

http://www.docjar.com/html/api/java/...eger.java.html

>>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?

comp.lang.java.help