Az összes n hosszú 0-1 sorozat generálása a lehető leghatékonyabban? (JAVA)
for (int i = 0; i < (int) Math.pow(2, n); i++) {
if (Integer.toBinaryString(i).length() == n) {
System.out.println(Integer.toBinaryString(i));
char[] numbersCharArray2 = Integer.toBinaryString(i).toCharArray();
StringBuilder sb = new StringBuilder();
for (int j = 0; j < numbersCharArray2.length; j++) {
if (numbersCharArray2[j] == '0') {
numbersCharArray2[j] = '1';
} else {
numbersCharArray2[j] = '0';
}
sb.append(numbersCharArray2[j]);
}
System.out.println(sb.toString());
}
Jelenleg így csinálom. Ez viszont n=21 esetén már 17 másodperc, n=22 esetén pedig ezt írja: Exception: java.lang.OutOfMemoryError thrown from the UncaughtExceptionHandler in thread "main".
válasza:Tesztelted a kódot? N=2-re jó eredményt ad? Annyi sort, amennyit kell?
Nekem ami fura:
Minek a belső ciklus a manuális állítgatással, mikor az i++ és a binaryString konverzió már megadja az összes permutációt?
válasza: válasza:Én így csinálnám:
for(int i = 0; i < (int) Math.pow(2, n); i++)
System.out.println(StringUtils.leftPad(Integer.toBinaryString(i), n, '0'));
A te megoldásodon sokat dobna többek között ha észrevennéd azt hogy a
for (int i = (int) Math.pow(2, n)/2; i < (int) Math.pow(2, n); i++)
adja vissza az n hosszúságú számokat.
válasza:Bináris fában nem lehetne valahogy tárolni?:D
Kezdődne a bináris fa 0-val (oké, egyes is kell, akkor az csak plussz egy kiírás...), aztán lenne két ága: 0-1
0
|\
1_0
esetén.
0,1*,
01, 11*, 00, 10*
*: ugye első helyen nemcsak nulla állhat, így kiírjuk 1-el is. Ugye nem kellé tárolni az összest, csak kiíratni?
De hogy ez mennyire jó ötlet, azt nem tudom.
4. válaszoló:
A te megoldásod nem fut le, ellenben az ötleted az én megoldásomhoz nagyon jó, minimálisan de hatékonyabb lett nagy n esetén.
5. válaszoló:
Tárolni kell, csak ez egyszerűség kedvéért írtam így ki.
Egyébként azóta találtam egy másik módszert, ennek is
kb ennyi a futási ideje, szóval nem tudom van-e hatékonyabb az ennél.
int n = arrayForTesting[0].length();
for (long k = 0; k < Math.pow(2, n); k++) {
StringBuilder sb = new StringBuilder();
for (int i = n - 1; i >= 0; sb.append((k >>> i--) & 1));
System.out.println(sb.toString());
}
válasza:
válasza:String permutation = new String('0', n);
Console.WriteLine(permutation);
for (int i = 0; i < n; ++i)
{
for (int j = i; j < n; ++j)
{
Console.WriteLine(permutation.Remove(j, 1).Insert(j, "1"));
}
permutation = permutation.Insert(0, "1").Remove(permutation.Length);
}
1. válaszoló:
A külső ciklus nem adja meg az összeset, csak 2^n/2 darabot, ezért kell a belső ciklus, mert a "fordítottaival" lesz meg összes. Próbáld ki nyugodtan.
válasza:#1 vagyok
Tfh. N=3
0 =< i < 2^3=8
i=0: 000
i=1: 001
i=2: 010
i=3: 011
i=4: 100
i=5: 101
i=6: 110
i=7: 111
Sz.v.sz. minden tükörkép és minden permutáció megvan benne mindenféle hókipóki nélkül, csak binárissá konvertálással. :) De mondj kimaradt permutációt nyugodtan. :)
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!