Permutations - all possible sets of numbers

Question

I have numbers, from 0 to 8. I would like in result, all possible sets of those numbers, each set should use all numbers, each number can occur only once in a set.

I would like to see solution made in PHP that could print out result. Or, at least, I would like some refreshment in theory of combinatorics, as I have long forgotten it. What is the formula to calculate how many permutations will there be?

Example sets:

• 0-1-2-3-4-5-6-7-8
• 0-1-2-3-4-5-6-8-7
• 0-1-2-3-4-5-8-6-7
• 0-1-2-3-4-8-5-6-7
• 0-1-2-3-8-4-5-6-7
• 0-1-2-8-3-4-5-6-7
• and so on...

Answer 1

I've something that You may like

function combination_number($k,$n){
    $n = intval($n);
    $k = intval($k);
    if ($k > $n){
        return 0;
    } elseif ($n == $k) {
        return 1;
    } else {
        if ($k >= $n - $k){
            $l = $k+1;
            for ($i = $l+1 ; $i <= $n ; $i++)
                $l *= $i;
            $m = 1;
            for ($i = 2 ; $i <= $n-$k ; $i++)
                $m *= $i;
        } else {
            $l = ($n-$k) + 1;
            for ($i = $l+1 ; $i <= $n ; $i++)
                $l *= $i;
            $m = 1;
            for ($i = 2 ; $i <= $k ; $i++)
                $m *= $i;            
        }
    }
    return $l/$m;
}

function array_combination($le, $set){

    $lk = combination_number($le, count($set));
    $ret = array_fill(0, $lk, array_fill(0, $le, '') );

    $temp = array();
    for ($i = 0 ; $i < $le ; $i++)
        $temp[$i] = $i;

    $ret[0] = $temp;

    for ($i = 1 ; $i < $lk ; $i++){
        if ($temp[$le-1] != count($set)-1){
            $temp[$le-1]++;
        } else {
            $od = -1;
            for ($j = $le-2 ; $j >= 0 ; $j--)
                if ($temp[$j]+1 != $temp[$j+1]){
                    $od = $j;
                    break;
                }
            if ($od == -1)
                break;
            $temp[$od]++;
            for ($j = $od+1 ; $j < $le ; $j++)    
                $temp[$j] = $temp[$od]+$j-$od;
        }
        $ret[$i] = $temp;
    }
    for ($i = 0 ; $i < $lk ; $i++)
        for ($j = 0 ; $j < $le ; $j++)
            $ret[$i][$j] = $set[$ret[$i][$j]];   

    return $ret;
}

Here is how to use it:

To get the number of combinations:

combination_number(3,10); // returns number of combinations of ten-elements set.

To get all possible combinations:

$mySet = array("A","B","C","D","E","F");
array_combination(3, $mySet); // returns all possible combinations of 3 elements of six-elements set.

Hope You make use of that.

Answer 2

This is a simple recursive function that prints all permutations (written in pseudocode)

function rec(n, k) {
    if (k == n) {
        for i = 0 to n-1
            print(perm[i], ' ');
        print('\n');
    }
    else {
        for i = 0 to n-1 {
            if (not used[i]) {
                used[i] = true;
                perm[k] = i;
                rec(n, k+1);
                used[i] = false;
            }
        }
    }
}

And it is called like this:

rec(9, 0);

Answer 3

Since PHP 5.5 you can use Generators. Generators save a lot of memory and are way faster (more than half compared to pc_permute()). So if you have any chance of having PHP 5.5 installed, you definitely want Generators. This snipped is ported from Python: https://stackoverflow.com/a/104436/3745311

function permutations(array $elements)
{
    if (count($elements) <= 1) {
        yield $elements;
    } else {
        foreach (permutations(array_slice($elements, 1)) as $permutation) {
            foreach (range(0, count($elements) - 1) as $i) {
                yield array_merge(
                    array_slice($permutation, 0, $i),
                    [$elements[0]],
                    array_slice($permutation, $i)
                );
            }
        }
    }
}

Sample usage:

$list = ['a', 'b', 'c'];

foreach (permutations($list) as $permutation) {
    echo implode(',', $permutation) . PHP_EOL;
}

Output:

a,b,c
b,a,c
b,c,a
a,c,b 
c,a,b
c,b,a

Answer 4

Lexicographical order. There is no recursion. Almost no limits for array length. There is no sort. It's running rather fast. It's easy to understand. Minus: it gives a notice, but you can add a condition to start compare with the second element or error_reporting(0).

$a = array(
1,
2,
3,
4,
5
 );
    $b = array_reverse($a);
    print_r($a);
   //here need "br"
  while ($a != $b)
{
foreach(array_reverse($a, true) as $k => $v)
    {
    if ($v < $a[$k + 1])
        {
        foreach(array_reverse($a, true) as $ka => $val)
            {
            if ($val > $v) break;
            }

        $ch = $a[$k];
        $a[$k] = $a[$ka];
        $a[$ka] = $ch;
        $c = array_slice($a, 0, $k + 1);
        print_r($a = array_merge($c, array_reverse(array_slice($a, $k + 1))));
        //here need "br"
        break;
        }
       }
      }

Answer 5

This is my version of class. This class builds and returns permutated array as result

class Permutation {
    private $result;

    public function getResult() {
        return $this->result;
    }

    public function permute($source, $permutated=array()) {
        if (empty($permutated)){
            $this->result = array();
        }
        if (empty($source)){
            $this->result[] = $permutated;
        } else {
            for($i=0; $i<count($source); $i++){
                $new_permutated = $permutated;
                $new_permutated[] = $source[$i];
                $new_source =    array_merge(array_slice($source,0,$i),array_slice($source,$i+1));
                $this->permute($new_source, $new_permutated);
            }
        }
        return $this;
    }
}

$arr = array(1,2,3,4,5);
$p = new Permutation();
print_r($p->permute($arr)->getResult());

The last three lines to test my class.

Answer 6

Try this...

//function to generate and print all N! permutations of $str. (N = strlen($str))

function permute($str,$i,$n) {
   if ($i == $n)
       print "$str\n";
   else {
        for ($j = $i; $j < $n; $j++) {
          swap($str,$i,$j);
          permute($str, $i+1, $n);
          swap($str,$i,$j); // backtrack.
       }
   }
}

// function to swap the char at pos $i and $j of $str.

function swap(&$str,$i,$j) {
    $temp = $str[$i];
    $str[$i] = $str[$j];
    $str[$j] = $temp;
}   
$str = "0123";
permute($str,0,strlen($str)); // call the function.