Mathe: Kombination/Permutation - Optimierung?

Sargnagel · 18.03.2004

Hallo,

vor kurzem gab man mir in meiner Arbeitsgruppe an der Uni ein 20^10 Rechenmonstrum zum Durchrechnen.
Das ergibt dann 1,024 * 10^13 Möglichkeiten, 20 Werte zur 10. Ordnung anzuordnen (d.h. Kombination mit Wiederholung und mit Berücksichtigung der Anordnung). Interessiert hat uns, wieviele Kombinationen eine Summe bildeten, die über einem bestimmten Schwellenwert liegt. Um einen ganzen Haufen an Berechnungen etwas abzukürzen, habe ich einen kleinen Trick angewandt, um die Durchläufe der innersten Schleife zu reduzieren.
Insgesamt benötigte mein kleiner 1.2 GHz Celeron Tualatin ca. 1,5h.

Meine Frage ist: Gibt es Algorithmen, mit denen man solche Berechnungen schneller durchführen kann? Denn die Permutationen einer 10er Folge sind natürlich völlig uninteressant für mich, da sie immer dieselbe Summe bilden.
Also, bevor ich das Rad eventuell neu erfinde, frage ich doch lieber mal die Experten, insbesondere die Mathematiker bzw. Informatiker, ob schon eine fertige Lösung existiert?!

Vielen Dank

Gruß

Sargnagel

P.S.: Klar sind 1,5h für 20^10 Berechnungen noch nicht die Welt, aber ich denke in größeren Dimensionen, denn z.B. bei 10^20 sieht das schon anders aus ...

i_hasser · 19.03.2004

Das riecht ja nach einem neuen Prog Wettbewerb

Ich bin in Wahrscheinlichkeitsrechnung gerade nicht allzu fit - kannst du mal einen Algorithmus kurz erklären?

Sargnagel · 19.03.2004

Ich hab's geahnt!

Das sind einfach nur 10 ineinander geschachtelte Schleifen. Die Werte habe ich zuvor absteigend sortiert, damit ich in der innersten Schleife abbrechen kann, sobald der Schwellenwert unterschritten worden ist. Denn mit allen nachfolgenden Werten können keine Summen mehr gebildet werden, die den Schwellenwert überschreiten.

Ich poste den Quellcode später. Jetzt habe ich leider keine Zeit.

bis nachher

P.S.: ich grübele schon an einer SSE-Lösung (AMD64) ...

Sargnagel · 19.03.2004

Hier ist der Quellcode meiner Brute Force Methode. Eleganter wäre natürlich eine Lösung, die von vornherein die Permutationen nicht berechnet. Meine Ideen dazu poste ich, sobald ich sie in verständlicher Art und Weise niedergeschrieben habe.

Code:

#include <stdio.h>
#include <math.h>

int main(void)
{
	float x[] = {	1.595339, 1.131402, 1.098612, 0.683097, 0.559616,
			0.165514, -0.139262, -0.186330, -0.342490, -0.342490,
			-0.356675, -0.597837, -1.049822, -1.108663, -1.171183,
			-2.040221, -2.207275, -3.218876, -3.912023, -3.912023
				};
	float y[] = {	0.774727, 0.722706, 0.683097, 0.553885, 0.488580,
			0.364643, 0.182322, 0.104360, -0.094311, -0.105361,
			-0.150823, -0.248461, -0.733969, -0.994252, -1.049822,
			-1.272966, -1.272966, -1.309333, -1.469676, -3.912023
				};
	
	unsigned long long int big_counter = 0;
		
	for(int a = 0; a < 20; ++a)
	{ 
		for(int b = 0; b < 20; ++b)
		{
			for(int c = 0; c < 20; ++c)
			{
				unsigned int small_counter = 0;
				float sum1 = x[a]+y[b]+x[c];
				
				for(int d = 0; d < 20; ++d)
				{
					float sum2 = sum1+y[d];
					
					for(int e = 0; e < 20; ++e)
					{
						float sum3 = sum2+x[e];
						
						for(int f = 0; f < 20; ++f)
						{
							float sum4 = sum3+y[f];
							
							for(int g = 0; g < 20; ++g)
							{
								float sum5 = sum4+x[g];
								
								for(int h = 0; h < 20; ++h)
								{
									float sum6 = sum5+y[h];
									
									for(int i = 0; i < 20; ++i)
									{
										float sum7 = sum6+x[i];
										
										for(int j = 0; j < 20; ++j)
										{
											if((sum7+y[j]) <= 2.0)
												break;
											else
												++small_counter;
										}	
									}
								}
							}
						}
					}
				}
				
				big_counter += small_counter;
				printf("\nupdate %lld", big_counter);
				fflush(stdout);
			}
			
		}
		
		printf("\n%d. pass of outer loop finished; big_counter = %lld", a+1, big_counter);
		fflush(stdout);
	}   
	
	printf("\nfinal result: %lld", big_counter);
	
	return 0;
}

Trodat · 19.03.2004

Also erstmal sehen, ob ich dein Problem richtig verstanden habe:
Du hast 20 Zahlen vorgegeben und sollst berechnen, wieviele Summen aus jeweils 10 dieser Zahlen es gibt, die über einem festen Wert A liegen.
Richtig?

Falls ich richtig liege, dann gibt es ganz sicher schnellere Algorithmen zur Lösung des Problems.
Ein relativ einfacher Ansatz zur Beschleunigung, der mir gerade auf Anhieb einfällt, ist folgender:

Warum überprüfst du nicht nach jedem Additionsschritt, ob die Summe bereits über dem Schwellenwert liegt?
Zum Beispiel, wenn du gerade 3 Zahlen addiert hast, dann könntest du prüfen, ob der Schwellenwert schon überschritten ist. Falls ja, brichst du die Schleifenbearbeitung ab, die inneren Schleifen sind ja dann unnötig. Deinen Counter für die zutreffenden Möglichkeiten musst du dann natürlich nicht nur um 1 erhöhen, sondern um die Anzahl der Möglichkeiten, die anderen 7 Plätze der Summe noch zu besetzen.

Und deinen Ansatz mit dem Abbrechen, falls die Summe im letzten Schritt mit der größten Zahl nicht über dem Schwellenwert liegt, könntest du auch noch auf frühere Schritte ausweiten. Wenn z.B. im vorletzten Schritt die Summe mit den beiden größtmöglichen Summanden auf den verbleibenden zwei Plätzen nicht größer als der Schwellenwert ist, dann kannst du ja die ganze innere Schleife für diese Kombination der ersten 8 Summanden abbrechen.

Sind jetzt nur einfache Ansätze, aber damit sollte das Programm schon wesentlich schneller laufen.

Edit: Das mit der Überprüfung ob die Summe schon groß genug ist macht natürlich nur ab dem Schritt n Sinn, wo es zum ersten mal überhaupt n Summanden gibt, die den Schwellenwert überschreiten

Falls du das Programm aber mit beliebigen Werten verwenden willst, weißst du natürlich vorher nicht, welcher Schritt das ist, und musst es jedesmal machen.

i_hasser · 19.03.2004

Also als erstes würd ich die Schleifen auseinander nehmen, das kann man mit einer einzigen while(1) Schleife realisieren (die einzelnen Zähler können in ein Array und man muss eben selbst den richtigen nehmen und erhöhen usw.).

Dann würd ich in dieser Schleife die Summe von mehreren Werten gleichzeitig berechnen, das freut die FPU.

Ansonsten schließ ich ich Trodat an - "Du hast 20 Zahlen vorgegeben und sollst berechnen, wieviele Summen aus jeweils 10 dieser Zahlen es gibt, die über einem festen Wert A liegen.
Richtig?"

EDIT

Das wichtigste ist natürlich, dass die Reihenfolge der Werte keine Rolle spielt - damit schränkt sich das Feld der Möglichkeiten erheblichst ein.

Sargnagel · 19.03.2004

Original geschrieben von Trodat
Also erstmal sehen, ob ich dein Problem richtig verstanden habe:
Du hast 20 Zahlen vorgegeben und sollst berechnen, wieviele Summen aus jeweils 10 dieser Zahlen es gibt, die über einem festen Wert A liegen.
Richtig?

Nicht ganz richtig!

Wenn Du genau hinschaust, siehst Du, daß ich zwei Mengen von je 20 Zahlen gegeben habe. D.h. 20^5 * 20^5 = 20^10. Aber vom Prinzip her ändert sich nun nichts an Deiner Feststellung.

Original geschrieben von Trodat
Warum überprüfst du nicht nach jedem Additionsschritt, ob die Summe bereits über dem Schwellenwert liegt?

Schön wäre es. Aber bedenke, daß ich alle möglichen Kombinationen durchrechne. Ich breche die Berechnung immer dann ab, wenn der Schwellenwert unterschritten worden ist, da es weitaus mehr Kombinationen gibt, bei denen der Schwellenwert nicht erreicht wird. Und dieses Abbrechen kann ich "nur" in der innersten Schleife vornehmen; bzw. sicherlich auch noch in der vorletzten oder vielleicht sogar vorvorletzten, wenn ich mir die Zahlen nochmal genau zu Gemüte führe und entsprechend weitere Tests einbaue.

Original geschrieben von Trodat
Und deinen Ansatz mit dem Abbrechen, falls die Summe im letzten Schritt mit der größten Zahl nicht über dem Schwellenwert liegt, könntest du auch noch auf frühere Schritte ausweiten. Wenn z.B. im vorletzten Schritt die Summe mit den beiden größtmöglichen Summanden auf den verbleibenden zwei Plätzen nicht größer als der Schwellenwert ist, dann kannst du ja die ganze innere Schleife für diese Kombination der ersten 8 Summanden abbrechen.

Jo, korrekt. Das könnte ich noch einarbeiten (s.o.).

Aber weitaus effizienter wäre es, könnte man schon von vornherein auf die Berechnung von Permutationen verzichten ...

Ich habe dazu auf den Seiten von Donald Knuth was gefunden. Er schreibt gerade an Vol4 von "The Art of Computer Programming" und stellt entsprechende Rohfassungen einzelner Kapitel zur Ansicht bereit.
Auf Seite 16 habe ich einen interessante Hinweis gefunden: "Combinations of a multiset". Der von mir gesuchte Algorithmus hat eventuell mit Gray codes und revolving door algorithms zu tun.

Leider habe ich zZt nicht nicht genügend Zeit, mich damit näher zu beschäftigen. Ich hatte nur gehofft, daß jemandem schon eine Lösung bekannt wäre, d.h. das es vielleicht normaler Vorlesungsstoff im Mathe- bzw. Informatik-Studium wäre.

Sargnagel · 19.03.2004

Original geschrieben von intel_hasser
Also als erstes würd ich die Schleifen auseinander nehmen, das kann man mit einer einzigen while(1) Schleife realisieren (die einzelnen Zähler können in ein Array und man muss eben selbst den richtigen nehmen und erhöhen usw.).

Jo. Das kann man auch machen.

Original geschrieben von intel_hasser
Dann würd ich in dieser Schleife die Summe von mehreren Werten gleichzeitig berechnen, das freut die FPU.

Mit SSE - logisch. Aber wie realisierst Du dann das Abbrechen der Berechnung, wenn bei einer dieser vier Summen, die Du auf einmal berechnen kannst, der Schwellenwert unterschritten wird und weitere Summanden nicht addiert werden müssen? Füllst Du dann diese eine Zeile in den SSE-Registern mit neuen Werten? Oder willst Du alles gnadenlos durchrechnen? Oder hast Du eine völlig andere Implementation im Kopf?

Original geschrieben von intel_hasser
Ansonsten schließ ich ich Trodat an - "Du hast 20 Zahlen vorgegeben und sollst berechnen, wieviele Summen aus jeweils 10 dieser Zahlen es gibt, die über einem festen Wert A liegen.
Richtig?"

Siehe mein obiges Posting.

Original geschrieben von intel_hasser
Das wichtigste ist natürlich, dass die Reihenfolge der Werte keine Rolle spielt - damit schränkt sich das Feld der Möglichkeiten erheblichst ein.

Yep! Ohne Berücksichtigung der Reihenfolge; d.h. wir können alle Permutationen einer Kombination ausschließen, d.h. jeweils 10! Möglichkeiten. Nur wie macht man das?

i_hasser · 19.03.2004

Also wenn X und Y Mengen sind bildest du Z=XxXxXxXxXxYxYxYxYxY und zählst dann durch, wie viele Elemente >2 sind. So richtig?

Ich denke das ließe sich am besten als statisches Netz darstellen.

Hannnibal · 19.03.2004

Moin,

ich würde sagen man kann vorraussagen treffen wann der schhwellwert A überschritten wird.

Dazu sortierst du die beiden felder von klein nach groß.

Dann gilt folgendes:

angenommen wir haben in a {1, 2, 3, 4, 5, 6, 7} und in b{1, 2, 3, 4, 5, 6, 7} der schwellwertt sei A 12.

So nun beginnt die permutation mit den feldplätzen 0 0 0 0 0 0 0 0 0 0 A=10
nächster schritt 0 0 0 0 0 0 0 0 0 1 A=11
beim 3. schritt 0 0 0 0 0 0 0 0 0 2 A=12
die nächsten schritte bei der erhöhung der letzten zahl werden ebenfalls über dem schwellwert liegen, also kann man auch den zähler dementsprechend höhersetzten und bei 0 0 0 0 0 0 0 0 1 0 weitersuchen

.

mfg

Sargnagel · 19.03.2004

Original geschrieben von intel_hasser
Also wenn X und Y Mengen sind bildest du Z=XxXxXxXxXxYxYxYxYxY und zählst dann durch, wie viele Elemente >2 sind. So richtig?
Ich denke das ließe sich am besten als statisches Netz darstellen.

Meinst Du nun '*' oder '+' ? Ich bilde schließlich die Summen von jeweils 10 Werten. Diese Summe muß >2 sein, um gezählt zu werden.

Original geschrieben von Hannnibal
ich würde sagen man kann vorraussagen treffen wann der schhwellwert A überschritten wird.

Dazu sortierst du die beiden felder von klein nach groß.

Es sollte eher ein Unterschreiten des Schwellenwertes als Abbruchbedingung herangezogen werden, da es weitaus mehr Summen <=2 gibt, als >2. Also, die Mengen einfach - wie gehabt - absteigend sortieren.
Ein weiteres Problem ist, daß sowohl positive als auch negative Werte in den Mengen auftauchen. Ich habe schon an eine Verschiebung der Baseline nachgedacht, so daß alle Zahlen positiv wären, aber das ist fast nicht möglich bzw. wäre weitaus komplizierter als diese Kombinationsberechnungen.

i_hasser · 19.03.2004

Ich hab die Kreuzmenge gebildet. Also wenn A={a,b} und B={c,d,e}, dann ist AxB={ac,ad,ae,bc,bd,be}.

Sargnagel · 19.03.2004

Original geschrieben von intel_hasser
Ich hab die Kreuzmenge gebildet. Also wenn A={a,b} und B={c,d,e}, dann ist AxB={ac,ad,ae,bc,bd,be}.

Ach ja, stimmt. Entschuldige, aber das ist schon etwas her.
Wenn das hilft, die Permutationen zu verhindern, dann immer her damit!

i_hasser · 19.03.2004

Leider nicht, das drückt es mathematisch nur etwas anders aus - die Begriffe Permutation und Kombination hab ich immer strengstens gemieden

i_hasser · 19.03.2004

Also ich denke wirklich am einfachsten ist es, wenn wir die Reihenfolge rausnehmen. Das wird zwar nicht ganz so einfach, aber ist die beste Optimierung.

Man könnte erstmal Grundfolgen aufstellen, die keinen Wert gemeinsam haben aber alle Werte aus den beiden Arrays nehmen.
Dann könnte man diese Grundfolgen nach bestimmten Regeln mitenander kombinieren - bei den Regeln muss eben verankert sein, dass keine Kombination 2mal vorkommt.

Dann könnte man es auch mit 2 10x10 Matrizen versuchen, wo die Belegung drinnen gespeichert wird.

EDIT Mir ist noch eine Variante eingefallen, man könnte auch versuchen die Zahlen als Bitmuster auszudrücken - jede Zahl bekommt eine Wertigkeit 2^n zugewiesen. Darüber könnte man schonmal einfache Prüfsummen bilden, die bei lediglich vertauschten Werten identisch ist.

EDIT2 Ja, das klingt am allerbesten. Bei 20 Zahlen reduziert das das Problem auf 1024^2 Berechnungen - ein klacks, selbst für alte Rechner.

EDIT3 hmm der Alg betrachtet nicht alle Lösungen, aber doch die meißten. Man müsste noch eine dynamische Wertigkeit einführen - der Alg betrachtet ja zb. nicht was passiert, wenn 2mal die selbe Zahl mit vorkommt.

PuckPoltergeist · 19.03.2004

Original geschrieben von Sargnagel
Nicht ganz richtig!

Wenn Du genau hinschaust, siehst Du, daß ich zwei Mengen von je 20 Zahlen gegeben habe. D.h. 20^5 * 20^5 = 20^10. Aber vom Prinzip her ändert sich nun nichts an Deiner Feststellung.

Mußt du dich bei den Summen immer aus beiden Mengen bedienen, oder kannst du dabei auch eine unberücksichtigt lassen?

i_hasser · 19.03.2004

So wie ich seinen Alg deute hat er 2 Mengen je 20 Elemente.

Und nun muss er 5 Elemente aus der 1. Menge und 5 Elemente aus der 2. Menge auswählen (je unabhängige Auswahl) - die Summe davon muss dann eben >2 sein (bzw. <2).

Sargnagel · 19.03.2004

Original geschrieben von intel_hasser
Leider nicht, das drückt es mathematisch nur etwas anders aus - die Begriffe Permutation und Kombination hab ich immer strengstens gemieden

Ach so, verständlich.

Erklär doch bitte mal, was Du mit einem statischen Netz meinst? Hast Du zufällig einen Web-Link dazu?

Original geschrieben von intel_hasser
EDIT Mir ist noch eine Variante eingefallen, man könnte auch versuchen die Zahlen als Bitmuster auszudrücken - jede Zahl bekommt eine Wertigkeit 2^n zugewiesen. Darüber könnte man schonmal einfache Prüfsummen bilden, die bei lediglich vertauschten Werten identisch ist.

Das hört sich gut an, aber dann berechnet man - wenn ich das richtig verstehe - doch noch jede Möglichkeit und testet mittels dieser Prüfsumme, ob es sich um eine Permutation handelt. Genau diesen Aufwand wollte ich von vornherein ausschließen; aber ob das möglich ist?

Sind es wirklich nur 1024^2 Möglichkeiten?

Sargnagel · 19.03.2004

Original geschrieben von intel_hasser
So wie ich seinen Alg deute hat er 2 Mengen je 20 Elemente.

Und nun muss er 5 Elemente aus der 1. Menge und 5 Elemente aus der 2. Menge auswählen (je unabhängige Auswahl) - die Summe davon muss dann eben >2 sein (bzw. <2).

@PuckPoltergeist:
So wie intel_hasser es schon erklärt hat, soll es sein. Und alle Summen, die größer als 2 sind, werden gezählt.

PuckPoltergeist · 19.03.2004

Original geschrieben von intel_hasser
So wie ich seinen Alg deute hat er 2 Mengen je 20 Elemente.

Und nun muss er 5 Elemente aus der 1. Menge und 5 Elemente aus der 2. Menge auswählen (je unabhängige Auswahl) - die Summe davon muss dann eben >2 sein (bzw. <2).

Mit oder ohne Wiederholungen?

i_hasser · 19.03.2004

Das Entscheidende ist ja, dass man bei einer Summe die Faktoren vertauschen kann - also wenn du die Werte nur in einer anderen Reihenfolge rauspickst kommt trotzdem genau das selbe Ergebnis raus.

Also es geht mit der Prüfsumme - allerdings muss für jede der 10 Zahlen mehr als 1 bit reserviert sein (genau gesagt Platz für... 5 Möglichkeiten - ein und der selbe Zahlenwert kann ja max. 5mal vorkommen).

Das reduziert das Problem auf (1024² war Blödsinn) 5^10 Möglichkeiten -> 9.7 Millionen. Jedoch muss die Parität immer 10 betragen, das schließt einiges wieder aus.

Du hast oben übrigens 20^10 Rechnungen durchgeführt... schlappe 10 Billionen

@Puck
Mit Wiederholungen - das ist ja das Dumme

PuckPoltergeist · 19.03.2004

Original geschrieben von intel_hasser
Das Entscheidende ist ja, dass man bei einer Summe die Faktoren vertauschen kann - also wenn du die Werte nur in einer anderen Reihenfolge rauspickst kommt trotzdem genau das selbe Ergebnis raus.

Das weiß ich. Es macht aber einen Unterschied, ob du gleiche oder unterschiedliche Elemente permutierst.

Sargnagel · 19.03.2004

Original geschrieben von PuckPoltergeist
Das weiß ich. Es macht aber einen Unterschied, ob du gleiche oder unterschiedliche Elemente permutierst.

[EDIT]
Hatte gerade Mist geschrieben. Ein neuer Versuch:
[/EDIT]
Es geht nur darum, daß sowohl X als auch Y mit je 5 Elementen zur Summe beitragen.

Mein erster Ansatz zu einer SSE-Lösung:
(die Zahlen stellen die Indizes der jeweiligen Mengen dar)

Code:

		x					y
__________________________________  _______________________________	
|				  | |				   |	
0	4	8	12	16  0	4	8	12	16		--> Summe
1	5	9	13	17  1	5	9	13	17		--> Summe
2	6	10	14	18  2	6	10	14	18		--> Summe
3	7	11	15	19  3	7	11	15	19		--> Summe

Nun bildet man die Summen einer jeden Zeile. Danach ordnet man die Zahlen in den Registern neu an. Das würde dann auch mittels mehrerer verschachtelter Schleifen laufen. Man verschiebt im ersten Register die Zahlen nach unten, wobei die unterste dann an die oberste Stelle geschrieben wird. Das zweite Register müßte, wenn es an der Reihe ist, in entgegengesetzter Richtung verschoben werden. Das dritte würde wieder wie das erste Register behandelt werden usw.
Ich bin mir darüber aber noch nicht ganz im klaren.

Natürlich bin ich mir bewußt, daß so noch jede Menge Möglichkeiten außen vor gelassen werden, aber zumindest - denke ich - berechnet man keinerlei Permutationen.
Nun müssen noch die Zahlen in den Registern in die "waagerechte" gebracht werden, um auch mit ihnen alle Kombinationen durchzuspielen. Aber wie nun zw. den Registern getauscht werden muß, das weiß ich (noch) nicht.

Zu guter letzt fehlen noch die Kombinationen mit mehreren gleichen Indizes. Da gibt es dann pro 5er Block folgende Anordnungsmöglichkeiten - wenn ich denn keinen vergessen haben sollte:

Code:

Die Zahlen stehen für die Anzahl an SSE-Registern, die jeweils mit Werten derselben Indizes befüllt sein müssen. D.h. man hat z.B. für die erste Zeile folgende Möglichkeiten:
20! * 19! * 18! * 17!
Wobei die 20! für die 2 in der ersten Zeile, erste Spalte gilt, d.h. zwei Register mit Werten derselben Indizes.
Ich hoffe, ich habe mich verständlich machen können.

PuckPoltergeist · 19.03.2004

Original geschrieben von Sargnagel
[EDIT]
Nach wie vor tragen aber sowohl X als auch Y mit je 5 Elementen zur Summe bei.
[/EDIT]

Ich sehe jetzt den Zusammenhang zum dargestellten Problem nicht. Hier mal die Darstellung, soweit ich es verstanden habe:

Es gibt zwei Mengen A und B von jeweils zehn Elementen. Jetzt werden alle möglichen Summen aus fünf Elementen aus A gebildet und in der Menge A' zusammengefaßt. Das selbe läuft für B analog. Zum Schluß werden alle Kombinationen aus A' und B' gebildet, wobei nur die Ergebnisse von Interesse sind, welchen den Schwellenwert überschreiten. Ist das soweit richtig? (Falls ja, sind hier schon die ersten Permutationen rausgeflogen)
Nun geht darum, die Permutationen in A' und B' zu eliminieren.

i_hasser · 19.03.2004

Was ich meine (nochmal langsam):

Der Alg oben rechnet alle Möglichkeiten durch - uA auch
a+b+c+d
a+c+b+d
b+a+c+d
usw. usf.

Die Ausdrücke oben liefern aber alle je das selbe Ergebnis. Es wäre also sinnvoller nur einen davon durchzurechnen und alle anderen mit selbem Ergebnis einfach auszuschließen - da müssen wir den Alg umdrehen.
Momentan bilden wir die Zahlenauswahl auf ein Ergebnis ab (wir bilden also eine Menge auf eine andere ab

). Dummerweise zeigen mehrere Zahlenauswahlen auf das selbe Ergebnis.
Ziel ist es also das einfach umzudrehen und von den Ergebnissen (die müssen nicht bekannt sein) auf die Zahlenauswahlen zu schließen, da (symbolisch) jedes Ergebniss auf eine andere Untermenge von Zahlenauswahlen zeigt.

Nun klar? Du wolltest doch etwas Theorie von mir hören

Statt Parität hätte ich oben übrigens Quersumme schreiben müssen.

Mit einem statischen Netz meine ich nur, dass wir ein Netz aus allen nötigen Rechnungen aufstellen (die Rechnungen bauen ja teilw. aufeinander auf). Aber das Netz wird etwas größer als es gut wäre und es würde ewig dauern es aufzustellen.

(Nochmal zu der Lösung oben) Mir ist gerade aufgefallen, dass ich die beim 2. Anlauf etwas verhunzt hab (nur in der Umsetzung, nicht in der Theorie).

Wir haben bei jeder Zahl 10 Summanden. Also brauchen wir erstmal eine Zahl mit 10 Ziffern. Jede dieser Ziffern muss 20 Möglichkeiten haben (also ein Zahlensystem mit der Basis 20).

Das macht auch erstmal 20^10 Möglichkeiten (dürfte kein Zufall sein, dass das deinem Alg entspricht).
Aber es ist nur jede Lösung gültig, bei der die Quersumme der Zahl genau 10 beträgt. Das dürfte über die Hälfte ausschließen.

Naja, daran arbeite ich noch. Deutlich einfacher wäre es, wenn jede Zahl nur 1mal in ein und derselben Summe vorkommen darf, dann wäre es ein Kinderspiel (2^20 Möglichkeiten - abzüglich der Zahlen, deren Quersumme!=10 ist).

Mathe: Kombination/Permutation - Optimierung?

Commodore Special

Grand Admiral Special

Commodore Special

Commodore Special

Grand Admiral Special

Grand Admiral Special

Commodore Special

Commodore Special

Grand Admiral Special

Admiral Special

Commodore Special

Grand Admiral Special

Commodore Special

Grand Admiral Special

Grand Admiral Special

Grand Admiral Special

Grand Admiral Special

Commodore Special

Commodore Special

Grand Admiral Special

Grand Admiral Special

Grand Admiral Special

Commodore Special

Grand Admiral Special

Grand Admiral Special

Ähnliche Themen