排列组合 - 所有可能的数字集合

Question

我有0到8的数字。 我希望得到所有可能的数字集合，每个集合应使用所有数字，每个数字在一个集合中只能出现一次。

我想看到用PHP编写的解决方案，可以打印出结果。或者，至少我想要一些组合数学理论的复习，因为我已经很久没有接触了。如何计算全排列的公式是什么？

示例集：

• 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
• 等等...

- Deele

Answer 1

你正在寻找排列组合公式：

nPk = n!/(n-k)!

在您的情况下，您有9个条目并且希望选择它们全部，即9P9 = 9！= 362880。

您可以在O'Reilly的“PHP Cookbook”中的配方4.26中找到一个用于排列的PHP算法。

pc_permute(array(0, 1, 2, 3, 4, 5, 7, 8));

从 O'Reilly 复制而来：

function pc_permute($items, $perms = array( )) {
    if (empty($items)) { 
        print join(' ', $perms) . "\n";
    }  else {
        for ($i = count($items) - 1; $i >= 0; --$i) {
             $newitems = $items;
             $newperms = $perms;
             list($foo) = array_splice($newitems, $i, 1);
             array_unshift($newperms, $foo);
             pc_permute($newitems, $newperms);
         }
    }
}

- yzxben

---

哇，这太疯狂了。也许这应该放在 Stack Exchange 的数学网站上，但为什么 0! = 1？ - Jason

你知道任何生成它们的算法吗？ :) 我可以将数量减少到8！= 40320，因为我知道第一个数字只能是0、1或4。而且40k并不太多... - Deele

@Jason：根据定义，结果为0。就像x^0 = 1一样（除了当x = 0时，因为0^0 = 0）。 - poke

@Deele 如果你想要以0、1或4开头的排列，那么你需要考虑三个不同的8位数字排列（不同的集合），因此是8！+8！+8！= 120960。 - yzxben

是的，我已经算过了 :) 我想我会使用这里提供的其中一个算法，将所有结果写入文件，然后读取它们以过滤出我需要的结果。 - Deele

Jason和Poke，你们误解了这里“!”的含义。在逻辑表达式中，它表示NOT，但在数学上下文中，它是阶乘的符号。去谷歌搜索一下吧。 - Ellert van Koperen

Answer 2

自 PHP 5.5 版本起，您可以使用生成器（Generators）。相比于pc_permute()，生成器在节省大量内存并提高运行速度（超过一半）方面表现更佳。因此，如果您的服务器已安装 PHP 5.5，您绝对需要使用生成器。 这段代码来自Python：https://dev59.com/OHVD5IYBdhLWcg3wDXJ3#104436

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)
                );
            }
        }
    }
}

使用示例：

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

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

输出:

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

- spezifanta

---

你如何适应只选择一个子集？例如，返回上述内容以及a,b | a,c | b,a | b,c | c,a | c,b | a | b | c？ - Codemonkey

看看我的答案，其中有一个函数可以让你指定排列的大小。从那里开始生成所有排列就很容易了。 - eddiewould

Answer 3

由于此问题经常出现在Google搜索结果中，因此这里提供了一个修改后的答案，它将所有组合作为数组返回，并将它们作为函数的返回值传递。

function pc_permute($items, $perms = array( )) {
    if (empty($items)) {
        $return = array($perms);
    }  else {
        $return = array();
        for ($i = count($items) - 1; $i >= 0; --$i) {
             $newitems = $items;
             $newperms = $perms;
         list($foo) = array_splice($newitems, $i, 1);
             array_unshift($newperms, $foo);
             $return = array_merge($return, pc_permute($newitems, $newperms));
         }
    }
    return $return;
}

使用方法：

$value = array('1', '2', '3');
print_r(pc_permute($value));

- dAngelov

---

内存使用过多："PHP致命错误：分配71字节时已用尽134217728字节的允许内存大小..." - Katie

@Kayvar ini_set('memory_limit', -1); （注：这是一段PHP代码，意为设置内存限制为无限制。） - verbumSapienti

Answer 4

我有一些东西，可能会对您感兴趣。

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;
}

以下是如何使用它：

获取组合数的方法：

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

获取所有可能的组合：

要获取所有可能的组合：

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

希望你能好好利用它。

- Piotr Salaciak

---

可爱，但这只是维持秩序而已。 - Bill Ortell

@Piotr Salaciak这里似乎还缺少一些内容 array_combination(2, $mySet); 将不会返回AA、BB或CC的组合。 - Guru

@Guru 这是一个没有重复的组合 链接 - Piotr Salaciak

只对三个元素有效，当我尝试四个元素时，它返回一个组合。 - delboy1978uk

@delboy1978uk 我猜你正在尝试组合一个只有3个元素的集合中的3个元素。 - Piotr Salaciak

Answer 5

我已经将列在这里的Python itertools代码（使用生成器）移植过来。与迄今所发布的解决方案相比，其优点在于它允许您指定r（排列大小）。

function permutations($pool, $r = null) {
    $n = count($pool);

    if ($r == null) {
        $r = $n;
    }

    if ($r > $n) {
        return;
    }

    $indices = range(0, $n - 1);
    $cycles = range($n, $n - $r + 1, -1); // count down

    yield array_slice($pool, 0, $r);

    if ($n <= 0) {
        return;
    }

    while (true) {
        $exit_early = false;
        for ($i = $r;$i--;$i >= 0) {
            $cycles[$i]-= 1;
            if ($cycles[$i] == 0) {
                // Push whatever is at index $i to the end, move everything back
                if ($i < count($indices)) {
                    $removed = array_splice($indices, $i, 1);
                    array_push($indices, $removed[0]);
                }
                $cycles[$i] = $n - $i;
            } else {
                $j = $cycles[$i];
                // Swap indices $i & -$j.
                $i_val = $indices[$i];
                $neg_j_val = $indices[count($indices) - $j];
                $indices[$i] = $neg_j_val;
                $indices[count($indices) - $j] = $i_val;
                $result = [];
                $counter = 0;
                foreach ($indices as $indx) {
                    array_push($result, $pool[$indx]);
                    $counter++;
                    if ($counter == $r) break;
                }
                yield $result;
                $exit_early = true;
                break;
            }
        }
        if (!$exit_early) {
            break; // Outer while loop
        }
    }
}

这对我来说可行，但不保证适用于所有情况！ 使用示例：

$result = iterator_to_array(permutations([1, 2, 3, 4], 3));
foreach ($result as $row) {
    print implode(", ", $row) . "\n";
}

- eddiewould

---

出色。谢谢eddiewould - delboy1978uk

你节省了我的时间，太棒了！ - Meas

谢谢你的解决方案。我试图生成（0-9和a-z）的5个字符排列组合。$result = iterator_to_array(permutations([0,1, 2, 3, 4,5,6,7,8,9,a,b,c,d], 5)); 运行良好。但是当我添加[0,1, 2, 3, 4,5,6,7,8,9,a,b,c,d, e]时，它停止工作了。有什么想法吗？ - Roy

Answer 6

这是我编写的一个类。该类生成并返回排列后的数组作为结果。

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());

测试我的类的最后三行代码。

- Jeff_Alieffson

Answer 7

以下是一个简单的递归函数，用于打印所有排列组合（伪代码）

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;
            }
        }
    }
}

这样称呼它：

rec(9, 0);

- fdermishin

Answer 8

字典序排序。没有递归。数组长度几乎没有限制。没有排序，运行非常快。易于理解。 缺点：它会发出一个通知，但是您可以添加条件来从第二个元素开始比较或使用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;
        }
       }
      }

- dcc0

---

修复通知：if (isset($a[$key + 1]) && $value < $a[$key + 1]) {（太短无法编辑 :) - Rarst

Answer 9

这是我的建议，希望比接受的答案更加清晰明了。

   function permutate($elements, $perm = array(), &$permArray = array())
{
    if(empty($elements))
    {
       array_push($permArray,$perm); return;
    }

    for($i=0;$i<=count($elements)-1;$i++)
    {
       array_push($perm,$elements[$i]);
       $tmp = $elements; array_splice($tmp,$i,1);
       permutate($tmp,$perm,$permArray);
       array_pop($perm);
    }

    return $permArray;
}

和用法：

$p = permutate(array('a','b','c'));
foreach($p as $perm)
    print join(",",$perm)."|\n";

- Jarek

Answer 10

你基本上在谈论当 n 和 k 都为9时的排列组合，因此你将有 9! 种不同的排列方式；请参见：http://en.wikipedia.org/wiki/Permutation。

- Argote