Algorithm combination

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

  • Algorithm combination

    Also ich brauche einen Algorithmus der mir alle moeglichen Kombinationen bis zu einem bestimmten Wert liefert!
    z.B. Der max Wert soll 11 sein und array mit Werten {4, 3, 5} soll folgendes liefern:
    4, 4, 3
    4, 3, 3
    3, 4, 4
    3, 3, 5
    3, 3, 3
    3, 4, 3
    5, 4
    5, 3, 3
    (Hoff ich hab alle)

    Also bisher hab ich sowas:

    Quellcode

    1. int arr[4] = {2, 1, 6, 3};
    2. int value = 0;
    3. int tmpV = 0;
    5. for (int i=0; i<c; i++) {
    6. value += arr[i];
    7. tmpV = value;
    8. std::cout << arr[i] << " " << arr[i] << " ";
    10. for (int k=0; k<c; k++) {
    11. if ((value + arr[k]) <= summationsLength) {
    12. value += arr[k];
    13. tmpV = value;
    14. std::cout << arr[k] << " " << arr[k] << " ";
    15. }
    17. for (int j=k; j<c; j++) {
    18. if ((value + arr[j]) <= summationsLength) {
    19. value += arr[j];
    20. std::cout << arr[j] << " " << arr[j] << " ";
    21. }
    22. }
    23. value = tmpV;
    24. }
    25. value = 0;
    26. std::cout << std::endl;
    27. }
    Alles anzeigen


    Leider funktioniert der nicht richtig weis vlt wer ne Loesung??

  • Ich habe den Algorithmus in Python geschrieben, darin gehen mir die Codes schneller von der Hand. Nach C darfst du ihn dann portieren. ;)

    Quellcode

    1. def per(menge, maximum, rekursionen=[]):
    2. for element in menge:
    3. r = rekursionen[:] # Kopie der Liste rekursionen erstellen
    4. r.append(element)
    6. if sum(r) <= maximum:
    7. print r,
    8. per(menge, maximum, r) # Rekursiver Aufruf

    An deinem Beispiel angewandt:

    Quellcode

    1. >>> per([3, 4, 5], 11)
    2. [3] [3, 3] [3, 3, 3] [3, 3, 4] [3, 3, 5] [3, 4] [3, 4, 3] [3, 4, 4] [3, 5] [3, 5, 3] [4] [4, 3] [4, 3, 3] [4, 3, 4] [4, 4] [4, 4, 3] [4, 5] [5] [5, 3] [5, 3, 3] [5, 4] [5, 5]

    Listet alle Kombinationen bzw. Permutationen auf, deren Summe kleiner gleich 11 ist. Kann man aber sicherlich noch optimieren.

  • Danke fuer die Antwort leider hab ich noch nie Python programmiert...
    Habs versucht umzusetzen komm auf sowas:

    Quellcode

    1. int COUNT = 0;
    2. void permutation(int m[], int max, int *v) {
    4. int size = (sizeof(m)/sizeof(*m));
    5. for (int i=0; i<size; i++) {
    7. int *k = new int[size];
    8. k = v;
    9. k[COUNT] = m[COUNT];
    10. COUNT++;
    12. int sum = 0;
    13. int j=0;
    14. int s = (int) sizeof(k)/sizeof(*k);
    15. while (j < s) {
    16. sum+=k[j];
    17. j++;
    18. }
    20. if (sum <= max) {
    21. int w=0;
    22. while (w < s) {
    23. std::cout << k[w];
    24. w++;
    25. }
    26. }
    27. std::cout << std::endl;
    28. permutation(m, max, k);
    29. }
    30. }
    Alles anzeigen


    Funktioniert aber nicht weis vlt wer wo der Fehler liegt?

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von Freaky256 ()