Java alles mit allem addieren? (sämtliche kombinationen)

[furryhamster]

Hi,

habe ganz viele zahlen. diese sollen in allen kombinationen addiert werden und das ergebnis zwischengespeichert werden.

Beispiel anhand 3 zahlen:
zahl1
zahl 1 + zahl 2
zahl 2 + zahl 3
zahl 1 + zahl 3
zahl 1 + zahl 2 + zahl 3

gibt es da eine möglichkeit?

 

[Killkrog]

Gleich tickt phil wieder aus ^^ Zurecht, jedoch...

gibt es da eine möglichkeit?

Ja! Sag uns doch mal bitte, wie dein Ansatz bis jetzt aussieht...

 

[roker002]

gibt es einen grund wieso du alles "addiren" willst und in aller möglichen kombinationen? ähm wie war nochmal der begriff für addition und substraktionsregeln? die unterliegen ja keiner reihenfolgen, solange diese alleine in der Gleichung stehen...

 

[kuddlmuddl]

http://de.wikipedia.org/wiki/Kommutativgesetz ^^

Klingt nach Rekursion, da man nicht weiß wie viele Zahlen es sind - aber ohne Ansatz gibts auch keinen code

 

[DasBoeseLebt]

Erstmal ist es tatsächlich egal, wie du addierst..

Wenn du das zwischen Ergebnis immer ausgeben willst, sieht es leicht anders aus mit allen möglichen Kombinationen. Oder sollen einfach immer nur zufällig 2 Zahlen addiert werden (eventuell dann als ,,gebraucht'' markiert werden?)

Und es ist eigentlich egal, wieviele Zahlen das sind. Jede Eingabe 1Feld mit in der ArrayListe(oder was anderes).. Einen String? Teilst du am Leerzeichen zu je einem Feld.

Wie oft du addieren musst, ist dann je nach Fall unterschiedlich ...

 

[furryhamster]

ist das Kommutativgesetz nicht für wahrscheinlichkeitsrechnung?

ich möchte gerne ein programm schreiben, welches die größe aller dateien (einzeln) in einem verzeichnis ausliest und mir dann sagt, welche dateien ich am besten auf eine dvd brennen soll, um möglichst auf 4,7gb zu kommen.

ansatz habe ich bisher keinen direkten da ich nicht weiß wie ich anfangen soll.
ich habe mir überlegt, dass ich zum einen die dateinamen in ein array werfe und in einem anderen die größen.
Das array mit den größen würde ich dann in einer foreach nutzen und mit sich selber addieren, wobei ich 2 gleiche größen außen vor lasse. um das ganze nicht so schwierig werden lasse, würde ich die schleife beenden, wenn das ergebnis zwischen 4650 und 4700 liegt

 

[Killkrog]

Oha, dann solltest du dich auf jeden Fall von der Permutationsgeschichte entfernen!
Zum einen sind auf der Festplatte wahrscheinlich zu viele Dateien, als dass du ordentliche Laufzeiten hinkriegst, wenn du alle Permutationen ausrechnen willst, außerdem werden die dann auch viele doppelte Ergebnisse geben. zB f1+f17+f3 hat die selbe Größe wie f17+f1+f3.
Überleg dir mal, was für eine Genauigkeit dir wichtig ist. Sagen wir mal, dir sind 100mb mehr oder weniger scheiss egal, dann erzeugst du dir 47 Listen...
0-100mb -> Liste 1
101-200mb -> Liste 2
usw...

Wenn du die Listen erstellt hast, nimmst du so lange aus der letzten Liste (mit den größten Inhalten) Elemente, bis das nächste Element deine Grenze von 4700mb sprengen würde. Dann schaust du, ob du in der nächsten Liste was findest, usw, bis du ganz unten bist. Das setzt zwar vorraus, dass du von allen Dateigrößen möglichst gleichviele Dateien hast, sollte aber den Versuch wert sein.

Greetz,
Killy

 

[furryhamster]

ich will den algorithmus ja nicht über sämtliche dateien laufen lassen sondern nur auf einen ordner. dort befinden sich so im schnitt 20 - 70 Dateien welche etwa 500 - 1500mb groß sind.
die listenmethode erscheint mir daher auf dem ersten blick als nicht so sinnvoll, da die rechnung seeehr ungenau aufgeht und genau aus diesem grund will ich ja ein programm schreiben.

mir müssen auch gar nicht alle kombinationen auf einmal ausgegeben werden. hat er z.b. eine kombination in der größe von 4650 - 4700 mb errechnet, so kann das programm abbrechen. die dateien brenne ich dann und entferne sie aus dem ordner. dann würde ich das programm erneut starten.

permutation sehe ich gar nicht als so kritisch. bei 50 dateien hat man zwar grundsätzlich 3,04141E+64 möglichkeiten. da aber bei > 4700mb abgebrochen werden kann dürften es viel weniger möglichkeiten sein

 

[Killkrog]

Na, wenn dus unbedingt durchziehen willst...
Hab hier mal ein paar Codeschnippsel von mir gefunden, damit hab ich mal permutiert. Musst zwar ein bisschen anpassen, aber sollte in paar Minuten zu machen sein.

public static void main(String[] args) {
		permute(new int[]{1, 2, 3, 4, 5}, 0, 5);
	}

	private static void swap(int[] arr, int index1, int index2) {
		int t = arr[index1];
		arr[index1] = arr[index2];
		arr[index2] = t;
	}

	private static void rotateLeft(int[] arr, int start, int n) {
		int tmp = arr[start];
		for (int i = start; i < n - 1; i++) {
			arr[i] = arr[i + 1];
		}
		arr[n - 1] = tmp;
	}

	private static void permute(int[] v, int start, int n) {
		print(v, n);
		if (start < n) {
			int i, j;
			for (i = n - 2; i >= start; i--) {
				for (j = i + 1; j < n; j++) {
					swap(v, i, j);
					permute(v, i + 1, n);
				}
				rotateLeft(v, i, n);
			}
		}
	}

	public static void print(int[] v, int size) {
		if (v != null) {
			for (int i = 0; i < size; i++) {
				System.out.print(v[i]);
			}
			System.out.println();
		}
	}
}

Ich wäre dann wirklich gespannt, was Laufzeittests bei verschiedenen Inhalten angeht

 

[ice-breaker]

ich möchte gerne ein programm schreiben, welches die größe aller dateien (einzeln) in einem verzeichnis ausliest und mir dann sagt, welche dateien ich am besten auf eine dvd brennen soll, um möglichst auf 4,7gb zu kommen.

klingt stark nach dem Rucksackproblem, welches NP vollständig ist also nicht effizient lösbar.
Du wirst aber auf einige Ansätze die "halbwegs effizient" funktionieren.

 

[furryhamster]

danke killrog
dummerweise sind meine java kenntnisse stark eingerostet, sodass ich doch etwas länger zum überarbeiten gebraucht habe

folgendes habe ich nun:

	public static void print(int[] v, int size) {
		if (v != null) {
			int count = 0;
			int[] reihe  = new int[100];
			int arraysize = 0;
			for (int i = 0; i < size; i++) {
				
				if (count < 4700)
				{
					reihe[i] = v[i];
					count = count + v[i];
					if (count >= 4600 && count < 4700)
					{
						System.out.println("----" + count);
						
						for (int w : reihe) {if (w > 0){arraysize++;} }
						int[] anzeigen  = new int[arraysize];
						for (int t = 0; t < arraysize; t++){ anzeigen[t] = reihe[t]; }
						System.out.println(java.util.Arrays.toString(anzeigen));
						System.exit(0);
					}
				}
			}
			System.out.println();
		}

bis auf 50 mb genau sollte das ganze jetzt klappen. jetzt müsste ich die größe nur noch mit dem dateinamen in beziehung bringen. dies würde ich (heute nicht mehr ^^) lösen, indem ich die größen, womit ich die 4700mb erreiche mit den größen der datei vergleichen und bei übereinstimmung den dateinamen ausspucken. bestimmt auch nicht das effizienteste aber bei 100 dateien denke keine große sache

 

[Killkrog]

Bin gerade dabei, nochmal eine deutlich effektivere Methode rauszusuchen...

// Edit
Okay, vergiss es... Hab daran gedacht, ne Powerset zu machen, anstatt alle Permus, aber dabei bin ich an die Grenzen von Long gestoßen, zumindest bei meinem Ansatz, der aber bei deinen 70 Dateien (> 63) in die Knie geht. Schade...

 

[DasBoeseLebt]

Das ist doch eigentlich nur ein hBacktracking-Problem, welches solange läuft, bis er die beste Kombination unter 4,7Gb, aber auch am nähsten dran, gefunden hat. Hier sogar relativ einfach umzusetzen,..

edit: ich sehe gerade, es wurde das Rucksackproblem schon angesprochen ;(

 

[Killkrog]

Naja, Backtracking net unbedingt...
Hab nun doch noch was gefunden.
Im Endeffekt baust dir die Potenzmenge deines Arrays auf, gehst alles durch und speicherst jeweils die Teilmenge, die den größten möglichen Platz verbraucht.

 

[convexus]

mit Backtracking erreichst du das gleiche, nur schneller. Solltest du dir unbedingt mal anschauen. Mit den Potenzmengenansatz könnte es etwas länger dauern, die Potenzmenge zu n-Elementen enthält nämlich 2^n Teilmengen.

Ergänzung (2. Dezember 2010)

ich habe mal ein kleines Python Skript geschrieben, welches einen Backtracking - Algorithmus nutzt. Bin aber noch Laie in der Python Programmierung.

def find_solution(sum, files, size):
    global found_solution
    global bag
    if not found_solution and sum <= size and size - sum < 4:
        print "Loesung"
        found_solution = True
        for part in files:
            if part < 0:
                bag.append(-part)
    elif not found_solution:
        n = len(files)
        for i in range(0, n):
            f = files[i]
            if f > 0 and sum+f <= size:
                files[i] = -files[i]
                find_solution(sum+f, files, size)
                files[i] = -files[i]
          
if __name__ == '__main__':
    found_solution = False
    bag = []
    files = [10, 20, 1, 2, 3, 4, 9, 19, 11, 15, 18, 33, 44, 33, 22, 11, 9, 9, 89, 99, 2]

    while True:
        bag = []
        found_solution = False
        find_solution(0, files, 100)
        if len(bag) != 0:
            for part in bag:
                print part
                files.remove(part)
        else:
            break
            
    print "Rest ist:"
    for part in files:
        print part

 

[Limit]

Ich denke, was du suchst ist weniger eine Lösung des Rucksack-Problems als mehr eines des Behälterproblems. Auf der Wiki-Seite ist auch ein grundsätzlicher approximierender Lösungsansatz.

Ich habe spaßeshalber den Algorithmus aus dem Wikipedia-Artikel in Python implementiert. Er scheint ganz gut zu funktionieren.

import os
import sys

directory = sys.argv[1]
max_bin_size = int(sys.argv[2])

# creates a list of tuples (filename, filesize)
def create_filelist(start_path):
	filelist = []
	for root, dirs, files in os.walk(start_path):
	    for name in files:
		path = os.path.join(root, name)
		filelist.append((path, os.stat(path)[6]))
	return filelist

# calculates the size of the files in a certain bin
def get_bin_size(bin):
	return sum(map(lambda x: x[1], bin))

files = create_filelist(directory)
files.sort(key=lambda x: x[1]) # files are sorted by filesize

bins = []

while(True):
	try:
		f = files.pop()
	except:
		break
	
	for b in bins:
		if f[1] > max_bin_size - get_bin_size(b):
			continue
		else:
			b.append(f)
			break
	else:
		new_bin = [f]
		bins.append(new_bin)

for b in bins:
	print(b)

 

[furryhamster]

so habe jetzt trotz aller bedenken auf die permutation aufgebaut und das programm zuende geschrieben.

habe es spaßeshalber mal für 664 Dateien durchlaufen lassen. Zumindest bei mir hat er keine Sekunde gebraucht zum anzeigen.

was mich wundert: habe die größe und den dateinamen immer in einer hashmap gespeichert. wenn ich mein verzeichnis einlese gibt mir lengh (von array) 664 elemente an. wenn ich size bei meiner hashmap anwende, kriege ich aber nur 630 elemente... wie kann das sein?

Edit: mhh scheint doch noch nicht zu laufen.... sobald ich der permuationsmethode als maxwert 37 übergebe scheint er immer nur die gleichen zusammenzurechnen und gerät daher in eine endlosschleife..

Edit2: mhh es scheint als habe ich einen denkfehler bei meiner abbruchbedingung gemacht. kann ich irgendwie angeben, dass er wenn eine abbruchbedingung in der print() anweisung erfüllt ist an einer anderen stelle der schleife in der methode permute() springt?