Anzeige:
Ergebnis 1 bis 2 von 2

Thema: Algorithmus für Kombinationen gesucht

  1. #1
    Registrierter Benutzer
    Registriert seit
    29.10.2006
    Beiträge
    14

    Algorithmus für Kombinationen gesucht

    Hi,

    das folgende Problem ist sicherlich in der Informatik wohlbekannt und einfach zu lösen, aber ich krieg es grad nicht hin.

    Ich möchte in einem Skript (z.B. mit PHP) alle möglichen Kombinationen von n Variablen ausgeben. Bei 4 Variablen wäre das:

    Code:
    a
    b
    c
    d
    
    ab
    ac
    ad
    bc
    bd
    cd
    
    abc
    abd
    acd
    bcd
    
    abcd
    Es gibt bei
    Code:
    1  2  3  4  .. (Variablen)
    1  3  7  15 .. (Kombinationen)
    Weiß jemand wie dieses Problem benannt wird, und welcher Algorithmus diese Aufgabe löst?

    Danke,
    Andreas

  2. #2
    Registrierter Benutzer
    Registriert seit
    29.10.2006
    Beiträge
    14
    Hab eine Lösung gefunden:

    Code:
    <?php
    
    $n = 5;
    
    function repeatIt($n, $rate) {
      $result=array();
      $val=false;
      $i=0;
      while($i<$n){
        $j=$rate;
        while($j>0) {
          $result[]=$val;
          $j--;
          $i++;
        }
        $val=!$val;
      }
      return($result);
    }
    
    $result=array();
    for ($i=1; $i<=$n; $i++) {
      $result[$i]=repeatIt(pow(2,$n),pow(2,$i-1));
    }
    
    $out = array();
    
    $ncomb=pow(2,$n);
    for ($i=1; $i<$ncomb; $i++) {
      for ($j=1; $j<=$n; $j++) {
        if ($result[$j][$i]>0) $out[$i][]=$j*$result[$j][$i];
      }
    }
    
    sort($out);
    foreach($out as $o) {
      foreach($o as $cell) {
        echo $cell." ";
      }
      echo "\n";
    }
    
    ?>
    liefert:
    Code:
    1 
    2 
    3 
    4 
    5 
    1 2 
    1 3 
    1 4 
    1 5 
    2 3 
    2 4 
    2 5 
    3 4 
    3 5 
    4 5 
    1 2 3 
    1 2 4 
    1 2 5 
    1 3 4 
    1 3 5 
    1 4 5 
    2 3 4 
    2 3 5 
    2 4 5 
    3 4 5 
    1 2 3 4 
    1 2 3 5 
    1 2 4 5 
    1 3 4 5 
    2 3 4 5 
    1 2 3 4 5

Lesezeichen

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •