Fakultätsreihe iterativ optimieren?

30.04.2010, 22:06

Daniel Marschall

Fakultätsreihe iterativ optimieren?

Meine Frage:
Hallo.

Ich habe ein Programm entwickelt, dass eine Reihe von 16 Zahlen (a..p) auswertet und auf eine Formel anwendet. Jede dieser Zahlen darf die Werte 1..16 aufnehmen.

Ich habe also die Zahlen-Kombination

a=[1..16] b=[1..16] c=[1..16] ... p=[1..16]

Es gibt also 16 hoch 16 Kombinationen.

Allerdings habe ich nun noch die Einschränkung, dass jede Zahl nur einmal vorkommen darf.

Deswegen gibt es nun nur noch 16! Kombinationen.

Es gilt nun, alle Kombinationen durchzulaufen - und da es extrem viele Kombinationen sind - möchte ich so viel Rechenaufwand wie möglich produzieren (eine Einzelne If-Abfrage kann sich aufsummieren). Mein Programm funktioniert zwar perfekt, allerdings brauche ich zur Lösung des Problems 160 Tage Rechenzeit, was ich gerne auf 100 Tage minimieren möchte.

Derzeit sieht mein Programmcode so aus (Pseudo-Code):

1. Durchlaufe für "a" von 1 bis 16. (For-Schleife)
2. Durchlaufe für "b" von 1 bis 16. (For-Schleife)
3. Wenn (b ungleich a), dann fahre fort, ansonsten gehe zum nächten "b".
4. Durchlaufe für "c" von 1 bis 16. (For-Schleife)
5. Wenn (c ungleich a) und (c ungleich b), dann fahre fort, ansonsten gehe zum nächten "b".
usw.

Am Ende habe ich eine wahre If-Pyramide, die so aussieht:

Wenn (p ungleich a) und (p ungleich b) und (p ungleich c) ... und (p ungleich o), dann...

Ist mein jetziger Algorithmus zum Durchlaufen aller Kombinationen dieser Fakultätsreihe (keine Ahnung, wie man das nennt) noch optimierbar oder kann man da etwas vereinfachen?

Ich möchte also am Ende alle Kombinationen von

1, 2, 3, 4, 5, 6, ..., 14, 15, 16 (Erste Kombination)
1, 2, 3, 4, 5, 6, ..., 14, 16, 15
1, 2, 3, 4, 5, 6, ..., 15, 14, 16
1, 2, 3, 4, 5, 6, ..., 15, 16, 14
1, 2, 3, 4, 5, 6, ..., 16, 15, 14
...
16, 15, 14, 13, ..., 3, 2, 1 (Letzte Kombination)

Zusatzfrage: Wie nennt man diese Art von endlichen Kombinationen, die eine endliche Reihe mit Elementen eines festen Wertebereiches, allerdings ohne doppelte Elemente als "Set" zusammenfasst?

PS: Hoffe, ich konnte es für alle Nicht-Programmierer verständlich erklären.

Meine Ideen:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:

for (a=1; a<=16; a++) {
for (b=1; b<=16; b++) {
if ((b != a)) {
for (c=1; c<=16; c++) {
if ((c != a) && (c != b)) {
for (d=1; d<=16; d++) {
if ((d != a) && (d != b) && (d != c)) {
for (e=1; e<=16; e++) {
if ((e != a) && (e != b) && (e != c) && (e != d)) {
for (f=1; f<=16; f++) {
if ((f != a) && (f != b) && (f != c) && (f != d) && (f != e)) {
for (g=1; g<=16; g++) {
if ((g != a) && (g != b) && (g != c) && (g != d) && (g != e) && (g != f)) {
for (h=1; h<=16; h++) {
if ((h != a) && (h != b) && (h != c) && (h != d) && (h != e) && (h != f) && (h != g)) {
for (i=1; i<=16; i++) {
if ((i != a) && (i != b) && (i != c) && (i != d) && (i != e) && (i != f) && (i != g) && (i != h)) {
for (j=1; j<=16; j++) {
if ((j != a) && (j != b) && (j != c) && (j != d) && (j != e) && (j != f) && (j != g) && (j != h) && (j != i)) {
for (k=1; k<=16; k++) {
if ((k != a) && (k != b) && (k != c) && (k != d) && (k != e) && (k != f) && (k != g) && (k != h) && (k != i) && (k != j)) {
for (l=1; l<=16; l++) {
if ((l != a) && (l != b) && (l != c) && (l != d) && (l != e) && (l != f) && (l != g) && (l != h) && (l != i) && (l != j) && (l != k)) {
for (m=1; m<=16; m++) {
if ((m != a) && (m != b) && (m != c) && (m != d) && (m != e) && (m != f) && (m != g) && (m != h) && (m != i) && (m != j) && (m != k) && (m != l)) {
for (n=1; n<=16; n++) {
if ((n != a) && (n != b) && (n != c) && (n != d) && (n != e) && (n != f) && (n != g) && (n != h) && (n != i) && (n != j) && (n != k) && (n != l) && (n != m)) {
for (o=1; o<=16; o++) {
if ((o != a) && (o != b) && (o != c) && (o != d) && (o != e) && (o != f) && (o != g) && (o != h) && (o != i) && (o != j) && (o != k) && (o != l) && (o != m) && (o != n)) {
for (p=1; p<=16; p++) {
if ((p != a) && (p != b) && (p != c) && (p != d) && (p != e) && (p != f) && (p != g) && (p != h) && (p != i) && (p != j) && (p != k) && (p != l) && (p != m) && (p != n) && (p != o)) {

// Ab hier kann ich was mit meiner [a, b, c, ..., o, p] Kombination machen :D

}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}

30.04.2010, 22:30

Auf diesen Beitrag antworten »

Zitat:

Original von Daniel Marschall
Zusatzfrage: Wie nennt man diese Art von endlichen Kombinationen, die eine endliche Reihe mit Elementen eines festen Wertebereiches, allerdings ohne doppelte Elemente als "Set" zusammenfasst?

Das nennt man Variationen (ohne Zurücklegen).

Die lassen sich wesentlich effizienter programmieren, als du das getan hast. Falls du in C oder C++ programmierst, kannst du z.B. mal einen Blick auf die GSL werfen, insbesondere diese Funktionen:

http://www.gnu.org/software/gsl/manual/h...rmutations.html
http://www.gnu.org/software/gsl/manual/h...mbinations.html

EDIT: Hab gerade mal selbst ein bisschen programmiert:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:

#include <stdlib.h>
#include <stdio.h>

#define MAXNO_ELEMENTS 100

/*********************************************/

typedef int tElement;

void PrepareElements (tElement *pe, int n)
{
  int i;
  for (i = 0; i < n; i++)
  {
    pe[i] = i+1;
  }
}

void ShowElements (tElement *pe, int k)
{
  int i;
  for (i = 0; i < k; i++)
  {
    printf("%d ", pe[i]);
  }
  printf("\n");
}

/*********************************************/

int GenerateVariations (int n, int k)
{
  tElement  e[MAXNO_ELEMENTS];
  int       c[MAXNO_ELEMENTS];
  tElement  tmp;
  int       i;
  int       n1;
  int       k1;
  if (n > MAXNO_ELEMENTS)
  {
    return 1;
  }
  if (n <= 0 || k <= 0 || k > n)
  {
    return 0;
  }
  PrepareElements(e, n);
  for (i = 0; i < k; i++)
  {
    c[i] = i;
  }
  n1 = n-1;
  k1 = k-1;
  i = k1;
  while (i >= 0)
  {
    if (i == k1)
    {
      ShowElements(e, k);
    }
    if (c[i] < n1)
    {
       tmp = e[c[i]];
       e[c[i]] = e[i];
       e[i] = e[++c[i]];
       e[c[i]] = tmp;
       while (i < k1)
       {
         i++;
         c[i] = i;
       }
    }
    else
    {
        tmp = e[i];
        e[i] = e[n1];
        e[n1] = tmp;
        i--;
    }
  }
  return 0;
}


int main (int argc, char *argv[])
{
  int n = 4;
  int k = 4;
  if (argc > 1)
  {
    n = atoi(argv[1]);
    if (argc > 2)
    {
      k = atoi(argv[2]);
    }
    else
    {
      k = n;
    }
  }
  GenerateVariations(n, k);
  return 0;
}

Mit diesem Code dauert allein die Erzeugung der $\begin{eqnarray*} 16! \approx 2.1\cdot 10^{13} \end{eqnarray*}$ Variationen schätzungsweise 4 Tage, mit immerhin etwa 60 Millionen Variationen pro Sekunde (1 Thread auf einem Intel Q9550). Diese Schätzung basiert auf der Dauer von ca. 100 Sekunden für 13! Variationen.

01.05.2010, 17:46

Mystic

Auf diesen Beitrag antworten »

Wenn man der Übersichtlichkeit halber nur die Kernroutine betrachtet, die zu jeder Permutation auf {1,2,...,n} die jeweils "nächste" (in lexikographischer Reihenfolge) erzeugt, soferne sie nicht bereits die "letzte" ist, so würde das in C# so aussehen (n wird dabei als globale Variable angenommen):

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

int[] nextperm(int[] p) {
	int i,j,t; 
	for(i=n-2;i>=0;i--) if(p[i]<p[i+1]) break;	
	if(i<0) return new int[]{0}; 	
	for(j=n-1;;j--) if(p[i]<p[j]) break; 
	t=p[i]; p[i]=p[j]; p[j]=t; 
	for(j=i+1;j<n+i-j;j++){ 	
		t=p[j];p[j]=p[n+i-j];p[n+i-j]=t; } 
	return p;
}

Im Prinzip muss man also die größtmöglichen Indizes i und j suchen, sodass gilt p[i]<p[j], und zwar so, dass man zuerst i maximiert und dann j. Anschließend werden p[i] und p[j] vertauscht und die Permutation ab der Position i+1 "gestürzt", d.h., aufsteigend (statt vorher absteigend) geordnet...

01.05.2010, 23:17

Daniel_Marschall

Auf diesen Beitrag antworten »

Vielen Dank für euere Antworten!!

Stimmt, da war ja was im Gymnasium mit Statistik und Variationen! ^^

Ich habe die GSL nun eingebunden und angewandt. Ich habe jetzt mit meiner Berechnung eine geschätzte Zeit von nur noch 17 Tagen (davor: 160!) Super!! Mit Zunge

Ich frage mich, wie es möglich ist, für das Durchlaufen der Variationen 1 bis x, einen schnelleren Code als meinen ursprünglichen zu erzeugen. Ich dachte, meine Methode (auch wenn sie ziemlich doof aussieht) sei so simpel, dass man nichts mehr optimieren könnte. Aber scheinbar steckt noch etwas mathematisches dahinter. Ich schau mir mal euere beiden Codes genauer an, um zu verstehen, was dahinter steckt.

02.05.2010, 00:29

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Daniel_Marschall
Vielen Dank für euere Antworten!!

Stimmt, da war ja was im Gymnasium mit Statistik und Variationen! ^^

Naja, eigentlich geht es hier genauer um Permutationen, also um eine überaus spezielle Klasse von Variationen ohne Wiederholung...

Zitat:

Original von Daniel_Marschall
Ich schau mir mal euere beiden Codes genauer an, um zu verstehen, was dahinter steckt.

Speziell was meinen Code betrifft, hab ich ja auch schon kurz zusammengefaßt, was dahintersteckt... Solltest du die Routine in irgendeiner Form verwenden wollen, so würde ich dir allerdings dringend raten, nur den Methodenrumpf in eine while-Schleife "einzubetten", um den Aufruf der Methode, der ja auch noch etwas Zeit kostet, einzusparen...

02.05.2010, 08:24

Auf diesen Beitrag antworten »

"Genauer" ist das nur, wenn du es lediglich auf den obigen Spezialfall 16,16 beziehst. Ich hatte mit der Bezeichnung "Variationen" auf die allgemeinere Frage

Zitat:

geantwortet und so auch den Algorithmus angelegt. Variationen habe ich in der gsl nämlich nicht gefunden, sondern nur Kombinationen und Permutationen, aus denen man dies zwar zusammenbasteln kann, aber auf diesem Weg erheblich Zeit mit Bürokratie vergeudet.

Der oben von mir angegebene Algorithmus liefert die Variationen nicht in lexikographischer Reihenfolge. Eine kleine Modifikation kann dies zwar leisten, kostet nach Messungen aber ca. 30% Aufschlag in der Rechenzeit, weshalb ich es unterlassen habe.

Die ganzen Effizienzbemühungen sind natürlich einigermaßen sinnlos, wenn die letzendliche Bearbeitungsprozedur der Variation (bei mir oben also "ShowElements") zuviel Zeit benötigt. Bei der Vorgabe von maximal 100 Tagen darf ein Durchlauf dieser Prozedur selbst unter Vernachlässigung des Variationserzeugungsaufwandes im Mittel maximal

$\begin{eqnarray*} \frac{100~\mbox{d}}{16!} \approx 400 ~ \mbox{ns} \end{eqnarray*}$

betragen. Sportlich, würde ich mal sagen, da man ja 16 Variablen auszuwerten hat, allzviel rechnen kann man dann nicht mehr - was da zu rechnen ist, hat Daniel Marschall ja nicht verraten (wenn die neue Schätzung mit den 17 Tagen stimmt, kann es wirklich nicht sehr viel sein). Genausowenig wissen wir, ob wirklich alle 16! Variationen zu betrachten sind. Bei einer Reihe von praxisrelevanten Fragestellungen kann man nämlich den volltändigen Variationsbaum kräftig stutzen und somit die Rechenzeit um Größenordnungen reduzieren - ich denke da an das Rucksackproblem o.ä.

02.05.2010, 10:05

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
"Genauer" ist das nur, wenn du es lediglich auf den obigen Spezialfall 16,16 beziehst.

Ja, das tat ich. Ich hatte irgendwie den Eindruck, dass dies dem Threadersteller nicht bewußt war und das war jetzt keinesfalls als Kritik an dir gedacht...

Zitat:

Original von Arthur Dent
Bei einer Reihe von praxisrelevanten Fragestellungen kann man nämlich den volltändigen Variationsbaum kräftig stutzen und somit die Rechenzeit um Größenordnungen reduzieren - ich denke da an das Rucksackproblem o.ä.

Ja, Branch & Bound nennt sich das (jetzt nur für den Threadersteller, damit er das leichter googeln kann), und tatsächlich scheint mir das auch die einzige Chance zu sein, das Problem, um das es hier geht, in halbwegs annehmbarer Zeit zu bewältigen... Augenzwinkern

Neue Frage »

Antworten »

Fakultätsreihe iterativ optimieren?

Verwandte Themen