[PHP] Alle mogelijke combinaties van array weergeven

[mrbombastic]

Ik heb een array met 8 elementen.
De bedoeling is dat de gebruiker kan aangeven hoeveel elementen hij uit die 8 wil halen en hiervan moeten dan alle mogelijke combinaties weergegeven worden.
Ik heb al wel een manier gevonden om dit te realiseren maar deze is zwaar inefficient.
Het moet ook met een functie kunnen maar dat lukt me maar niet.

Inefficiente code:

code:

<?php
error_reporting(E_ALL);

function my_loop($size) {
   $numbers = array('1','5','20','500','2.500','5.000','10.000','2.500.000');
   $count = count($numbers);
   $combinations=0;
   if($size==6) {
      echo "Combinaties van $size<br>\n";
      for($i=0;$i<$count;$i++) {
          for($j=$i+1;$j<$count;$j++) {
              for($k=$j+1;$k<$count;$k++) {
                  for($l=$k+1;$l<$count;$l++) {
                      for($m=$l+1;$m<$count;$m++) {
                          for($n=$m+1;$n<$count;$n++) {
                              echo "$numbers[$i]<br>$numbers[$j]<br>$numbers[$k]<br>$numbers[$l]<br>$numbers[$m]<br>$numbers[$n]<br><br>\n";
                              $combinations++;
                          }
                       }
                   }
               }
           }
       }
    }

   if($size==5) {
      echo "Combinaties van $size<br>\n";
      for($i=0;$i<$count;$i++) {
          for($j=$i+1;$j<$count;$j++) {
              for($k=$j+1;$k<$count;$k++) {
                  for($l=$k+1;$l<$count;$l++) {
                      for($m=$l+1;$m<$count;$m++) {
                          echo "$numbers[$i]<br>$numbers[$j]<br>$numbers[$k]<br>$numbers[$l]<br>$numbers[$m]<br><br>\n";
                          $combinations++;
                      }
                  }
               }
           }
       }
   }

   if($size==4) {
      echo "Combinaties van $size<br>\n";
      for($i=0;$i<$count;$i++) {
          for($j=$i+1;$j<$count;$j++) {
              for($k=$j+1;$k<$count;$k++) {
                  for($l=$k+1;$l<$count;$l++) {
                      echo "$numbers[$i]<br>$numbers[$j]<br>$numbers[$k]<br>$numbers[$l]<br><br>\n";
                      $combinations++;
                  }
               }
          }
      }
   }

   if($size==3) {
      echo "Combinaties van $size<br>\n";
      for($i=0;$i<$count;$i++) {
          for($j=$i+1;$j<$count;$j++) {
              for($k=$j+1;$k<$count;$k++) {
                  echo "$numbers[$i]<br>$numbers[$j]<br>$numbers[$k]<br><br>\n";
                  $combinations++;
              }
          }
      }
   }

   if($size==2) {
      echo "Combinaties van $size<br>\n";
      for($i=0;$i<$count;$i++) {
          for($j=$i+1;$j<$count;$j++) {
              echo "$numbers[$i]<br>$numbers[$j]<br><br>\n";
              $combinations++;
          }
      }
   }

   if($size==1) {
      echo "Combinaties van $size<br>\n";
      for($i=0;$i<$count;$i++) {
          echo "$numbers[$i]<br><br>\n";
          $combinations++;
      }
   }

   echo "Totaal aantal combinaties: $combinations<br><br>\n";
}

my_loop($input);

?>

Code die ik tot nu toe heb, maar niet werkt

code:

<?php

function my_loop($size) {
   $numbers = array('1','5','20','500','2.500','5.000','10.000','2.500.000');
   $count = count($numbers);
   $current=0;
   for($i=$current;$i<$count;$i++) {
       echo "$numbers[$i]<br>";
       $current++;
       if($current<=$size) {
       my_loop($size);
       }
   }
}

my_loop($input);
?>

Edit: search werkt niet

[ Voor 13% gewijzigd door mrbombastic op 07-04-2004 17:59 ]

[djluc]

offtopic:
Zie ook het mededelingenforum voor de oplossing voor de search...

[dusty]

Alle combinaties, wat bedoel je er precies mee, unieke combinaties ? of Elke combinatie ie:
2 uit ( 1, 2, 3)
Kan je 1,2 ^ 1,3 ^ 2,3 hebben als het alleen unieke combinaties zijn.
Is het geen unieke combinatie zit er ook nog 2,1 e.d. in.

[Sybr_E-N]

Je komt toch al gauw bij statistiek terecht, kansrekening, en dan in de hoek van permutaties "n!" / variaties "n!/(n-k)!" / combinaties "n boven k == n!/(n-k)!*k!". Maar welke hier van toepassing is, is niet aan mij besteed want statistiek is nooit mijn sterkste punt geweest.

[mrbombastic]

dusty schreef op 07 april 2004 @ 21:51:
Alle combinaties, wat bedoel je er precies mee, unieke combinaties ? of Elke combinatie ie:
2 uit ( 1, 2, 3)
Kan je 1,2 ^ 1,3 ^ 2,3 hebben als het alleen unieke combinaties zijn.
Is het geen unieke combinatie zit er ook nog 2,1 e.d. in.

Stel de array bestaat uit 4 elementen (1,2,3,4).
Dan wil ik hebben:
Combinaties van 1 element:
1
2
3
4
Totaal 4 (4 boven 1)

Combinaties van 2 elementen:
1-2
1-3
1-4
2-3
2-4
3-4
Totaal 6 (4 boven 2)

Combinaties van 3 elementen:
1-2-3
1-2-4
1-3-4
2-3-4
Totaal 4 (4 boven 3)

Combinaties van 4 elementen:
1-2-3-4
Totaal 1 (4 boven 4)

Dus de volgorde is irrelevant.
En de kansrekening is hier inderdaad mee verbonden, het gaat om combinaties.
Maar dat is mijn probleem niet (in 2 opzichten: als econometrist zijnde en het is hier niet de hoofdzaak).
Mijn doel is niet om uit te rekenen hoeveel combinaties er zijn, maar om alle combinaties ook daadwerkelijk weer te geven.


Edit: heb net een oplossing van een vriend gekregen.
Bedankt voor het meedenken iig.

[ Voor 9% gewijzigd door mrbombastic op 08-04-2004 00:38 ]

[bigtree]

Wil je je oplossing nog delen voor de search dan?

[Verwijderd]

Als je een database tot je beschikking hebt, dan zou je die kunnen gebruiken om je tabel te genereren, namelijk door middel van een group by cube. ( Oracle en MSSql ondersteunen dit, ik weet niet of MySQL dat doet )

- Maak een tabel met 1 record, met daarin al je waarden.
- voer het volgende sqlstatement uit (oracle syntax)

code:

Select veld1,veld2,veld3.....veldn from tabel group by cube (veld1,veld2,veld3....veldn)

Dit geeft je alle mogelijke combinaties van veld1,veld2,veld3....veldn

[Verwijderd]

Je tweede code bevat ook een fout.

Je blijft in een oneindige loop. Want $current is altijd kleiner dan $size als je eerst $current op 0 zet als je de functie opnieuw aanroept met dezelfde size. Ik denk dat het hem in regel 6 ($current = 0;) zit.

Ik denk dat dit beter zal werken.

PHP:

$current = 0;

function my_loop($size)
{
  $numbers = array('1','5','20','500','2.500','5.000','10.000','2.500.000');
  $count = count($numbers);

  for ($i=$current;$i<$count;$i++)
  {
    echo "$numbers[$i]<br>";
    $current++;

    if($current<=$size)
    {
      my_loop($size);
    }
  }
}

Het niet de mogelijkheid om het te testen

[ Voor 57% gewijzigd door Verwijderd op 08-04-2004 11:25 ]

[seweso]

Verwijderd schreef op 08 april 2004 @ 11:10:
....

Het niet de mogelijkheid om het te testen

Dat kan wel, gewoon tussentijds echoën naar de browser (en daarbij wel rekening houden met het bufferen van IE).

code:

echo str_repeat(" ", 255) . "Joehoe ik zit nu hier en variabele var = $var <br />\n";

[bigtree]

* bigtree heeft zitten puzzelen en kwam tot het volgende:

PHP:

    function get_combis($left, $items, $prefix = array()) {
        $tmp_array = array();
        if ($items == 1) {
            $prefix = array_values($prefix);
            foreach($left as $key => $val) {
                $tmp_array[] = array_merge($prefix, array($val));
            }
        } elseif ($items > 1 && (sizeof($left) > $items)) {
            $n = sizeof($left);
            $left = array_values($left);
            for ($i = 0; $i < $n - $items; $i++) {
                $tmp_prefix = array($left[$i]);
                unset($left[$i]);
                $tmp_arrays = get_combis($left, $items - 1, array_merge($prefix, $tmp_prefix));
                $tmp_array = array_merge($tmp_array, $tmp_arrays);
            }
        } elseif ($items > 1) {
            $tmp_array = $left;
        }
        return $tmp_array;
    }
    

    $items_array = array('A', 'B', 'C', 'D');

    $tmp_array = get_combis($items_array, 1);
    print_r($tmp_array);

    $tmp_array = get_combis($items_array, 2);
    print_r($tmp_array);

    $tmp_array = get_combis($items_array, 3);
    print_r($tmp_array);

    $tmp_array = get_combis($items_array, 4);
    print_r($tmp_array);

Tadaa!

[Soultaker]

Dat kan wel wat korter hoor:

PHP:

function combine($left, $items, $current=array())
{
    if($left == 0)
    {
        // doe hier wat je wilt met je combinatie
        echo implode(',', $current), '<br />';
    }
    else
    if(sizeof($items) > 0)
    {
        array_push($current, array_shift($items));
        combine($left-1, $items, $current);
        array_pop($current);
        combine($left, $items, $current);
    }  
}

combine(3, array('A','B','C','D'));

Uitvoer in dit voorbeeld:

code:

A,B,C
A,B,D
A,C,D
B,C,D

[ Voor 9% gewijzigd door Soultaker op 14-04-2004 20:55 ]

[verytallman]

Allereerst; ik weet dat deze thread oud is, echter heb ik in de search geen nieuwe threads gevonden over dit onderwerp. Bovendien blijft de informatie zo op één plek.

In de laatste post van Soultaker staat zijn oplossing die ik erg goed vind. Ik probeer echter het resultaat (de combinaties) op te vangen in 1 array die de functie teruggeeft. Dit is mijn code:

PHP:

function combine($left, $items, $current = array()) {

    $arrResults = array();
    
    if($left == 0) {
    
        $temp = implode(',', $current);
        return $temp;
        
    } elseif(count($items) > 0) {
            
        array_push($current, array_shift($items));
        
        if (($tmpResult = combine($left-1, $items, $current)) != NULL) {
            $arrResults[] = $tmpResult;
        }
        
        array_pop($current);
        
        if (($tmpResult  = combine($left, $items, $current)) != NULL) {
            $arrResults[] = $tmpResult;
        }
        
    } 
    
    return $arrResults; 
}

$results = combine(2, array('A','B','C','D'), array());
print_r($results);

Ik krijg wel een goed resultaat met alle combinaties, alleen zijn het arrays in arrays die ik terug krijg, zoals dit:

code:

    [0] => Array
        (
            [0] => A,B
            [1] => Array
                (
                    [0] => A,C
                    [1] => Array
                        (
                            [0] => A,D
                        )

                )
etc..

Terwijl ik zo'n array wil hebben:

code:

    [0] => Array
        (
            [0] => A,B
            [1] => A,C
            [2] => A,D
            [3] => etc....
        )

[Grijze Vos]

PHP:

$arrResults[] = $tmpResult;

vervangen door

PHP:

$arrResults = array_merge($arrResults, $tmpResult);

Volgens mij krijg je altijd arrays terug, dus dat zou geen problemen moeten opleveren ivm array-type-checking.

[verytallman]

Ja je hebt gelijk, en hij werkt,

Moest nog wel

PHP:

return $temp;

Vervangen met

PHP:

return array($temp);