php 排列 - 所有可能的数字集
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5506888/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Permutations - all possible sets of numbers
提问by Deele
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.
我有数字，从 0 到 8。我想在结果中，这些数字的所有可能集合，每个集合都应该使用所有数字，每个数字在一个集合中只能出现一次。
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?
我希望看到可以打印出结果的 PHP 解决方案。或者，至少，我想要一些组合数学理论的提神，因为我早就忘记了。计算有多少排列的公式是什么？
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...
- 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
- 等等...
回答by yzxben
You're looking for the permutations formula:
您正在寻找排列公式：
nPk = n!/(n-k)!
In your case, you have 9 entries and you want to choose all of them, that's 9P9 = 9! = 362880
在您的情况下，您有 9 个条目并且您想选择所有条目，即 9P9 = 9！= 362880
You can find a PHP algorithm to permutate in recipe 4.26 of O'Reilly's "PHP Cookbook".
您可以在 O'Reilly 的“PHP Cookbook”的配方 4.26 中找到要置换的 PHP 算法。
pc_permute(array(0, 1, 2, 3, 4, 5, 7, 8));
Copied in from O'Reilly:
复制自 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);
}
}
}
回答by spezifanta
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
从 PHP 5.5 开始，您可以使用Generators。生成器节省了大量内存并且速度更快（与pc_permute()相比超过一半）。因此，如果您有机会安装 PHP 5.5，那么您肯定需要 Generators。这个片段是从 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
回答by dAngelov
Since this question often comes up in Google Search results, here's a modified version of the accepted answer that returns all combinations in an array and passes them as a return value of the function.
由于这个问题经常出现在 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;
}
To use:
使用：
$value = array('1', '2', '3');
print_r(pc_permute($value));
回答by Piotr Salaciak
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.
希望你利用它。
回答by Jeff_Alieffson
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.
最后三行来测试我的课程。
回答by eddiewould
I've ported the Python itertools code listed here(using generators). The advantage over the solutions posted so far is that it allows you to specify r (permutation size).
我已经移植了此处列出的 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
}
}
}
It works for me, but no promises! Example usage:
它对我有用，但没有承诺！用法示例：
$result = iterator_to_array(permutations([1, 2, 3, 4], 3));
foreach ($result as $row) {
print implode(", ", $row) . "\n";
}
回答by dcc0
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).
字典序。没有递归。数组长度几乎没有限制。没有排序。它运行得相当快。这很容易理解。减号：它给出了一个通知，但您可以添加一个条件来开始与第二个元素或 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;
}
}
}
回答by fdermishin
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);
回答by Argote
You're basically talking about permutations where both nand kare 9 so you'll have 9!different permutations; see this: http://en.wikipedia.org/wiki/Permutation.
你基本上是在谈论排列，其中n和k都是 9，所以你会有9!不同的排列；请参阅：http: //en.wikipedia.org/wiki/Permutation。
回答by jeswin
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.
