排列 – 所有可能的数字组合
我有数字，从0到8.我想结果，这些数字的所有可能的集合，每个集合应该使用所有数字，每个数字只能在一个集合中只出现一次。
我想看看在PHP中可以打印出结果的解决scheme。 或者，至less，我想在组合学的理论上有所提神，因为我早已忘记了它。 计算有多less排列的公式是多less？
示例集：
- 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
- 等等…
你正在寻找排列公式：
nPk = n!/(nk)! 在你的情况下，你有9个条目，你想select所有的，这是9P9 = 9！ = 362880
你可以在O'Reilly的“PHP Cookbook”的配方4.26中find一个PHPalgorithm来进行排列。
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); } } }
由于这个问题经常出现在Googlesearch结果中，下面是接受答案的修改版本，它返回数组中的所有组合，并将它们作为函数的返回值传递。
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));
从PHP 5.5开始，你可以使用Generators 。 发生器节省了大量的内存，并且速度更快（比pc_permute（）多了一半）。 所以，如果你有任何安装PHP 5.5的机会，你绝对想要发电机。 这个剪辑是从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) ); } } } }
示例用法：
$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,bc,a,b c,b,a
我有你可能喜欢的东西
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.
希望你利用这一点。
这是我的课程版本。 这个类构build并返回排列的数组作为结果
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());
最后三行来testing我的课程。
这是一个简单的recursion函数，它打印所有的排列（用伪代码写）
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);
字典顺序。 没有recursion。 数组长度几乎没有限制。 没有sorting。 运行速度相当快 这很容易理解。 减号：它给出了一个通知，但你可以添加一个条件来开始比较第二个元素或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; } } }
你基本上谈论的是n和k都是9的排列，所以你会有9! 不同的排列; 看到这个： http : //en.wikipedia.org/wiki/Permutation 。
这是我的build议，希望比接受的答案更清楚一些。
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";
尝试这个…
//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.
我移植了这里列出的Python itertools代码（使用生成器）。 迄今为止发布的解决scheme的优点是它允许您指定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"; }
