Kombinationen bilden, Algorithmus?

Also die Reihenfolge der Elemente ist egal, hauptsache das alle Kombinationen erfasst werden und die Kombinationen nur einmal auftauchen.

1. loop. länge so lang erhöhen bis arraylänge.
2. loop. position sonlange erhöhen, wie pos + länge in array

hä? wie soll das gehen mit zwei schleifen?

stimmt, müssten 3 sein, aber dann wäre 98 76 doch nicht dabei

Hat sonst niemand eine Idee?
Das Problem ist doch nicht neu, wo sind die Freaks?

is ja gnaz einfach
binär

int[] arry = {98, 56, 76};
for(int i = 0; i<Math.pow(2,arry.length); i++) {
	for(int len = 0; len<arry.length; len++) {
		int mask = 1<<len;
		if((i & mask) != 0)  {
			System.out.print(arry[len]+ ",");
		}
	}
	System.out.println();
}

Danke Dir, aber wie kann das gehen, ich checke das noch nicht, muss wohl noch ein Weilchen darüber nachdenken.

schreib dir die zahlen 0 bis 7 binär auf

for(int i = 0; i<Math.pow(2,arry.length); i++) {

Das ist ja grausam!

das wird bestimmt nen c++ vs java benchmark damit c++ wieder schneller wird

Javaner42 schrieb:

for(int i = 0; i<Math.pow(2,arry.length); i++) {

Das ist ja grausam!

is nur zum zeigen wie es geht.

naja, zu zeigen wie es geht ... du machst aus einer O(2^n) ne O(n*2^n) komplexität.

SG1

Viel schlimmer: Math.pow gibt 'ne Fliesskommazahl zurueck. Dafuer gibt's <<.

ja ja, man macht einfach die "komplizierte" Berechnung vor der Schleife, weil das Ergebnis immer gleich ist.

Ich würde aber vom Gefühl her sagen, dass es eine andere Stelle gibt, an der man dieses "Programm" mehr optimieren kann. n kann ja auch nicht so groß werden, weil dann int nicht mehr reicht.

So hier nochmal nach gemessen
Original

StringBuffer buffer = new StringBuffer();
		int[] arry = {98, 56, 76, 55, 12, 100, 333, 777, 1236, 9999, 76543, 1, 99999};
		long start = System.currentTimeMillis();
		for(int i = 0; i<Math.pow(2,arry.length); i++) {
			for(int len = 0; len<arry.length; len++) {
				int mask = 1<<len;
				if((i & mask) != 0)  {
//					buffer.append(arry[len]+ ",");
					System.out.print(arry[len]+ ",");
				}
			}
			System.out.println();
//			buffer.append('\n');
		}
//		System.out.println(buffer.toString());
		long end = System.currentTimeMillis();
		System.out.println("time: " + (end-start));

...
98,76,55,12,100,333,777,1236,9999,76543,1,99999,
56,76,55,12,100,333,777,1236,9999,76543,1,99999,
98,56,76,55,12,100,333,777,1236,9999,76543,1,99999,
time: 1172

Eure "Optimierung"

StringBuffer buffer = new StringBuffer();
		int[] arry = {98, 56, 76, 55, 12, 100, 333, 777, 1236, 9999, 76543, 1, 99999};
		int pow = (int) Math.pow(2,arry.length);
		long start = System.currentTimeMillis();
		for(int i = 0; i<pow; i++) {
			for(int len = 0; len<arry.length; len++) {
				int mask = 1<<len;
				if((i & mask) != 0)  {
//					buffer.append(arry[len]+ ",");
					System.out.print(arry[len]+ ",");
				}
			}
			System.out.println();
//			buffer.append('\n');
		}
//		System.out.println(buffer.toString());
		long end = System.currentTimeMillis();
		System.out.println("time: " + (end-start));

...
98,76,55,12,100,333,777,1236,9999,76543,1,99999,
56,76,55,12,100,333,777,1236,9999,76543,1,99999,
98,56,76,55,12,100,333,777,1236,9999,76543,1,99999,
time: 1156

Besser Optimiert

StringBuffer buffer = new StringBuffer();
		int[] arry = {98, 56, 76, 55, 12, 100, 333, 777, 1236, 9999, 76543, 1, 99999};
		long start = System.currentTimeMillis();
		for(int i = 0; i<Math.pow(2,arry.length); i++) {
			for(int len = 0; len<arry.length; len++) {
				int mask = 1<<len;
				if((i & mask) != 0)  {
					buffer.append(arry[len]+ ",");
//					System.out.print(arry[len]+ ",");
				}
			}
//			System.out.println();
			buffer.append('\n');
		}
		System.out.println(buffer.toString());
		long end = System.currentTimeMillis();
		System.out.println("time: " + (end-start));

...
98,76,55,12,100,333,777,1236,9999,76543,1,99999,
56,76,55,12,100,333,777,1236,9999,76543,1,99999,
98,56,76,55,12,100,333,777,1236,9999,76543,1,99999,

time: 641

vonwegen

grenouille_unreg schrieb:

naja, zu zeigen wie es geht ... du machst aus einer O(2^n) ne O(n*2^n) komplexität.

Ist nicht immer so einfach wie es aussieht. Auf so einfache Sachen kommt oft schon der Compiler.

bin grad immer no am schmunzeln. verrate mir mal einen compiler, der mir z.b. aus einer quadritischen, eine lineare laufzeit macht.

ausserdem haben alle 3 hochoptimierten versionen ne laufzeit von O(n*2^n).

schoene gruesse

grenouille_unreg schrieb:

bin grad immer no am schmunzeln. verrate mir mal einen compiler, der mir z.b. aus einer quadritischen, eine lineare laufzeit macht.

Stell dich nicht so dumm. das Math.pow rausziehen kann der compiler, wenn er sieht, dass sich die array größe nicht ändert.

grenouille_unreg schrieb:

ausserdem haben alle 3 hochoptimierten versionen ne laufzeit von O(n*2^n).

Du hast wohl garnichts verstanden. Keiner von den 3 ist "hochoptimiert"
Aber dann zeigt doch mal wie du das Programm so optimierst, dass es von der angeblichen Laufzeit (n*2^n) auf O(2^n) kommt. Reproduzierbar und messbar als Code und nciht nur theoretisch!