[sparrow]

Ich stehe hier gerade total auf dem Schlauch.


Angenommen ich habe den Wert 15 und eine Zahlenreihe von 1 bis 10
Nun möchte ich alle Konstellationen der Zahlenreihe (also: 1+1, 1+2, 2+2, 6+7+8, 3+9, 1+9) durchproboeren bis ich auf 15 komme oder alle Konstellationen durch habe.


Irgendwie fehlt mir gerade der Durchblick das zu tun...
Wie geh ich da vor?


*schlauchsteher*

sparrow

[Gottzilla]

Hat die Zahlenreihe ein bestimmtes Format (also z. B. Array o. ä.) oder ist das egal?

[edit] Dürfen Zahlen doppelt vorkommen, also praktisch 1+1+1+2?

[robo47]

ich schreibs mal als php-code

PHP-Code:

<?php
error_reporting(E_ALL);
$wertebereich = array(1,2,3,4,5,6,7,8,9,10);
$wunschergebnis = 15;
$wertepaare = array();
foreach($wertebereich as $wert1)
{
    foreach($wertebereich as $wert2)
    {
          if ( $wert1 + $wert2 == $wunschergebnis)
          {
              $temp = array();
              $temp[1] = $wert1;
              $temp[2] = $wert2;
              $wertepaare[] = $temp;
              echo $wert1.' + '.$wert2.' = '.$wunschergebnis.'<br />'."\n";
          }
    }
}
?>

dann hat man in $wertepaare alle ergebnisse, allerdings hat man auch die doppelten die müsste man wenn das gewünscht ist, noch filtern.

in aktion: http://robo47.net/public/developersg...rtebereich.php

EDIT:

ich seh grad das macht nur für 2 zahlen das ganze, nicht ganz das gewünschte ergebnis

mfg
robo47

[sparrow]

Zitat von Gottzilla

Hat die Zahlenreihe ein bestimmtes Format (also z. B. Array o. ä.) oder ist das egal?

Ja, sagen wir es sind Werte in einem Array.

Zitat von Gottzilla

[edit] Dürfen Zahlen doppelt vorkommen, also praktisch 1+1+1+2?

Nein, Zahlen dürfen nicht doppelt verwendet werden.
Also: 1+1+1+2 geht nicht.
Ich geh jetzt einfach mal davon aus, dass die "Zahlenreihe" die Indexnummer eines Arrays ist.

Zitat von robo47

ich seh grad das macht nur für 2 zahlen das ganze, nicht ganz das gewünschte ergebnis

Stimmt leider. Nur 2 Zahlen reicht mir leider nicht.


Man muss sich das ganze so vorstellen:
Ich habe eine Zahl (15) und ganze viele andere (in dem Array mit der Länge 20). Nun möchte ich alle Werte aus dem Array miteinander summieren, alle Möglichkeiten durchspielen und dann entweder:

1. Eine Kostellation finden die 15 ergibt und darauf reagieren
2. Wenn alle Kombinationen durchprobiert sind abbrechen bzw. den Ablauf des Programms anderweitig fortsetzen.

[Gottzilla]

Schau mal ob das sowas ist, was du suchst. Funktioniert aber momentan nur mit Zahlen die bei 1 Anfangen und lückenlos bis n weitergehen.

public class Konstellation {
 
 private int wert = 0;
 private int[] zahlen = null;
 
 public void setWert(int wert) {
  
  this.wert = wert;
 }
 
 public void setZahlen(int ... zahlen) {
  
  this.zahlen = zahlen;
 }
 
 public void execute() {
  
  for (int i = 0; i < zahlen.length; i++) {
   iterate(new int[] {zahlen[i]});
  }
 }
 
 private void iterate(int[] curLine) {
  
  int cur = 0;
  int[] newLine = new int[curLine.length + 1];
  for (int j = curLine[curLine.length -1]; j < zahlen.length; j++) {
   cur = 0;
   for (int k = 0; k < curLine.length; k++) {
    newLine[k] = curLine[k];
    cur += curLine[k];
   }
   newLine[curLine.length] = zahlen[j];
   cur += zahlen[j];
   if (cur == wert) {
    System.out.print(newLine[0]);
    for (int k = 1; k < newLine.length; k++) {
     System.out.print("+" + String.valueOf(newLine[k]));
    }
    System.out.println("=" + String.valueOf(cur));
   }
   iterate(newLine);
  }
 }
  
 public static void main(String[] args) {
  
  Konstellation konst = new Konstellation();
  konst.setWert(15);
  konst.setZahlen(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
  konst.execute();
 }
}

[sparrow]

Tja... son mist, hab hier in der Firma augenblicklich nicht mal einen Java-Compiler.

Außerdem brauch ich das Ding als Excel-Code... den Bau ich mir schon selber, wenn ich den Ansatz verstanden habe

[Gottzilla]

Ergebnis wäre folgendes:

1+2+3+4+5=15
1+2+3+9=15
1+2+4+8=15
1+2+5+7=15
1+3+4+7=15
1+3+5+6=15
1+4+10=15
1+5+9=15
1+6+8=15
2+3+4+6=15
2+3+10=15
2+4+9=15
2+5+8=15
2+6+7=15
3+4+8=15
3+5+7=15
4+5+6=15
5+10=15
6+9=15
7+8=15

Code verstanden oder besteht Erklärungsbedarf (bzw. macht er überhaupt das, was du möchtest? Könnte wenn du willst zum Test das ganze noch mit ein paar Anderen Zahlen durchlaufen lassen!?)?

[sparrow]

Ok, Gott der API

könntest du den Code noch so ändern, dass er gar nicht gegen einen Wert prüft sondern einfach nur alle Konstellationen die er gerade durchprobiert ausgibt.

Und ein paar Kommentare einfügen?

Das wäre supi nett

[Gottzilla]

Hab den Code mal ein bisschen erweitert. Jetzt kannst du auch x-beliebige Zahlen in einer x-beliebigen Reihenfolge übergeben. Außerdem ist das Umschreiben auf andere Datentypen (z. B. Strings) nur ein kleiner Aufwand.

PHP-Code:

public class Konstellation {
 
 private int wert = 0;
 private int[] zahlen = null;
 private boolean drawMatch = true;
 
 public void setWert(int wert) {
  
  this.wert = wert;
 }
 
 public void setZahlen(int ... zahlen) {
  
  this.zahlen = zahlen;
 }
 
 public void setDrawMatch(boolean drawMatch) {
  
  this.drawMatch = drawMatch;
 }
 
 public void execute() {
  
  // Geht jedes Element in "zahlen" durch
  for (int i = 0; i < zahlen.length; i++) {
   // ruft die Methode "iterate" mit der gerade ausgwählten Zahl und
   // einer Positionsangabe die auf eine Stelle nach der, der Zahl zeigt
   iterate(new int[] {zahlen[i]}, i + 1);
  }
 }
 /**
  * Erwartet einen Teil des Arrays "zahlen" und eine Positionsangabe, wo sich
  * die letzte Zahl des Subarrays in "zahlen" befindet.
  *
  * Funktionsweise:
  *
  * In einer Schleife wird das aktuelle Subarray um jedes Element, welches im
  * Array "zahlen" nach der Variablen "pos" kommt erweitert, überprüft und
  * ausgegeben. Anschließend wird diese Funktion rekursiv mit dem neuen Subarray
  * und der neuen Position (erhöht um den Faktor 1) aufgerufen. 
 */
 private void iterate(int[] curLine, int pos) {
  
  // Counter falls auf ein Ergebnis geprüft werden soll
  int cur = 0;
  // In newLine wird die als nächstes zu bearbeitende Zeile gespeichert,
  // deshalb ist das Array um 1 groeßer als die aktuelle Zeile curLine
  int[] newLine = new int[curLine.length + 1]; 
  for (int j = pos; j < zahlen.length; j++) {
   // Counter für jeden neuen Durchlauf auf 0 setzen
   cur = 0;
   System.out.print("Moeglichkeit: ");
   // Gibt die momentan zu bearbeitende Zeile aus und schreibt sie in
   // die Variable newLine
   for (int k = 0; k < curLine.length; k++) {
    System.out.print(curLine[k] + "+");
    newLine[k] = curLine[k];
    cur += curLine[k];
   }
   System.out.println(zahlen[j]);
   // Added die letzte Zahl zu newLine
   newLine[curLine.length] = zahlen[j];
   cur += zahlen[j];
   // Alles in dieser if ist einzig und allein für die Ausgabe im Falle
   // eines Treffers
   if (drawMatch && cur == wert) {
    System.out.print("Treffer: ");
    System.out.print(newLine[0]);
    for (int k = 1; k < newLine.length; k++) {
     System.out.print("+" + String.valueOf(newLine[k]));
    }
    System.out.println("=" + String.valueOf(cur));
   }
   // Ruft iterate mit der neuen "Ausgangssituation" auf, passt gleich-
   // zeitig die Position an die neue Situation an
   iterate(newLine, ++pos);
  }
 }
 
 public static void main(String[] args) {
  
  Konstellation konst = new Konstellation();
  konst.setWert(15);
  konst.setZahlen(1,2,3,4,5,6,7,8,9,10);
  konst.setDrawMatch(false);
  konst.execute();
 }
} 


Hoffe du kommst damit klar, ansonsten einfach fragen

[Waq]

Nuja, die Variante zeigt wohl eher die Hässlichkeit imperativer Algorithmen... hier mal ein einfaches rekursives Backtracking.
Dies trifft bei jedem Schritt nur eine Entscheidung, ob die aktuelle Zahl aufsummiert oder weggelassen werden soll, und macht für beide Varianten einen Rekursionszweig.

PHP-Code:

<?php
$zielSumme = 15;
$bausteine = range (1,10); //array mit Zahlen von 1 bis 10

function findResult ($bausteine,$zielSumme) {
    //start: Summe 0 und noch alle Bausteine
    $res = branch (0,array(),$bausteine,$zielSumme);
    var_dump($res); //Ergebnis ausgeben
}

function branch ($zwischenSumme,$zwischenSummanden,$bausteine,$zielSumme) {
    if (empty($bausteine)) //Terminationsbedingung
        return array();

    $zahl = array_shift($bausteine); //erste Zahl aus Array entfernen

    //lokale Werte: zwischen-Summe und Summanden incl. $zahl
    $summe = $zwischenSumme + $zahl;
    $summanden = $zwischenSummanden;
    array_push($summanden,$zahl);

    //Zweig ohne Zahl
    $res1 = branch($zwischenSumme,$zwischenSummanden,$bausteine,$zielSumme);
    //Zweig mit Zahl
    $res2 = branch($summe,$summanden,$bausteine,$zielSumme);

    if ($summe == $zielSumme) 
        array_unshift($res1,$summanden); //Summanden auf Ergebnis schieben
    return array_merge($res1,$res2);
}

findResult ($bausteine,$zielSumme);
?>