Kombination von 5 versch. Zahlen

[Gerald Hofbauer]

Hallo Forumsmitglieder,

ich stehe hier eigentlich vor einem kleinem Problem, aber ich komme jedesmal durcheinander.

Ich muss aus 5 Zahlen:
1,2,3,4,5
alle möglichen Kombinationen erstellen, also:
1+2+3+4+5
1+2+3+4
1+2+3
2+3+4+5
2+3+4
...

Ich checke dies einfach nicht und komme jedesmal durcheinander.

Gibt es da ein kleines Helfertool, oder eine einfache math. Formel?

Mit freundlichen Grüssen
Gerald Hofbauer

[the-FoX]

helfen da nicht verschatelte for-schleifen ?!?
for (i=1;i<6;i++)
  for (j=1;j<6;j++)
    for (k=1;k<6;k++)
      for (l=1;l<6;l++)
        for (m=1;m<6;m++)
         print(i + j + k + l + m )

....

ist jetzt nur pseudocode.

[fastix®]

Moin!

helfen da nicht verschatelte for-schleifen ?!?

und tests...

for ($i=1;$i<6;$i++) {
  for ($j=1;$j<6;$j++) {
    if ($j != $i) {
      for ($k=1;$k<6;$k++) {
        if (($k != $i) and ($k != $j)) {
          for ($l=1;$l<6;$l++) {
            if (($l !=$i) and ($l != $j) and ($l != $k)) {
              for ($m=1;$m<6;$m++) {
                if (($m != $i) and ($m !=$j) and ($m != $k)and ($m != $l)) {
                  $z=$i*10000 + $j*1000 + $k*100 + $l*10 + $m;
                  echo $z;
                }
              }
            }
          }
        }
      }
    }
  }
}

MFFG (Mit freundlich- friedfertigem Grinsen)

fastix®

[fastix®]

Moin!

ok. Ich sah gerade: auch die kürzeren Kombinationen. kein Problem.

for ($i=1;$i<6;$i++) {
  $z=$i;
  echo $z;
  for ($j=1;$j<6;$j++) {
    if ($j != $i) {
      $z=$i*10 + $j*1;
      echo $z;
      for ($k=1;$k<6;$k++) {
        if (($k != $i) and ($k != $j)) {
          $z=$i*100 + $j*10 + $k*1;
          echo $z;
          for ($l=1;$l<6;$l++) {
            if (($l !=$i) and ($l != $j) and ($l != $k)) {
              $z=$i*1000 + $j*100 + $k*10 + $l*1;
              echo $z;
              for ($m=1;$m<6;$m++) {
                if (($m != $i) and ($m !=$j) and ($m != $k)and ($m != $l)) {
                  $z=$i*10000 + $j*1000 + $k*100 + $l*10 + $m;
                  echo $z;
                }
              }
            }
          }
        }
      }
    }
  }
}

MFFG (Mit freundlich- friedfertigem Grinsen)

fastix®

[Gerald Hofbauer]

Hallo fastix®,

danke für deine Lösung, aber ich hätte dazusagen sollen, dass die Kombinationen nur 1 mal vorkommen dürfen, also:
12345
aber dann nicht mehr
54321

Wie müssen deine for-Schleifen umgewandelt werden, damit ich es richtig hinbekomme?

Mit freunlichen Grüssen
Gerald Hofbauer

[fastix®]

Moin!

Hallo fastix®,

danke für deine Lösung, aber ich hätte dazusagen sollen, dass die Kombinationen nur 1 mal vorkommen dürfen, also:
12345
aber dann nicht mehr
54321

Dann wird es kürzer:

for ($i=1;$i<6;$i++) {
  $z=$i;
  echo $z."<br>";
  for ($j=$i+1;$j<6;$j++) {
    $z=$i*10 + $j*1;
    echo $z."<br>";
    for ($k=$j+1;$k<6;$k++) {
      $z=$i*100 + $j*10 + $k*1;
      echo $z."<br>";
      for ($l=$k+1;$l<6;$l++) {
        $z=$i*1000 + $j*100 + $k*10 + $l*1;
        echo $z."<br>";
        for ($m=$l+1;$m<6;$m++) {
          $z=$i*10000 + $j*1000 + $k*100 + $l*10 + $m;
          echo $z."<br>";
        }
      }
    }
  }
}

Überlege mal, warum....

MFFG (Mit freundlich- friedfertigem Grinsen)

fastix®

[Gerald Hofbauer]

Hallo fastix®,

danke für die Hilfe.
Genau dies ist die Lösung.

Werd mir mal genauer den Kopf darüber zerbrechen.

Mit freundlichen Grüssen
Gerald Hofbauer

[Charlie]

Hallo Gerald,

Ich muss aus 5 Zahlen:
1,2,3,4,5
alle möglichen Kombinationen erstellen, also:

Um die Anzahl der Kombinationsmöglichkeiten zu erhalten nimm diese Formel:
2hoch(Anhal der Zahlen)-1
In deinem Fall ist dies 31.

Wie du die Kombinationsmöglichkeiten am leichtesten erstellst, kann ich dir auf die schnelle leider auch nicht verraten.

lg
Charlie

[Martin Hölter]

Hi!

Um die Anzahl der Kombinationsmöglichkeiten zu erhalten nimm diese Formel:
2hoch(Anhal der Zahlen)-1
In deinem Fall ist dies 31.

Hä?

Ist das nicht einfach n! ? Also bei 5 wäre das dann 5*4*3*2*1=120

Gruß aus Iserlohn

Martin

[Charlie]

Hallo Martin,

Ist das nicht einfach n! ? Also bei 5 wäre das dann 5*4*3*2*1=120

Ich hab ja geschrieben:

2hoch(Anhal der Zahlen)-1

Also 2hoch5(weil es ja fünf Zahlen sind)-1 = 31

lg
Charlie

[the-FoX]

Hallo Martin,

Ist das nicht einfach n! ? Also bei 5 wäre das dann 5*4*3*2*1=120

Ich hab ja geschrieben:

2hoch(Anhal der Zahlen)-1

Also 2hoch5(weil es ja fünf Zahlen sind)-1 = 31

lg
Charlie

Die entscheidende Frage ist doch: Darf jede Zahl nur einmal auftreten in einer Kombination oder x mal. Also ist  1 1 1 1 1 gültig oder nicht

[Ashura]

Hallo Martin.

Ist das nicht einfach n! ? Also bei 5 wäre das dann 5*4*3*2*1=120

Nein:

Ich muss aus 5 Zahlen:
1,2,3,4,5
alle möglichen Kombinationen erstellen, also:
1+2+3+4+5
1+2+3+4
1+2+3
2+3+4+5
2+3+4

Es können also auch Kombinationen vorkommen, in denen nicht alle Zahlen enthalten sind.

Einen schönen Montag noch.

Gruß, Ashura

[Daniel Thoma]

Hallo Ashura,

Es können also auch Kombinationen vorkommen, in denen nicht alle Zahlen enthalten sind.

Das ist der eine Punkt, aber es scheint auch so zu sein, als würde die Reihenfolge der Zahlen keine rolle spielen.
D.h. er will einfach alle möglichen Teilmengen von {1,2,3,4,5} ohne die leere Menge. Da stimmt 2^n - 1, (die leere Menge hat genau eine, also 2^0 Elemente und wenn man zu einer Menge ein element hinzu tut, verdoppelt man offensichtlich die Anzahl der Teilmengen. Jede Teilmenge die es vorher gab, gibt es hinterher einmal mit und einmal ohne das neue Element.)

Wenn die Reihenfolge allerdings eine Rolle spielt, gibt es SUMME VON i = 1 BIS  5 ÜBER ((5 über i) * i!) Kombinationen. Was in diesem Fall 325 wären.
Mag sein, dass sich das noch etwas vereinfachen lässt, aber das ist die Formel, die man auf den ersten Blick sieht.

Für das Teilmengenproblem würde ich diesen Algorithmus nehmen:

function teilmengen(menge) {
  if(menge.length == 0) {
    return new Array(new Array());
  }
  var result = new Array();
  var elem = menge.pop();
  var tm = teilmengen(menge);
  for(var i = 0; i < tm.length; i++) {
    var m = new Array();
    m[0] = elem;
    m = m.concat(tm[i]);
    result.push(m);
  }
  result = result.concat(tm);
  return result;
}

Grüße

Daniel

[Gerald Hofbauer]

Hallo Daniel,

Wenn die Reihenfolge allerdings eine Rolle spielt, gibt es SUMME VON »» i = 1 BIS  5 ÜBER ((5 über i) * i!) Kombinationen. Was in diesem Fall »» 325 wären

Nein da hat Charlie in seinem Posting schon recht gehabt:

Um die Anzahl der Kombinationsmöglichkeiten zu erhalten nimm diese »» »» Formel:
2hoch(Anhal der Zahlen)-1
In deinem Fall ist dies 31.

Es sollen keine doppelte Kombinationen wie zB:
12345
und
54321
vorkommen.

Jede Kombination soll nur 1 mal vorkommen.

lg
Charlie

[Daniel Thoma]

Hallo Gerald,

Jede Kombination soll nur 1 mal vorkommen.

Ja eben die Teilmengen bestimmen. Da spielt die Reihenfolge ja keine Rolle.
Genau das tut der von mir angegebene Algorithmus. Ich glaube, das hast Du nicht erkannt ;-)

Grüße

Daniel

[Daniel Thoma]

Achso, ich hätte evtl. noch ergänzen sollen, dass man das Ding mit einem Array also z.B. alert(teilmengen(new Array(1, 2, 3, 4, 5))); aufrufen muss.

[seth]

gudn tach Daniel!

dein algorithmus ist toll, keine frage!

dennoch moechte ich eine weitere variante nennen.
es geht naemlich auch ohne rekursionen, kuerzer und fuer leute, die mit binaeren zahlen was anfangen koennen, auch leichter verstaendlich:

  
#!/usr/bin/perl -w  
use strict;  
for(my $i=1;$i>>5<1;++$i){  
 for(0..4){  
  print 1+$_ if $i & 2**$_;  
 }  
 print "\n";  
}

prost
seth

[Daniel Thoma]

Hallo seth,

Na, mit Perl bekomme ich meinen aber auch so kurz ;-)

  
#!/usr/bin/perl  
use strict;  
print join("\n", map {join(",", @{$_})} teilmengen(1..5)), "\n";  
sub teilmengen {  
  return @_ ? (map {$_, [$_[0], @{$_}]} teilmengen(@_[1..$#_])) : ([]);  
}  

es geht naemlich auch ohne rekursionen,

Ja, mein Algorithmus ist einfach der in Code gegossene Induktionsbeweis, warum das 2^n Teilmengen sind. Da bietet sich Rekursion zum schnellen Hinschreiben an.

kuerzer und fuer leute, die mit binaeren zahlen was anfangen koennen, auch leichter verstaendlich

als für Leute, die nichts mit binären Zahlen zu tun haben? Dem stimme ich uneingeschränkt zu ;-)

Einfach bis 2^n zu Zählen und die Teilmengen aus den Bitbelegungen zu bestimmen, ist natürlich trickreich.

Grüße

Daniel

[dedlfix]

echo $begrüßung;

Ich muss aus 5 Zahlen:
1,2,3,4,5
alle möglichen Kombinationen erstellen, also:

Gibt es da ein kleines Helfertool, [...] ?

Wie wärs mit MySQL? (Na gut, klein ist das nicht grade.)

CREATE TABLE a (a int);
INSERT INTO a VALUES (1),(2),(4),(8),(16);
SELECT DISTINCT MAKE_SET(a1.a | a2.a | a3.a | a4.a | a5.a, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13) FROM a a1, a a2, a a3, a a4, a a5 ORDER BY 1;

(Irgendwie will das nicht, wenn ich das make_set nur mit 1 bis 5 füttere, aber mit 13 gehts...)

echo "$verabschiedung $name";