# Partitionen der Länge x einer natürlichen Zahl n



## louis (7. Nov 2007)

Hallo Community,

ich benötige alle sog. "Partitionen der Länge x einer natürlichen Zahl n". Auf gut deutsch sind das alle möglichen Summenzerlegungen einer bestimmten Zahl, wobei auch die Null vorkommen darf. Kleines Beispiel:


```
n = 3, x = 4

Ergebnis:

3 0 0 0 
2 1 0 0 
2 0 1 0 
2 0 0 1 
1 2 0 0 
1 1 1 0 
1 1 0 1 
1 0 2 0 
1 0 1 1 
1 0 0 2 
0 3 0 0 
0 2 1 0 
0 2 0 1 
0 1 2 0 
0 1 1 1 
0 1 0 2 
0 0 3 0 
0 0 2 1 
0 0 1 2 
0 0 0 3
```

Zur Veranschaulichung kann man sich vorstellen, n Kugeln in x Urnen zu verteilen. Ich habe mir einen Algorithmus überlegt, der genau nach obigem Beispiel vorgeht. Zuerst werden alle Kugeln in die Urne ganz links gelegt, dann wird eine Kugel aus dieser Urne herausgenommen und in alle Urnen rechts davon gelegt. Dieser Vorgang wird rekursiv für alle Ergebnisse wiederholt:





```
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class Partitioner implements Iterator<int[]> {
	
	protected Queue<PartitionerState> queue;
	protected HashSet<PartitionerState> visitedStates;

	protected int balls;
	protected int buckets;

	public Partitioner( int balls, int buckets ) {
		queue = new LinkedList<PartitionerState>();
		visitedStates = new HashSet<PartitionerState>();
		
		this.balls = balls;
		this.buckets = buckets;
		
		//in the beginning all balls are in the most left bucket
		int[] start = new int[buckets];
		start[0] = balls;
		
		queue.offer( new PartitionerState(start) );
	}

	public boolean hasNext() {
		return ! queue.isEmpty();
	}

	public int[] next() {
		return enqueue();
	}

	public void remove() {
		throw new IllegalArgumentException("method remove() not implemented");
	}

	private int[] enqueue() {
		
		PartitionerState state = null;
		if (!queue.isEmpty()) {
			state = queue.poll();
			//get first bucket not zero
			int i=0;
			for (; i<state.buckets.length; i++) {
				if (state.buckets[i]>0)
					break;
			}
			//take a ball from the found bucket and put it in every 
			//bucket right hand to this one
			for (int j=i; j<buckets; j++) {
				int[] tempBucket = (int[]) state.buckets.clone();
				tempBucket[i] -= 1;
				if (j+1<tempBucket.length) {
					tempBucket[j+1] += 1;
					PartitionerState newState = new PartitionerState(tempBucket);
					if ( !visitedStates.contains(newState) ) {
						queue.offer(newState);
						visitedStates.add(newState);
				    }
				}
			}
		}
		
		return state.buckets;
	}
	
	public static void main( String[] args ) throws Exception {
	    
		int maxBalls = 15;
		int maxBuckets = 15;
		for (int balls=1; balls <= maxBalls; balls++) {
			for (int buckets = 1; buckets <= maxBuckets; buckets++) {
				System.out.print(balls + " balls in " + buckets + " buckets: ");
				Partitioner p = new Partitioner(balls, buckets);
				long start = System.currentTimeMillis(); 
				int i=0;
				while ( p.hasNext() ) {
					int[] partition = (int[]) p.next();
					i++;
			    }
			    long diff = System.currentTimeMillis() - start; 
			    System.out.println(i + " partitions, duration: " + diff + " ms");
			}
		}
	}
}	

class PartitionerState {

	protected int[] buckets;

	public PartitionerState( int[] buckets ) {
		this.buckets = buckets;
	}

	public boolean equals( Object other ) {
		PartitionerState s = (PartitionerState) other;
		for( int i=0; i<this.buckets.length; i++ ) {
			if ( this.buckets[i] != s.buckets[i] ) {
				return false;
			}
		}
		return true;
	}

	public int hashCode() {
		int hash = 0;
		int m = 1;
		for( int i=0; i<buckets.length; i++ ) {
			hash += m * buckets[i];
			m *= 2;
		}
		return hash;
	}
}
```

Hinweis: das Programm sollte mit den Optionen -Xms512m -Xmx512m gestartet werden, es benötigt ein bisschen Speicher :shock: 

Um Dubletten zu erkennen benutze ich ein HashSet, in dem ich mir alle bereits vorgekommenen Kombinationen merke. Ansonsten ist der Code denke ich selbsterklärend.

Wenn man das Programm mal laufen lässt, erkennt man mein Problem...bei größeren Zahlenkombinationen wird das ganze recht zäh. Das Kernproblem liegt meiner Ansicht nach klar auf der Hand...bei größeren Kombinationen Kugeln / Urnen wird das Hashset recht groß, und die Lookups dauern ihre Zeit. 

Wie könnte ich den Algorithmus noch tunen??? An der hashCode Methode schrauben? In der Doku steht, ein HashSet sei bei einer eindeutigen Hashfunktion am schnellsten, allerdings sollte die Hashfunktion auch schnell sein. Lohnt es sich, da noch mehr zu experimentieren?

Oder bin ich auf dem völlig falschen Dampfer und es gibt eine performantere und speichersparendere Art und Weise, die Dubletten zu vermeiden?

Des weiteren bin ich etwas verwundert über die Speicherfreigabe. Das Programm nimmt sich ziemlich schnell die 512 MB Speicher und dümpelt dann an dieser Obergrenze rum. Ich habe den Eindruck, der Speicher wird sehr selten freigegeben. gc ist ja ein Thema für sich, Java macht das lieber selbst. Eigentlich sollte ja nach jedem Schleifendurchlauf das alte Partitioner-Objekt nicht mehr referenziert werden, der Speicher könnte wieder freigegeben werden. Ist aber anscheinend nicht wirklich so...Kann ich da auch noch was optimieren?


Ich bin für jederlei Anregung offen...danke schonmal für die Mühe...

Grüße Louis


----------



## Wildcard (7. Nov 2007)

Geht doch viel einfacher:
Zähl einfach zur Basis n, x gibt dir die maximalen Stellen an. Jede Zahl ist eine automatisch eine gültige, einzigartige Kombination.


> Des weiteren bin ich etwas verwundert über die Speicherfreigabe. Das Programm nimmt sich ziemlich schnell die 512 MB Speicher und dümpelt dann an dieser Obergrenze rum. Ich habe den Eindruck, der Speicher wird sehr selten freigegeben. gc ist ja ein Thema für sich, Java macht das lieber selbst. Eigentlich sollte ja nach jedem Schleifendurchlauf das alte Partitioner-Objekt nicht mehr referenziert werden, der Speicher könnte wieder freigegeben werden. Ist aber anscheinend nicht wirklich so...Kann ich da auch noch was optimieren?


Warum soll der GC aufräumen wenn 
1. Das Programm noch auf Volllast läuft
2. Der Speicher akutell nicht benötigt wird


----------



## Saxony (7. Nov 2007)

Hiho,

Anmerkung zur Methode PartitionerState#equals():

Als erstes würde ich die Arraygrenzen beider Arrays überprüfen.
Sollte nämlich die Länge von s.buckets kleiner der von this.buckets sein, gibts ne ArrayIndexOutBoundException.

Der cast ganz am Anfang sollte vielleicht mit einem if (other instanceof PartitionerState) eingeleitet werden.

Nur für den Fall, dass diese Methode jemals verwendet werden sollte. 

bye Saxony


----------



## SlaterB (7. Nov 2007)

> Auf gut deutsch sind das alle möglichen Summenzerlegungen einer bestimmten Zahl, wobei auch die Null vorkommen darf. 

deine Liste ist vollkommen gleichmäßig
3 0 0 0 
2 1 0 0 
...
0 0 1 2 
0 0 0 3 

was bedeuten denn die einzelnen Zeilen, eine Summe a la
3 0 0 0  = 3*0+0*1+0*2+0*3?
kommt doch nicht hin und wenn, dann würde das ganze nicht gleichmäßig aussehen,

und wieso ist die 0 erlaubt, die kann ja unendlich oft in der Sume vorkommen,
oder meinst du, es ist erlaubt, dass die 4 null mal vorkommt?

in jedem Fall solltest du höchstens paar Schleife brauchen und die Ergebnisse direkt ausgeben
oder die Ergebnisse gerne in einer Liste speichern,

mit Doppelten dürfte das alles nichts zu tun haben, lehne ich mich aus dem Fenster,
genauer drüber nachdenken tue ich erst, wenn du genau beschreibst, was gesucht ist (Beispiel!, falls das obige kein korrektes Beispiel ist),
und in ein paar Sätzen dein bisheriges Verfahren erklärst


----------



## Saxony (7. Nov 2007)

Hiho,

ich nochmal. 

Also unter diesem Link findest du eine kleine mathematishce Abhandlung zum Thema.
Auf den Seiten 8 und 9 findest du sogar etwas Pseudocode zur Vorgehensweise.
Berücksichtigt werden bei der Summenbildung nur die Faktoren, deren Produkt != 0 ist.

d.h

bei n = 5

3+1+1=n, es entfallen dinge wie 3+0+0+1+0+1 wenn k = 6 sein sollte.

Naja vielleicht hilft es ja.

bye Saxony


----------



## louis (7. Nov 2007)

Hallo zusammen,

erst mal vielen Dank für euere Beiträge...da sind viele interessante Aspekte dabei! 



> Geht doch viel einfacher:
> Zähl einfach zur Basis n, x gibt dir die maximalen Stellen an. Jede Zahl ist eine automatisch eine gültige, einzigartige Kombination.



 :shock: Clevere Idee! Da bin ich nicht draufgekommen...ich war irgendwie gedanklich bei Rekursion...das werde ich mal  ausprobieren...

Der Link von Saxony schaut auch vielversprechend aus! Leider ist das ganze mein privater Spass...mal schauen wann ich zeitlich wieder dazukomme.

Kurz zu dem Sinn und Zweck der Sache...ich habe einen automatischen Lösungsgenerator für sogenannte "Logicals" programmiert bzw. bin gerade am Feinschliff...prinzipiell laufen tut es schon. Vielleicht kennt jemand diese lustigen Rätselheftchen von PM, da gibt es auch eines mit Logicals...online gibts das ganze auch, z.B. unter www.janko.at/Raetsel/Nonograms/index.htm, dort heissen die Dinger Nonogramme.

Meine Idee war, zu jeder Reihe und Spalte alle möglichen Verteilungen der Blöcke zu berechnen und daraus dann schrittweise die Lösung zu ermitteln. Zur Berechnung der Verteilung der Blöcke brauche ich die Partitionen, damit ich die "Lücken" zwischen den Blöcken entsprechend füllen kann.

Wie gesagt, das ganze läuft schon, und es klappt auch...bei großen Rätseln (z.B. 50*60) dauert das ganze allerdings 'ne viertel Stunde oder so...das muss ich noch optimieren   

Danke schonmal an alle Helfer...vielleicht habt ihr noch mehr Anregungen

Grüße Louis


----------



## happy_robot (7. Nov 2007)

hi,

das hier macht das was du willst. braucht auch nur wenig speicher  


```
public class Test {

	public static void part(int base, int num) {
		base++;
		
		int max = (int)Math.pow(base, num);
		
		for(int n = 0; n < max; n++) {
			
			int value = n;
			String output = "";
			for(int numIndex = 1; numIndex <= num; numIndex++) {
				int divisor = (int)Math.pow(base, num-numIndex);
				int numValue = value / divisor;
				output = output + numValue;
				value = value - numValue * divisor;
			}
			System.out.println(output);
		}
	}
	
	public static void main(String[] args) {
		part(3,4);
	}
	
}
```


mfg


----------



## louis (7. Nov 2007)

```
hi,

das hier macht das was du willst. braucht auch nur wenig speicher
```

Cool...werde ich auch mal ausprobieren...Danke!

Allgemein muss ich sagen...tolles Forum!  :toll: 

Ciao Louis


----------



## Wildcard (7. Nov 2007)

Ja, das ist so in etwa was ich meinte, allerdings würde ich die Konvertierung Integer#toString überlassen.


----------



## Saxony (7. Nov 2007)

happy_robot hat gesagt.:
			
		

> das hier macht das was du willst. braucht auch nur wenig speicher



Yep jetzt müsen nur noch die Ergebnisse raus, deren Quersumme != n ist.

bye Saxony


----------



## happy_robot (7. Nov 2007)

oder so. das hier dürfte auch äusserst effizient sein. ohne rechnen (ausser simple addition):


```
public static void part(int base, int num) {
		char[] output = new char[num];
		for(int n = 0; n < output.length; n++) {
			output[n] = '0';
		}
		
		while(true) {
			for(int n = 0; n < num; n++) {
				if(output[n] < base+48) {
					output[n]++;
					break;
				} else {
					if(n == num-1) {
						return;
					} else {
						output[n] = '0';
					}
				}
			}
			System.out.println(output);
		}
	}
```

EDIT: für das ausfiltern der anzahl != n folgendes fragment statt der ausgabe einfügen:


```
int sum = 0;
			for(int n = 0; n < num; n++) {
				sum += output[n]-48;
			}		
			if(sum == base) {
				System.out.println(output);
			}
```

mfg


----------



## louis (8. Nov 2007)

Hallo,

soooo...ich habe jetzt mal ein bisschen getestet und mit ein wenig größeren Zahlen experimentiert...und bin zu folgendem Ergebnis gekommen. 

Hier das Ergebnis nach dem von happy_robot zuletzt vorgeschlagenen Algorithmus:


```
7 Kugeln in 7 Urnen: 1716 Partitionen, Dauer: 79 ms
7 Kugeln in 8 Urnen: 3432 Partitionen, Dauer: 584 ms
7 Kugeln in 9 Urnen: 6435 Partitionen, Dauer: 6277 ms
7 Kugeln in 10 Urnen: 11440 Partitionen, Dauer: 55155 ms

8 Kugeln in 8 Urnen: 6435 Partitionen, Dauer: 1529 ms
8 Kugeln in 9 Urnen: 12870 Partitionen, Dauer: 18505 ms
8 Kugeln in 10 Urnen: 24310 Partitionen, Dauer: 177118 ms
8 Kugeln in 11 Urnen:
```

Bei 7 bzw. 8 Kugeln in 11 Urnen habe ich nach einigen Minuten abgebrochen :autsch: 

Hier zum Vergleich das Ergebnis von meinem Algorithmus:


```
7 Kugeln in 7 Urnen: 1716 Partitionen, Dauer: 31 ms
7 Kugeln in 8 Urnen: 3432 Partitionen, Dauer: 16 ms
7 Kugeln in 9 Urnen: 6435 Partitionen, Dauer: 62 ms
7 Kugeln in 10 Urnen: 11440 Partitionen, Dauer: 95 ms
7 Kugeln in 11 Urnen: 19448 Partitionen, Dauer: 235 ms
7 Kugeln in 12 Urnen: 31824 Partitionen, Dauer: 486 ms
7 Kugeln in 13 Urnen: 50388 Partitionen, Dauer: 924 ms

8 Kugeln in 7 Urnen: 3003 Partitionen, Dauer: 16 ms
8 Kugeln in 8 Urnen: 6435 Partitionen, Dauer: 47 ms
8 Kugeln in 9 Urnen: 12870 Partitionen, Dauer: 141 ms
8 Kugeln in 10 Urnen: 24310 Partitionen, Dauer: 267 ms
8 Kugeln in 11 Urnen: 43758 Partitionen, Dauer: 595 ms
8 Kugeln in 12 Urnen: 75582 Partitionen, Dauer: 1583 ms
8 Kugeln in 13 Urnen: 125970 Partitionen, Dauer: 3637 ms
9 Kugeln in 7 Urnen: 5005 Partitionen, Dauer: 15 ms
9 Kugeln in 8 Urnen: 11440 Partitionen, Dauer: 94 ms
9 Kugeln in 9 Urnen: 24310 Partitionen, Dauer: 283 ms
9 Kugeln in 10 Urnen: 48620 Partitionen, Dauer: 799 ms
9 Kugeln in 11 Urnen: 92378 Partitionen, Dauer: 2022 ms
```

Das positive ist, dass beide Algorithmen die identischen Ergebnisse liefern  :wink:

Bei der Durchzähl-Methode werde die Wertebereiche bei ein bisschen größeren Zahlen einfach zu groß...da zählt er sich nen Wolf. Allerdings frisst es bei weitem nicht so viel Speicher wie meins.

Aus meiner Sicht ist euere vorgeschlagene Vorgehensweise also leider nicht praktikabel   

Weitere Vorschläge???

Grüße Louis


----------



## SlaterB (8. Nov 2007)

was genau ist denn die Anforderung an deinen Algorithmus, was willst du haben?
nur die Anzahl oder alle Elemente einzeln oder oder..

wohin soll denn geschrieben werden?


----------



## louis (8. Nov 2007)

SlaterB hat gesagt.:
			
		

> was genau ist denn die Anforderung an deinen Algorithmus, was willst du haben?
> nur die Anzahl oder alle Elemente einzeln oder oder..
> 
> wohin soll denn geschrieben werden?



OK...ich komme wohl nicht drumm herum, mein komplettes Vorhaben zu beschreiben. Aber ich denke es ist sinnvoll, dass du dir (wenn noch nicht geschehen) kurz den oben geposteten Link anschaust. Dort ist eine Erklärung für solche Rätsel und testweise mal eines lösen kannst du auch. Probiere es bzw. ihr alle mal aus, es macht Spass. Ansonsten denkt ihr euch, wenn ihr weiter lest: "Was erzählt der denn für wirres Zeug???" 

Grundprinzip des Rätsels ist die Art und Weise, wie sichere Felder in einer Zeile bzw. Spalte aufzufinden sind. Ausgehend von der Angabe der Blöcke verschiebt man Gedanklich die Blöcke von links nach rechts bzw. oben nach unten und prüft, welche Felder immer überlappen. 

Um diese Felder herauszufinden, definiere ich den sog. "Freiheitsgrad" für eine Zeile bzw. Spalte als die "maximal mögliche Verschiebung eines Blocks". Als Anzahl der Lücken definiere ich die Freiräume zwischen den Blöcken und den Anfang und das Ende einer Zeile.

Beispiel: Zeilenlänge 10, Blöcke 2, 5 --> Freiheitsgrad 2 (10 - (2 + 1 zwischen den Blöcken + 5)), Lücken 3
Beispiel: Zeilenlänge 10, Blöcke 1, 3, 1 --> Freiheitsgrad 3 (10 - (1+1+3+1+1)), Lücken 4

Nun kommen die Partitionen ins Spiel: ich berechne nun zu jeder Zeile bzw. Spalte die Partition partition(freiheitsgrad, lücken), um alle möglichen Verteilungen der Freiheitsgrade auf die Lücken zu erhalten.  

Mit diesen Partitionen kann ich nun alle möglichen Verteilungen  der Blöcke in den Zeilen und Spalten eines Rätsels bestimmen. Ich erzeuge mir also eine Liste aller möglichen Partitionen als int[], durchlaufe dann diese Liste und erzeuge für jedes Array aus der Liste ein entsprechendes Array mit der Blockverteilung (Array mit Länge = gesamte Zeilenlänge, 1 für ein gesetztes Feld und 0 für ein leeres Feld). Dazu fülle ich die gefundene Partition und fülle die Werte der Partition in die entsprechenden Lücken ein (in den "mittleren" Lücken muss ich noch 1 für das zwingend freie Feld zwischen den einzelnen Blöcken dazuzählen). Dieses Array speichere ich wieder in einer Liste und hänge diese an ein Zeilen- bzw. Spaltenobjekt, das diese verwaltet. Somit habe ich für jede Zeile und Spalte ein Objekt mit allen möglichen Verteilungen der Blöcke.

Nun generiere ich mir die Lösung des Rätsels, indem ich über die Zeilen und Spalten iteriere und für jede Zeile und Spalte zuerst prüfe, welche Felder sicher belegt sind. Dazu durchlaufe ich alle möglichen Verteilungen der Blöcke und prüfe, ob ein Feld in jeder Möglichkeit immer belegt bzw. nicht belegt ist. Wenn ich sichere Elemente in einer Spalte gefunden habe, werden diese in einem Array markiert und die entsprechenden sicheren Felder in der korrespondierenden Zeile auch als sicher markiert (und genau andersrum auch). Anhand dieser sicheren Felder schmeisse ich dann alle Elemente in meiner möglichen Verteilungsliste der Blöcke raus, die dazu nicht passen.  Diesen Vorgang wiederhole ich so lange, bis eine sichere Lösung gefunden ist.

Bei den Rätseln, die ich bisher ausprobiert habe, bin ich mit dieser Methode nach max. 100 Iterationen auf die Lösung gekommen, wobei ich mir vorstellen kann, das kompliziertere Rätsel noch mehr "Intelligenz" benötigen.

Vielleicht ist das ganze jetzt ein bisschen klarer geworden...ich hoffe ich habe nicht zu wirr gefaselt  Mir ist bewusst, dass das ganze eine ziemliche "Holzhammermethode" ist, aber wenn man mal ein größeres Rätsel in so einem PM Heftchen per Hand gemacht hat und versucht, alle Lösungsstrategien zusammenzuschreiben, die man dabei anwendet, wird das ziemlich kompliziert...da war mir als erster Wurf die Holzhammermethode lieber....soll je keine Doktorarbeit werden.

Bei Bedarf kann ich auch mal den kompletten Code posten...ob den jemand nach dem obigen Roman durchlesen will, halte ich für fraglich 

Grüße
Louis


----------



## happy_robot (9. Nov 2007)

Ok....das hat mich jetzt ins Mark getroffen ..   

Hab meine Variante mal überarbeitet und nen Booster reingehauen.

Bei 9 Kugeln, 11 Behältern: Mit Ausgabe 2464ms, ohne Ausgabe 65ms. 
Bei 12 Kugeln, 16 Behältern: Ohne Ausgabe 8769ms, 17383860 Permutationen.   

Speicherbedarf fast nix..... 



```
public static void partBoooost(int base, int num) {
		long start = System.currentTimeMillis(); 
		int counter = 0;
		char[] output = new char[num];
		for(int n = 0; n < output.length; n++) {
			output[n] = 0;
		}
		
		int sum = 0;
		while(true) {
			for(int n = 0; n < num; n++) {
				if(output[n] < base) {
					if(sum > base) {
						sum += base-output[n];
						output[n] = (char)base;
					} else {
						output[n]++;
						sum += 1;
					}
					break;
				} else {
					if(n == num-1) {
					    long end = System.currentTimeMillis()-start;
				        System.out.println("Zeit:"+end); 
						System.out.println("Permutationen:"+counter);
						return;
					} else {
						sum -= output[n];
						output[n] = 0;
					}
				}
			}

			
			if(sum == base) {
				counter++;
				String strOutput = "";
				for(int n = 0; n < num; n++) {
					strOutput += (int)output[n]; 
				}
				System.out.println(strOutput);
			}
		}
		
    }
```


mfg


----------



## louis (9. Nov 2007)

Holla die Waldfee 

Das klingt ja vielversprechend! Muss ich mir genauer anschauen, wenn ich Zeit habe. Vielen Dank auf jeden Fall happy_robot!!!

mfg Louis


----------



## louis (11. Nov 2007)

Hi, nochmal ich.

Habe das ganze nun mal getestet und als gut befunden! Ich habe den Algorithmus jetzt mit kleinen Anpassungen eingebaut...rennt jetzt ne ganze Ecke schneller! 

grüße Louis


----------



## V0lle85 (22. Dez 2007)

Hallo!

Ich bin auf diesen Thread (und dieses Board) gestoßen, weil ich einen solchen Algorithmus ebenfalls geschrieben habe. Zwar suche ich nach einer Möglichkeit, Kombinationen wie 1,2,0,0,0 und 0,0,0,2,1, die durch "Spiegelung" ineinander übergehen, garnicht erst doppelt zu generieren, worum es hier ja nicht geht. Allerdings glaube ich, dass mein Algorithmus, wie ich ihn bisher nutze, besonders für größere Zahlen noch effizienter sein dürfte.

Ich muss dazu sagen, dass ich nicht in Java programmiere, sondern dass ich ihn in Octave, einer Script-Sprache ähnlich Matlab (nicht gerade schnell  ), umgesetzt habe.

Verstehe ich es richtig, dass ihr quasi ALLE Zahlen in der entsprechenden Basis hochzählt, um dann jeweils zu überprüfen, ob die Gesamtsumme der Zahlen tatsächlich der Basis entspricht?

Mein Algorithmus geht anders vor, und zwar derart, dass jede erzeugte Kombination automatisch die richtige Summe hat.

In Pseudocode sieht das etwa so aus:


```
%%Initialisiert wird so:
Output[1] = n;
for i = 2 to n do Output[i] = 0;
%%%

%% Finden der weiteren Kombinationen:
while Output[n] != x do
{
if Output[1] > 0 do
  {
  Output[1]--;
  Output[2]++;
  }
else
  {
  i = 1;
  while 1 do
    {
    if Output[i] > 0 do                %% Erstes Element ungleich Null gefunden
      {
      Output[i+1]++;                  %% Das geht, weil i=n in dieser Schleife nie erreicht wird, da sonst x[n] == n wäre...
      Output[1] = Output[i] - 1;
      Output[i] = 0;
      break;
      }
    i++;
    }
  }
AUSGABE ODER SO...
}
```

Auf diese Weise vermeidet man den Overhead, der gerade bei großen n und x dadurch entsteht, dass man viele Zahlen zwar zählt, aber ohnehin wegschmeißen muss.

Zur Erklärung mal ein kleines Zahlenbeispiel. Wir wollen die 9 verteilen. Auf wieviele Plätze ist letztenendes für den Algorithmus fast egal, bloß dass abgebrochen wird, wenn an letzter Stelle die Zahl n (und damit überall anders eine 0) steht.

Dann wird angefangen mit:

9 0 0 0 0 0 0

Von der ersten Stelle wird 1 abgezogen und auf die zweite Stelle geschoben:

8 1 0 0 0 0 0

Das wird solange gemacht, bis an erster Stelle eine Null steht. Erinnert, wenn man die Zahlen umdreht, irgendwie an die wiederholte Addition von 9, oder? 

7 2 0 0 0 0 0
...
0 9 0 0 0 0 0

Jetzt steht an erster Stelle ne Null. Dann wird die erste Stelle ungleich Null gesucht. Die darüber liegende Stelle wird dann um 1 erhöht, der Rest der an der Stelle liegenden "Kugeln" wird wieder auf die erste Stelle gepackt.
--->

8 0 1 0 0 0 0

Man sieht, dass hierdurch automatisch die Zahl "99" übersprungen wird. Jetzt ist die erste Stelle wieder größer Null
--->

7 1 1 0 0 0 0
6 2 1 0 0 0 0
...
0 8 1 0 0 0 0

Erste Stelle ungleich 1 suchen... übersprungen werden dadurch 189 und 198...
--->

7 0 2 0 0 0 0

... usw...

Grundlage dieser Vorgehensweise ist tatsächlich das, was passiert, wenn man die Zahl n-1 in der Basis n immer wieder addiert und alle Zahlen überspringt, deren Quersumme nicht direkt n-1 ist, wie z.B. eben die 99 bzw. 189 und 198.

Ich hoffe, dass ich nicht gegen irgendeine Art von Boardregel verstoßen habe, weil dieser Text zu lang, ausführlich oder einfach nicht Java-mäßig genug ist  Außerdem hoffe ich, dass das überhaupt wen interessiert. Sollte jemand wissen, wie ich diesen Algortihmus anpassen kann, damit direkt nicht 7 0 2 0 0 0 0 und 0 0 0 0 2 0 7 beide generiert werden, OHNE hinterher die generierte Zahl dafür überprüfen zu müssen, dann wäre es toll, wenn ich das erfahren würde 

Gruß, Volker


----------



## V0lle85 (23. Dez 2007)

Hoppla, mir sind da gerade ein, zwei Fehler aufgefallen, die mir wohl unterlaufen sind, weil ich meine Variablennamen umbenannt habe und davon abgesehen für meine Anwendung nur der Fall n = x wichtig war.
Output hieß vorher blöderweise x, was sich aber mit der Anzahl der Plätze x etwas biss.
Also nochmal zur Klärung: x ist die Anzahl der Plätze, n die in ihre Summen zu zerlegene Zahl.


Folgende Fehler wären zu korrigieren:

Zeile 4 des Codebeispiels: "for i = 1 to x" statt "for i = 1 to n"
Zeile 8: Output[x] != n, nicht umgekehrt
Zeile 22: %% Das geht, weil i=x in dieser Schleife nie erreicht wird, da sonst Output[x] == n wäre... 

Sorry dafür, es war spät und ich habe das Beispiel fix aus dem Kopf aufgeschrieben. Da ich zu dem Zeitpunkt nicht im Forum angemeldet war, kann ich die Fehler nicht selbst korrigieren, vllt könnte das ein Moderator für mich übernehmen?

Gruß, Volker


----------



## happy_robot (24. Dez 2007)

Frohes Fest 

nachdem nun die geschenke verteilt sind und die erste flasche wein den hals passiert hat kann ich hierzu nur eines sagen. egal wie du das auch immer geregelt hast, wie sind die zeiten? mein algorithmus schmeisst auch unnötige berechnungen weg. hast du hier für deinen alg. werte? 
wenn sie wirklich vergleichbar sein sollen sollten sie aber in java gemessen werden, ausser sie sind eklatant besser.

weihnachtliche grüße


----------



## V0lle85 (27. Dez 2007)

Hi! Wünsche dir, ebenfalls ein frohes Fest gehabt zu haben! 

Ich kann dir leider überhaupt keine Zeiten nennen, da mein Algorithmus in einem Programm fest implementiert ist, welches diese Partitionierung auf mehrere Blöcke anwendet und zusätzlich noch irgendwelche Gewichtsfaktoren ausrechnet. Es macht also wenig Sinn, die Zeiten dieses Programms anzugeben, da außerdem auch noch nur der Fall 
n = x gebraucht wird.

Es wäre toll, wenn du oder jemand anders aus diesem Forum das Teil mal in Java umsetzen könnte, einfach aus Spaß an der Freude, um mal einen Vergleich zu haben. Mich würde es sehr interessieren, ob sich die Mühe, die ich in die Überlegungen gesteckt habe, auch gelohnt hat.

Andernfalls sehe ich mich gezwungen, mich spartanisch in Java einzulesen, was sicherlich ohnehin nicht nachteilig wäre. Aber dann könnten die Ergebnisse auch durch Erfahrungsmangel verfälscht werden 

Ich werd mal sehen, ob ich Zeit finde. Allzu kompliziert ist das Ganze ja nicht zu programmieren. Aber wie gesagt, vllt hat ja auch jemand von euch Zeit und Lust?

Gruß, Volker


----------



## Guest (28. Dez 2007)

Da bin ich mal wieder!

Ich habe deinen letzten hier angegebenen Algorithmus mal einfach per Copy & Paste in ne Datei gepackt und nur durch eine aurufende Main-Funktion ergänzt.

Aus irgendwelchen Gründen bekomme ich dabei langsamere Zeiten als du, obwohl mein Laptop eigtl auf dem neusten Stand ist... evtl hast du einen wundervoll schnellen Quad-Core-Festrechner benutzt? Jedenfalls habe ich für den sinnvollen Vergleich sowohl deinen als auch meinen Algorithmus mit einigen Kombinationen in der gleichen Testumgebung (die Linux-Konsole meines Laptops) durchlaufen lassen. Mit deinem Programm als Vorlage war es ja nicht allzu schwer, die Java-Syntax einigermaßen hinzubekommen und so meinen Algorithmus umzusetzen,

Ich habe allerdings die Output-Variable durch ein Integer-Array ersetzt (in beiden Programmen), weil der Compiler für mich sinnlose Fehlermeldungen ausgab, die sich dadurch vermeiden ließen. Das sollte den Vergleich jedoch nicht beeinflussen, denn es werden ja für beide Programme die gleichen Variablentypen genutzt. Macht es eigentlich von der Geschwindigkeit her einen Unterschied, ob man Charakter- oder Integer-Variablen nutzt? Das könnte dann ja ein Grund dafür sein, dass dein Algorithmus auf meinem Rechner langsamer läuft. Was solche Fragen angeht, kenne ich mich überhaupt nicht aus, da ich nur sehr wenig Programmiererfahrung habe. Rein technisch fände ich das allerdings unlogisch, da die Register ja 32Bit fassen und die Operationen der ALU hierfür ausgelegt sind.

Ich habe jedenfalls folgende Zeiten erhalten:

Dein Algorithmus:

```
7 Kugeln, 7 Urnen: mit Ausgabe 228ms, ohne Ausgabe 3ms, 1716 Partitionen
7 Kugeln, 8 Urnen: mit Ausgabe 520ms, ohne Ausgabe 7ms, 3432 Partitionen
7 Kugeln, 9 Urnen: mit Ausgabe 1007ms, ohne Ausgabe 18ms, 6435 Partitionen
7 Kugeln, 10 Urnen: mit Ausgabe 1588ms, ohne Ausgabe 39ms, 11440 Partitionen
7 Kugeln, 11 Urnen: mit Ausgabe 2743ms, ohne Ausgabe 88ms, 19448 Partitionen
7 Kugeln, 12 Urnen: mit Ausgabe 4584ms, ohne Ausgabe 191ms, 31824 Partitionen
7 Kugeln, 13 Urnen: mit Ausgabe 7471ms, ohne Ausgabe 406ms, 50388 Partitionen

8 Kugeln, 7 Urnen: mit Ausgabe 442ms, ohne Ausgabe 4ms, 3003 Partitionen
8 Kugeln, 8 Urnen: mit Ausgabe 860ms, ohne Ausgabe 12ms, 6435 Partitionen
8 Kugeln, 9 Urnen: mit Ausgabe 1743ms, ohne Ausgabe 29ms, 12870 Partitionen
8 Kugeln, 10 Urnen: mit Ausgabe 3340ms, ohne Ausgabe 71ms, 24310 Partitionen
8 Kugeln, 11 Urnen: mit Ausgabe 6115ms, ohne Ausgabe 159ms, 43758 Partitionen
8 Kugeln, 12 Urnen: mit Ausgabe 10745ms, ohne Ausgabe 350ms, 75582 Partitionen
8 Kugeln, 13 Urnen: mit Ausgabe 20300ms, ohne Ausgabe 757ms, 125970 Partitionen


9 Kugeln, 11 Urnen: mit Ausgabe 12874ms, ohne Ausgabe 264ms, 92378 Partitionen
10 Kugeln, 11 Urnen: mit Ausgabe 25748ms, ohne Ausgabe 469ms, 184756 Partitionen
11 Kugeln, 11 Urnen: mit Ausgabe 55475ms, ohne Ausgabe 822ms, 352716 Partitionen

12 Kugeln, 16 Urnen: mit Ausgabe --, ohne Ausgabe 87847ms, 17.383.860 Partitionen
```

Mein Algorithmus:

```
7 Kugeln, 7 Urnen: mit Ausgabe 254ms, ohne Ausgabe "0ms", 1716 Partitionen
7 Kugeln, 8 Urnen: mit Ausgabe 460ms, ohne Ausgabe 1ms, 3432 Partitionen
7 Kugeln, 9 Urnen: mit Ausgabe 863ms, ohne Ausgabe 1ms, 6435 Partitionen
7 Kugeln, 10 Urnen: mit Ausgabe 1545ms, ohne Ausgabe 2ms, 11440 Partitionen
7 Kugeln, 11 Urnen: mit Ausgabe 2666ms, ohne Ausgabe 5ms, 19448 Partitionen
7 Kugeln, 12 Urnen: mit Ausgabe 4408ms, ohne Ausgabe 5ms, 31824 Partitionen
7 Kugeln, 13 Urnen: mit Ausgabe 7035ms, ohne Ausgabe 10ms, 50388 Partitionen

8 Kugeln, 7 Urnen: mit Ausgabe 389ms, ohne Ausgabe 1ms, 3003 Partitionen
8 Kugeln, 8 Urnen: mit Ausgabe 853ms, ohne Ausgabe 1ms, 6435 Partitionen
8 Kugeln, 9 Urnen: mit Ausgabe 1715ms, ohne Ausgabe 2ms, 12870 Partitionen
8 Kugeln, 10 Urnen: mit Ausgabe 3267ms, ohne Ausgabe 5ms, 24310 Partitionen
8 Kugeln, 11 Urnen: mit Ausgabe 5960ms, ohne Ausgabe 8ms, 43758 Partitionen
8 Kugeln, 12 Urnen: mit Ausgabe 10404ms, ohne Ausgabe 14ms, 75582 Partitionen
8 Kugeln, 13 Urnen: mit Ausgabe 17501ms, ohne Ausgabe 23ms, 125970 Partitionen

9 Kugeln, 11 Urnen: mit Ausgabe 12694ms, 17ms, 92378 Partitionen
10 Kugeln, 11 Urnen: mit Ausgabe 28743ms, 33ms, 184756 Partitionen
11 Kugeln, 11 Urnen: mit Ausgabe 54680ms, 53ms, 352716 Partitionen

12 Kugeln, 16 Urnen: mit Ausgabe --, ohne Ausgabe 2965ms, 17383860 Partitionen


Und hier noch ein kleiner Leistungstest:

16 Kugeln, 16 Urnen, ohne Ausgabe: 50717ms, 300.540.195 Partitionen
```

Es zeigt sich, dass die Frage nach dem genutzten Algorithmus nahezu irrelevant ist, wenn man alle Kombinationen ausgeben will (Allerdings interessieren die ja meist auch nicht  ) oder wenn man das Ganze für relativ große x und n berechnen lassen will.

Bei meinem Test hat sich meine Variante, was den reinen Algorithmus ohne Ausgabe angeht, durchaus als schneller herausgestellt (Faktor fast 30 bei n = 12, x = 16; Faktor ca. 20 bei n = 7, x = 9).

Vielleicht möchte das jemand mal bei sich testen (und hoffentlich bestätigen  ). Daher hier der Vollständigkeit halber für Copy & Paste der Java-Code:


```
public static void Algorithm(int base, int num) {
	long start = System.currentTimeMillis();
	int counter = 1;
	int[] output = new int[num];
	output[0] = base;
	for(int n = 1; n < output.length; n++) {
		output[n] = 0;
	}
	while(output[num-1] != base) {
		if (output[0] > 0) {
			output[0]--;
			output[1]++;
		} else {
			for(int i = 1; i < output.length; i++) {
				if (output[i] > 0) {
					output[i+1]++;
					output[0] = output[i] - 1;
					output[i] = 0;
					break;
				}
			}
		}
		counter++;
	}
	long end = System.currentTimeMillis()-start;
	System.out.println("Zeit:"+end);
	System.out.println("Permutationen:"+counter);
}
```

Achja, und die Anzahl der Partitionen ist auch hier glücklicherweise wieder in beiden Fällen identisch.

Gruß, Volker


----------

