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

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

---