Hilfe bei Mutation

lima-city → Forum → Programmiersprachen → C/C++ und D

Autor dieses Themas
~~g****e~~
20:25, 29.3.2012
Heyho

Ich hoffe der Titel stimmt, ich betrachte das folgende Problem einfach als Mutation (oder rekursive Kombination?).
Ich komme mit meinen Gedanken und Ideen zu keinem Ergebnis. Vorweg: Ich arbeite mit Qt und C++.
Ich habe einen QVector
```
QVectory<double> list;
list<<20.2<<5.4<<2.1<<3.0<<6.3;
```
So. In meinem konkreten Fall sinds Klassen, welche sich aber genau wie doubles Verhalten in diesem Kontext. Ziel ist es jetzt, dass man diese kombinieren kann, und nicht nur das in beliebiger Zahl, sondern auch in Prozentskalierung. Also von Hand geschrieben:
```
list[0] * 0.9 + list[1] * 0.1;
list[0] * 0.9 + list[2] * 0.1;
list[0] * 0.9 + list[3] * 0.1;
...
list[0] * 0.8 + list[1] * 0.2;
list[0] * 0.8 + list[2] * 0.2;
list[0] * 0.8 + list[3] * 0.2;
...
list[0] * 0.1 + list[1] * 0.9;
list[0] * 0.1 + list[2] * 0.9;
list[0] * 0.1 + list[3] * 0.9;
...
list[1] * 0.9 + list[2] * 0.1;
list[1] * 0.9 + list[3] * 0.1;
list[1] * 0.9 + list[4] * 0.1;
...
list[2] * 0.9 + list[3] * 0.1;
list[2] * 0.9 + list[4] * 0.1;
list[2] * 0.9 + list[5] * 0.1;
```
Das Muster sollte klar sein denk ich. Das ist aber noch nicht alles, das ist Stufe 1.
Stufe 2 sieht so aus, dass ich nun auch haben möchte:
```
list[0] * 0.8 + list[1] * 0.1 + list[2] * 0.1;
list[0] * 0.8 + list[1] * 0.1 + list[3] * 0.1;
list[0] * 0.8 + list[1] * 0.1 + list[4] * 0.1;
...
list[0] * 0.8 + list[2] * 0.1 + list[3] * 0.1;
```
Und das ganze soweit bis maximal 10 Einträge:
```
list[0] * 0.1 + list[1] * 0.1 + list[2] * 0.1 + list[3] * 0.1 .... + list[9] * 0.1;
```
Die Faktoren 0.1 bis 0.9 entsprechen, wie man sich nun vllt erschließen kann, den Prozenten in 10ner Schritten (also 10%, 20% ... 80%, 90%), und gesamt halt 100%. Die Ergebnisse werden allerdings in einen Ergebnisvector geschrieben, hier mal nicht betrachtet. Diese werden für diese Kombinationskram nicht beachtet.

Ich hoffe, das Problem ist verstanden, wenn nicht unbedingt nachfragen. Ich bin mit meinem Gedankengut jetzt schon mindestens eine Woche daran, und überlege, wie ich das wohl gestallten mag, nur komm ich einfach nicht weiter.

Ich hoffe es kann jemand helfen. Danke schonmal
Liebe Grüße
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

lima-city: Gratis werbefreier Webspace für deine eigene Homepage
hackyourlife

Moderator

hackyourlife hat kostenlosen Webspace.

20:44, 29.3.2012
Du möchtest das also von möglichst 2 Zeilen Code in einer Schleife ausführen?
Autor dieses Themas
~~g****e~~

21:17, 29.3.2012
Nein, dass das keine wenigen Zeilen sind ist relativ logisch. Das wird vermutlich über mehrere Schleifen gehen, nur habe ich keinen Durchblick mehr. Und der QVector ist so btw auch nicht immer gleich groß, mal hat er 5 einträge, mal 1000. Darum sind die Kombinationsmöglichkeiten usw variabel, ich muss sie also erstellen lassen. Nur bin ich irgendwie wohl zu blöd das zu rallen...

Liebe Grüße

Moderator

21:36, 29.3.2012

Ich hab jetzt ein Programm geschrieben das dir dein Muster ausgibt.
Lass es mal laufen und schau ob es das ist was du willst (gibt sowas aus was du vorher gepostet hast).

Wenn es passt: ersetz die printf-Zeilen durch deine Berechnungen (die sonst ausgegeben werden).

int length = 10; // Anzahl der Elemente
printf("Muster 1\n");
for(int i = 0; i < length; i++)
	for(float step = 0.1f; step < 1.0f; step += 0.1f)
		for(int j = i + 1; j < length; j++)
			printf("list[%i] * %1.1f + list[%i] * %1.1f\n", i, 1.0f - step, j, step);
printf("Muster 2\n");
for(int i = 0; i < length; i++)
	for(int j = i + 1; j < length; j++)
		for(int k = j + 1; k < length; k++)
			printf("list[%i] * %1.1f + list[%i] * %1.1f + list[%i] * %1.1f\n", i, 0.8f, j, 0.1f, k, 0.1f);

(OK, es sind 11 Zeilen geworden :biggrin:

)

Autor dieses Themas
~~g****e~~

22:57, 29.3.2012
Ne, das kommt nicht ganz auf das hinaus, was ich brauche. Mein Fehler, ich habs wohl nicht richtig ausgedrückt.
Das alles soll nicht in 2 Mustern berechnet werden, sondern das soll ein Vector als Ergebnis haben, in dem die Ergbnis doublewerte sind.

Um es in die Praxis zu heben: Ich habe Lichtquellen, welche ich unterschiedlich Stark kombinieren möchte. Die Doublewerkte repräsentieren die Lichter. Es sind zwischen 2 bis 10 Lichtquellen mischbar, welche jeweils (also jede quelle einzelnd) zu einem gewissen Prozentsatz zum Gesamtlicht beitragen, dabei sind die prozentualen Beiträge alle glatte 10% Beträge, also 10%, 20%, 30% usw. sodass das Licht nachher gemischt wird. Dies wird über ein addieren der einzelnen Anteile erreicht. Doch dafür muss ich alle möglichen Kombinationen natürlich berechnen, um sie dann gegeneinander zu vergleichen.

Vielleicht macht dies Praxisbeispiel das Porblem ein wenig anschaulicher, hoffe ich.

Liebe Grüße

darkpandemic

darkpandemic hat kostenlosen Webspace.

20:23, 30.3.2012

Hallo ggamee,

auf den ersten Blick sieht Dein Problem aus wie eine simple Matrix-Multiplikation.
Wenn Du im Allgemeinen n Lichter und m Ergebnis-Kombinationen haben willst, dann kannst Du Deine Liste als n-elementigen Vektor auffassen. Das Ergebnis soll ein m-elementiger Vektor sein, der die gewünschten Kombinationen enthält. Was Du noch benötigst ist die Gewichts-Matrix, welche die Werte zwischen 0.0 und 1.0 enthält. Diese muss jetzt eine m x n-Matrix sein. Z.B:
Lichintensitäten der Lichtquellen (die Liste / 3 Stück):
$Formel: \vec{L}=\left( \begin{array}{c} 1.0 \\ 2.0 \\ 1.5 \end{array} \right)$
Wenn man zwei Ergebnisse haben will, dann muss die Gewichts-Matrix die Größe 2x3 haben:
$Formel: A = \left( \begin{array}{ccc} 0.8 & 0.1 & 0.1 \\ 0.5 & 0.0 & 0.5 \end{array} \right)$
Die Zeilen von A sind die Gewichte, die Du in der Summe mit den einzelnen Summanden multiplizierst. Wenn ein Licht in einer Summe nicht berücksichtigt werden soll, dann wird der zugehörige Eintrag in der Matrix einfach auf 0.0 gesetzt. Und schon hat man nur noch eine Teilsummen.
Das Ergebnis ist dann einfach:
$Formel: \vec{C} = A\cdot\vec{L} = \left( \begin{array}{ccc} 2.5\\ 1.25 \end{array} \right)$
An Deiner Stelle würde ich einfach eine Funktion/Methode schreiben, die die Liste und eine Matrix entgegennimmt, die Matrix-Multiplikation durchführt und das Ergebnis als Liste zurückgibt.

Edit: Mir ist aufgefallen, dass das Problem wohl das erstellen der Gewichts-Matrix für alle möglichen Kombinationen ist. Also hier noch etwas Code dazu:

/* compute binomial coeff */
int binomial(int n, int k)
{
  int i, dividend, divisor;

  dividend = 1;
  divisor = 1;

  for(i=k+1;i<=n;i++)
    dividend *= i;

  for(i=2;i<=(n-k);i++)
    divisor *= i;

  return dividend/divisor;
}

/* compute weights */
int get_weights_recursion(DblMatrix m, int current_row, int max_column, int max_weight)
{
  int i, j, next_row;

  /* return if first row is reached */
  if(!max_column)
  {
    m[current_row][0] = max_weight;
    return current_row + 1;
  }

  /* from 0 to maximum weight */
  for(i=0;i<=max_weight;i++)
  {
    /* distribute the remaining weights */
    next_row = get_weights_recursion(m, current_row, max_column-1 ,max_weight-i);

    /* fill max column with current weight */
    for(j=current_row; j<next_row; j++)
      m[j][max_column] = i;

    current_row = next_row;
  }

  return current_row;
}

DblMatrix get_weights(int light_count)
{
  int i, row_count, current_row;
  DblMatrix result;
  
  /* compute row count of matrix */
  row_count = binomial(light_count+9, 10); /* N+k-1 over k */

  /* create matrix */
  result = DblMatrix_Create(row_count, light_count);

  /* get weights */
  get_weights_recursion(result, 0, light_count-1, 10);

  /* scale weights down to [0.0;1.0] */
  DblMatrix_MulScalar(result, 0.1);

  /* return result */
  return result;
}

Das Verteilen von 10-tel Gewichten entspricht einem "Ziehe mit Zurücklegen" (wahrscheinlichkeits-theoretisch ausgedrückt). Daher hat die Matrix
$Formel: \left( \begin{array}{c} N+k-1 \\ k \end{array} \right)$
(Binomialkoeffizient!) Zeilen. Die Berechnung der Gewichte kann dann rekursiv erfolgen in dem man erst alles auf die erste Spalte verteilt, dann auf die ersten beiden Spalten, dann auf drei usw. bis man alles hat.
Ich habe es jetzt mal mit C geschrieben. Aber ich denke, dass kann man leicht in C++ nachprogrammieren.
Für drei Lichter kommt z.B. folgendes raus:

/  1.0000    0.0000    0.0000   \
|  0.9000    0.1000    0.0000   |
|  0.8000    0.2000    0.0000   |
|  0.7000    0.3000    0.0000   |
|  0.6000    0.4000    0.0000   |
|  0.5000    0.5000    0.0000   |
|  0.4000    0.6000    0.0000   |
|  0.3000    0.7000    0.0000   |
|  0.2000    0.8000    0.0000   |
|  0.1000    0.9000    0.0000   |
|  0.0000    1.0000    0.0000   |
|  0.9000    0.0000    0.1000   |
|  0.8000    0.1000    0.1000   |
|  0.7000    0.2000    0.1000   |
|  0.6000    0.3000    0.1000   |
|  0.5000    0.4000    0.1000   |
|  0.4000    0.5000    0.1000   |
|  0.3000    0.6000    0.1000   |
|  0.2000    0.7000    0.1000   |
|  0.1000    0.8000    0.1000   |
|  0.0000    0.9000    0.1000   |
|  0.8000    0.0000    0.2000   |
|  0.7000    0.1000    0.2000   |
|  0.6000    0.2000    0.2000   |
|  0.5000    0.3000    0.2000   |
|  0.4000    0.4000    0.2000   |
|  0.3000    0.5000    0.2000   |
|  0.2000    0.6000    0.2000   |
|  0.1000    0.7000    0.2000   |
|  0.0000    0.8000    0.2000   |
|  0.7000    0.0000    0.3000   |
|  0.6000    0.1000    0.3000   |
|  0.5000    0.2000    0.3000   |
|  0.4000    0.3000    0.3000   |
|  0.3000    0.4000    0.3000   |
|  0.2000    0.5000    0.3000   |
|  0.1000    0.6000    0.3000   |
|  0.0000    0.7000    0.3000   |
|  0.6000    0.0000    0.4000   |
|  0.5000    0.1000    0.4000   |
|  0.4000    0.2000    0.4000   |
|  0.3000    0.3000    0.4000   |
|  0.2000    0.4000    0.4000   |
|  0.1000    0.5000    0.4000   |
|  0.0000    0.6000    0.4000   |
|  0.5000    0.0000    0.5000   |
|  0.4000    0.1000    0.5000   |
|  0.3000    0.2000    0.5000   |
|  0.2000    0.3000    0.5000   |
|  0.1000    0.4000    0.5000   |
|  0.0000    0.5000    0.5000   |
|  0.4000    0.0000    0.6000   |
|  0.3000    0.1000    0.6000   |
|  0.2000    0.2000    0.6000   |
|  0.1000    0.3000    0.6000   |
|  0.0000    0.4000    0.6000   |
|  0.3000    0.0000    0.7000   |
|  0.2000    0.1000    0.7000   |
|  0.1000    0.2000    0.7000   |
|  0.0000    0.3000    0.7000   |
|  0.2000    0.0000    0.8000   |
|  0.1000    0.1000    0.8000   |
|  0.0000    0.2000    0.8000   |
|  0.1000    0.0000    0.9000   |
|  0.0000    0.1000    0.9000   |
\  0.0000    0.0000    1.0000   /

Beitrag zuletzt geändert: 30.3.2012 21:37:43 von darkpandemic

Autor dieses Themas
~~g****e~~

15:52, 31.3.2012
Du hast mein Problem erfasst darkpandemic.
Leider verstehe ich dein Code nicht ganz, das liegt aber daran, dass ich mit Rekursionen einfach nicht klarkomme. Ich verstehe sie nicht richtig. Aber du hast mir genau den richtigen und wichtigen wink gegeben: Matrizenrechnung! Und die Gewichtsmatrix war mein Problem. Als ich das ganze heute morgen aber von Hand eintippen wollte (alle kombinationen) ist mir etwas aufgefallen, unzwar habe ich da das Schema erkannt und kann es nun durchiterieren. Gab zwar einige Probleme von meinem PHP Prototypen nach C++, weil doubles in for-Schleifen Fehler verursachen, aber so hab ich was neues gelernt. Jetzt muss ich nurnoch die Multiplikation schreiben, und das sollte laufen.

Danke für den Gedankenanstoß! Der war einfach ideal!

Liebe Grüße
darkpandemic

darkpandemic hat kostenlosen Webspace.
21:16, 31.3.2012
Hallo ggamee,

dass die Idee hilfreich war freut mich.
Und dass Du einen eigenen Weg gefunden hast ist hervorragend, denn Konzepte, die man sich selber erarbeitet hat, bleiben einem im Gedächtnis, im Gegensatz zu den Dingen die man einfach nur abschreibt oder halbherzig nachvollzieht
Aber dennoch will ich versuchen, ob ich es nicht schaffe, die Rekursion so zu erklären, dass sie verstehbar ist:
Also für den Fall, dass man nur ein Licht hat ist die Sache wohl klar. Dann muss das Ergebnis eine 1x1-Matrix mit Eintrag 1.0 sein.
Wenn man zwei Lichter hat, dann ist die Sache auch noch einfach. Wenn in der ersten Spalte ein Gewicht w eingetragen ist, dann muss in der zweiten Spalte der Wert 1.0-w stehen. Desweiteren müssen in der ersten Spalte alle Werte von 0.0 bis 1.0 eingetragen werden. Das ganze lässt sich noch durch eine Schleife lösen (iteriere w und trage w und 1.0-w in die Matrix ein).
Ab drei Lichtern wird die Sache langsam interessant. Ab jetzt ist es besser, wenn man von rechts nach links, also von Spalten mit hohem zu Spalten mit niedrigem Index vorgeht.
Am Anfang hat man ja 10 Gewichte mit einem Wert von jeweils 0.1 zu verteilen.
Gestartet wird in der ersten Zeile mit der dritten Spalte. Man weiß, dass in der dritten Spalte alle Werte zwischen 0.0 und 1.0 vorkommen müssen. Also benötigt man eine Schleife, die von 0.0 bis 1.0 geht:
```
for(i=0;i<=max_weight;i++)
{
  ...
}
```
Wenn in der dritten Spalte der Wert 0.0 eingetragen wird, dann können noch 10 mal 0.1 Werte in den links davon liegenden Spalten eingetragen werden. Wenn in der dritten Spalte der Wert 0.1 eingetragen ist, dann kann man noch 0.9 auf die erste und zweite Spalte verteilen, für 0.2 in der dritten Spalte bleiben 0.8 für die anderen beiden und so weiter.
D.h. die Funktion setzt den Wert einer Spalte und ruft sich dann mit dem restlichen Gewicht für die links davon liegenden Spalten wieder auf:
```
get_weights_recursion(m, current_row, max_column-1 ,max_weight-i);
```
Wenn die Funktion für die erste Spalte aufgerufen wird, dann können keine Gewichte mehr nach links weitergegeben werden. Daher kann man nur noch das übrige Gesamtgewicht in die Matrix eintragen und dann zurückkehren:
```
if(!max_column)
{
  m[current_row][0] = max_weight;
  return current_row + 1;
}
```
Da man nicht weiß, wie viele Zeilen verwendet werde, wenn man die Gewichte nach links weiterreicht, muss die rekursive Funktion den Index der nächsten unbesetzen Zeile zurückgeben. In der ersten Spalte erhöht sich der Index immer um Eins, für weiter rechts liegende Spalten entspricht die Zeilenanzahl der Anzahl der Aufrufe der Funktion für die erste Spalte. D.h. nur die erste Spalte muss den Zeilenzähler erhöhen. Andererseits weiß die aufrufende Funktion anhand des Rückgabewertes, wie oft sie Ihr aktuelles Gewicht, also den Teil, welchen sie nicht nach links weitergereicht hat in die Matrix eintragen muss:
```
for(j=current_row; j<next_row; j++)
  m[j][max_column] = i;
```
Damit ist dann alles getan, was zu tun war.
Ich hoffe, jetzt ist es nachvollziehbar. Vielleicht findest Du ja auch mal gefallen an Rekursionen.
Autor dieses Themas
~~g****e~~

15:36, 3.4.2012
Hmm, also das Grundkonzept ist also das, dass du quasi sagst "mein Rest ist noch 50%, den Teil auf den nächsten auf!", und der dann dementsprechend wieder die Funktion zum aufteiln aufruft, bis es alles aufgeteilt ist. So habe ich das ungefähr rausgelesen, und das ist natürlich auch ne gute Möglichkeit. So mache ich es nun eigentlich auch, bloß halt als Iteration. Ein Freund von Rekursionen werd ich nicht so recht glaub ich, die sind nicht sooo mein Fall. Aber danke für die Aufklärung :) Werd ich immer wieder dran zurückdenken.

Liebe Grüße
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

lima-city: Gratis werbefreier Webspace für deine eigene Homepage

Dir gefällt dieses Thema?

Über lima-city

lima-city bietet dir kostenlosen und werbefreien Speicherplatz für Deine Homepage. Sofort anmelden und direkt loslegen mit Webspace, PHP, Datenbanken, günstigen Domains und einer tollen Community!

kostenloser Webspace werbefrei: lima-city