Permutationen

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Permutationen

    Weiß jemand, wie folgendes Problem zu lösen ist? m Geldbeträge sind auf n Zeitpunkte zu verteilen.
    Beispiel: m=2 (A,B) auf n=3 Zeitpunkte 1,2,3:
    A B
    1 1
    1 2
    1 3
    2 1
    2 2
    2 3
    3 1
    3 2
    3 3
    Es gibt also k = n^m Möglichkeiten.

    Für m=2 kann man alle Permutationen so erzeugen:

    Quellcode

    1. k=0;
    2. for(i=1;i<=n;i++)
    3. {
    4. for(j=1;j<=n;j++)
    5. {
    6. k++;
    7. A[k] = i;
    8. B[k] = j;
    9. }
    10. }

    Aber wie geht das allgemein? Ich kenne ja vorher nicht m, weiß also nicht, wieviele for-Schleifen ich brauche.

    Gibt es eine iterative, NICHT-REKURSIVE Lösung zu diesem Problem?

    Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von osb ()

  • Hallo,

    ich würde dir gerne helfen, allerdings verstehe ich das Programm nicht wirklich.
    Also dass du mehrere Geldbeträge auf mehrere Zeitpunkte verteilen willst, habe ich verstanden,
    aber wenn du 2 Geldbeträge hast, dann kann ja der eine einen Betrag von 50 und der abdere einen Betrag von 45,62 haben.
    Jetzt haben wir dann noch 3 Zeitpunkte. das heißt dass die (insgesamt) 95,62 auf die 3 Zeitpunkte verteilt werden müssen...

    Habe ich das soweit richtig verstanden?
    Aus deiner kleinen Tabelle werde ich einfach nicht schlau.

    Und sollen die Geldbeträge nur aus ganzen Zahlen (also int) bestehen oder dachtest du da an Kommazahlen (also float)?


    MfG, Agent2

  • Hallo, Danke für Deine Antwort. Unten ein Programm, welches das Problem SEHR UNELEGANT löst.

    Es sind auch 10 "Geldbeträge", auf die das Problem dann begrenzt bleibt.

    Ab Zeile 45 wird eine Testausgabe generiert. Daran siehst Du bestimmt, was ich meine.

    Eine andere nicht-rekursive Lösung wäre super.

    Gruß,

    Oliver





    Quellcode

    1. int main(void)
    2. {
    3. int A[N][100000];
    4. int i, j, k;
    5. int z1, z2, z3, z4, z5, z6, z7, z8, z9, z10;
    7. k=0;
    8. for(z1=1;z1<=n;z1++)
    9. {
    10. for(z2=1;z2<=n;z2++)
    11. {
    12. for(z3=1;z3<=n;z3++)
    13. {
    14. for(z4=1;z4<=n;z4++)
    15. {
    16. for(z5=1;z5<=n;z5++)
    17. {
    18. for(z6=1;z6<=n;z6++)
    19. {
    20. for(z7=1;z7<=n;z7++)
    21. {
    22. for(z8=1;z8<=n;z8++)
    23. {
    24. for(z9=1;z9<=n;z9++)
    25. {
    26. for(z10=1;z10<=n;z10++)
    27. {
    28. k++;
    29. A[10][k] = z1;
    30. A[9] [k] = z2;
    31. A[8] [k] = z3;
    32. A[7] [k] = z4;
    33. A[6] [k] = z5;
    34. A[5] [k] = z6;
    35. A[4] [k] = z7;
    36. A[3] [k] = z8;
    37. A[2] [k] = z9;
    38. A[1] [k] = z10;
    39. }
    40. }
    41. }
    42. }
    43. }
    44. }
    45. }
    46. }
    47. }
    48. }
    50. for(i=1;i<=10;i++)
    51. {
    52. for(j=1;j<=3;j++)
    53. {
    54. printf("z%d[%d]=%d ", j, i, A[j]);
    55. }
    56. printf("\n");
    57. }
    59. return EXIT_SUCCESS;
    60. }
    Alles anzeigen

  • Hallo,
    lise dir mal das Fallbeispiel hier durch, das ist super erklärt und auch für Leute die keine Mathematischen vorkenntnisse besitzen.
    magazin.c-plusplus.de/artikel/Permutationen
    Erst wenn der letzte FTP Server kostenpflichtig, der letzte GNU-Sourcecode verkauft, der letzte Algorithmus patentiert, der letzte Netzknoten kommerzialisiert, die letzte Newsgroup moderiert wird, werdet Ihr merken, dass man mit Geld allein nicht programmieren kann.