Archiv verlassen und diese Seite im Standarddesign anzeigen : [c++]3d array mit allen möglichkeiten füllen
ich habe ein aray a[4][4][4] die jeweiligen felder können entweder 1 oder 0 sein, es gibt 32 einsen und 32 nullen und ich suche eine möglichkeit wie alle möglichen keiten einmal in das array rein geschrieben bekomme.
Quasi: array füllen, analysieren, neu füllen, und somit quasi alle möglichkeiten einmal durch gehe.
Du bist dir im klaren darüber, dass du damit 1832624140942590534 Möglichkeiten durchgehen willst?
hab doch noch 60 Jahre vor mir bis ich sterbe :biggrin:
Das reicht nicht wenn ich es richtig überschlagen hab ;)
Baalzamon
2006-02-23, 10:36:03
ich habe ein aray a[4][4][4] die jeweiligen felder können entweder 1 oder 0 sein, es gibt 32 einsen und 32 nullen und ich suche eine möglichkeit wie alle möglichen keiten einmal in das array rein geschrieben bekomme.
Quasi: array füllen, analysieren, neu füllen, und somit quasi alle möglichkeiten einmal durch gehe.
Keine Ahnung ob ich dich richtig verstehe, aber das wäre dann doch einfach eine dreifach geschachtelte for-Schleife, jeweils mit Bit-weiser +1 Addtion oder nicht?
Damit kannst du dann einfach alle Möglichkeiten durchlaufen.
Pseudocode:
for (int x=0; x < 32; x++) {
for (int y=0; y < 32; y++) {
for (int z=0; z < 32; z++) {
a[][][0] = bitwise +1
}
a[][0][] = bitwise +1
}
a[0][][] = bitwise +1
}
Natürlich muss die bitwise Operation so gestaltet sein, das der Übertrag auf den nächsten Array-Eintrag überspringt. Also ein Volladdierer mit Übertrag.
Für a[0]=1 + (bw+1) => a[0]=0 =>a[1]=1 usw.
Kleine Tabelle dazu?
0000 +1
0001 +1
0010 +1
0011 +1
0100 +1 usw.
Somit hast du durch einfaches Abzählen alle Möglichkeiten durchprobiert. Wenn es nicht das ist was du möchtest, ignoriere meinen Beitrag geflissentlich. ;)
Baalzamon
2006-02-23, 10:55:41
Das reicht nicht wenn ich es richtig überschlagen hab ;)
Wenn ich es richtig überschlage habe braucht ein 2Ghz Rechner für die Anzahl an Möglichkeiten die Xmas gepostet hat knapp 30 Jahre. Dann hat er ja noch 30 Jahre Zeit das Ergebnis zu analysieren. ;D
Kleine Verständnisfrage am Rande: Warum sollten das soviele Möglichkeiten sein wie Xmas angegeben hat? Bin ich gerade nur zu blöd oder sollte es nicht einfach 32*32*32 = 32768 Möglichkeiten geben?
Juerg
2006-02-23, 11:23:30
Vielleicht hilft Dir das weiter:
Permutationen eine kubischen Arrays
http://www.google.ch/search?hl=de&q=Permutationen+eine+kubischen+Arrays&spell=1
permutation of cubical arrays
http://www.google.ch/search?hl=de&q=permutation+of+cubical+arrays&meta=
Nachtrag: Ich würde ebenfalls vorschlagen das Array "ein wenig" kleiner zu gestalten. Es hilft ungemein beim Überblicken der Lösung ;).
Neomi
2006-02-23, 13:05:02
Wenn ich es richtig überschlage habe braucht ein 2Ghz Rechner für die Anzahl an Möglichkeiten die Xmas gepostet hat knapp 30 Jahre. Dann hat er ja noch 30 Jahre Zeit das Ergebnis zu analysieren. ;D
Du willst also ein Array mit 64 (4^3) Elementen passend mit Werten belegen und analysieren (was auch immer das in dem Fall bedeutet) in nur einem einzigen Taktzyklus? Das halte ich für... sagen wir mal... "optimistisch". ;)
Kleine Verständnisfrage am Rande: Warum sollten das soviele Möglichkeiten sein wie Xmas angegeben hat? Bin ich gerade nur zu blöd oder sollte es nicht einfach 32*32*32 = 32768 Möglichkeiten geben?
4^3 Arrayelemente, also insgesamt 64, jedes davon entweder 0 oder 1, quasi 2 Möglichkeiten pro Element. Demnach gibt es 2^64 Möglichkeiten, das Array zu belegen. 18446744073709551616 ist schon die korrekte Zahl.
Wenn ich es richtig überschlage habe braucht ein 2Ghz Rechner für die Anzahl an Möglichkeiten die Xmas gepostet hat knapp 30 Jahre. Dann hat er ja noch 30 Jahre Zeit das Ergebnis zu analysieren. ;D1832624140942590534 * x / 2Ghz = 916312070s * x = ~29 Jahre * x
Wobei x der Takt-Faktor ist der pro Möglichkeit gebraucht wird. Und das sind bestimmt auch an die 100.
Aber soweit ich den Threadstarter verstanden hab geht es nicht um alle beliebigen Kombinationen sondern nur um die wo 32 1en und 32 0en im Array stehen. Da müsste ich jetzt im Buch nachschauen wie man da die Anzahl der Möglichkeiten ausrechnet...
Es gibt 4*4*4=64 Einträge und jeder kann 0 oder 1 sein: 2^64 Möglichkeiten.
Ah, nein dass ist nicht richtig, du brauchst ja genau 32 1 und 32 0. Dann ist es "64 über 32"=1832624140942590534 weil man die 32 Stellen aus den 64 Stellen wählt an denen man die Einsen plaziert.
Ah ok, dann stimmt das was XMas gepostet hat :)
Baalzamon
2006-02-23, 13:21:43
@Trap
danke, 64 über 32 verstehe ich doch direkt. :) Dann ist auch die Anzahl der Möglichkeiten klar.
@Coda & Neomi
Natürlich war das ziemlich optimistisch, deswegen ja auch der ;D. Wenn man aber 'nur' vom setzen der einzelnen Bits ausgeht,bzw. +1 in einem Volladdierer, ist ein Taktzyklus doch realistisch (Rechnerstruktur ist schon so lange her ;))? Das man für Nachfolgeoperationen (oder Analyse-Funktionen) länger braucht ist klar.
Edit: Habe jetzt auch erst gelesen das der Threadstarter ja genau 32 0en und 32 1en haben will. :bonk: Ich sollte mich an meine Signatur halten.
Interessant wird die Frage mit kleineren Grenzen:
Was ist ein effizienter Algorithmus um alle Permutationen mit 16 1en und 16 0en zu erzeugen?
Ich hab vor nem halben Jahr mal einen 5-Zeiler gesehen der das mit Arithmetik macht, aber leider wieder vergessen.
Juerg
2006-02-23, 13:27:14
Mit einem Quad-DC-Opteron gehts dann nur noch 32:8 ~ 30 Jahre : 8 Cores = 4 Jahre. Vorausgesetzt, dass dies keine stochastische Verteilung ist, kann dann mit einem klize-kleinen Hint wo im Raum die Lösung sein könnte, innert Tagen oder sogar Stunden daran sein.
Neomi
2006-02-23, 13:40:56
Interessant wird die Frage mit kleineren Grenzen:
Was ist ein effizienter Algorithmus um alle Permutationen mit 16 1en und 16 0en zu erzeugen?
int iLiniar [32];
void Analyze ()
{
// analyze iLinear
return;
}
void Permutate (int iZeroesLeft, int iOnesLeft)
{
int iPos = iZeroesLeft + iOnesLeft - 1;
if (iPos >= 0)
{
if (iZeroesLeft > 0)
{
iLinear [iPos] = 0;
Permutate (iZeroesLeft - 1, iOnesLeft);
}
if (iOnesLeft > 0)
{
iLinear [iPos] = 1;
Permutate (iZeroesLeft, iOnesLeft - 1);
}
}
else
Analyze ();
return;
}
Dann einfach Permutate (16, 16); aufrufen. Rekursion ist doch was schönes. Mit Arithmetik geht das natürlich ebenfalls, dann shiftet man eben ein paar Bits durch die Gegend.
Ja, die Lösung ist nett.
Die Lösung die ich meine hat zusätzlich noch die Lösungen in aufsteigender Reihenfolge erzeugt: (0011, 0101, 0110, 1001, 1010, 1100).
Hab die Lösung wieder aufgetrieben:
unsigned snoob(unsigned x) {
unsigned smallest, ripple, ones;
// x = xxx0 1111 0000
smallest = x & -x; // 0000 0001 0000
ripple = x + smallest; // xxx1 0000 0000
ones = x ^ ripple; // 0001 1111 0000
ones = (ones >> 2)/smallest; // 0000 0000 0111
return ripple | ones; // xxx1 0000 0111
}
Pinoccio
2006-02-23, 20:23:50
Das reicht nicht wenn ich es richtig überschlagen hab ;)2^64 mögliche Belegungen testen? Sollte reichen. Vorrausgesetzt, er wechselt zwischendurch auf neuere Modelle und die Analyse dauert nicht alnge.
mfg Sebastian
Naja mit x-Core CPUs wird er es wohl irgendwann schon schaffen, da hast du recht.
man könnte die mögliche keiten noch etwas minimieren, eigentlich ist es das array ein 3d gebilde und es wäre egal ob das ganze auf dem kopfsteht oder um 90° gedreht ist usw, aber ich glaube das würde die maximale zeit auch nur 6teln(??). und sicher das das 2^64 fälle sind, weil die anzahl der 1 und 0 bleibt immer gleich.
Ne es sind 64 über 32 Möglichkeiten. XMas hat es schon richtig gerechnet.
Spiegeln und Drehen ändert nix am Ergebnis der Analyse? Das bringt schonmal ne ganze Menge. Sonst noch irgendwas das man machen kann ohne das Ergebnis zu verändern?
Welche Art von Spiegelungen? Auch Spiegelungen an Ebenen diagonal durch den Würfel?
Die 2^64 ist falsch, 64 über 32 ist richtig für dumm alles durchprobieren.
Vielleicht wäre es mal nicht schlecht überhaupt zu erörtern was für ein Problem sich stellt.
hoffentlich schlägt man mich jetzt nicht, wollte bruteforce mäßig die maximale anzahl von vollständigen reihen eines 3d viergewinnt(feld ist 4x4x4 große mit jeweils 32 weißen und 32 roten steinen) berechnen :biggrin: ,jaja die lange weile in den semsterferien.
Hm. Es kann doch auch schon unter 64 Steinen zu einem Sieg kommen, oder nicht?
Hm. Es kann doch auch schon unter 64 Steinen zu einem Sieg kommen, oder nicht?
es wird weiter gespielt wer am ende die meißten hat, hat gewonnen. und um diese fertigen reihen geht es mir.
Aus dem Kopf: 23
Niedrigstes Spiel 0:0, höchstes Spiel 20:20, höchster Sieg 23:1
vBulletin®, Copyright ©2000-2024, Jelsoft Enterprises Ltd.