两天来我一直在疯狂地试图做到这一点，也许你可以启发我。这是针对马匹投注的排列。每次用户玩游戏时，我都会得到一个多维数组（2 级）。第一级包含比赛ID，第二级包含用户为该比赛选择的马匹。它看起来像这样：
$play = array
(
'4' => array(7, 32),
'8' => array(4),
'2' => array(9),
'12' => array('5'),
'83' => array('10', '11', '12', ''),
'9' => array('3'),
);
我需要知道该剧的所有可能组合是什么。使用此功能很容易完成：
function permutations(array $array)
{
switch (count($array)) {
case 1:
return $array[0];
break;
case 0:
throw new InvalidArgumentException('Requires at least one array');
break;
}
$a = array_shift($array);
$b = permutations($array);
$return = array();
foreach ($a as $key => $v) {
if(is_numeric($v))
{
foreach ($b as $key2 => $v2) {
$return[] = array_merge(array($v), (array) $v2);
}
}
}
return $return;
}
这将漂亮地返回一个包含所有可能组合的数组。到目前为止一切顺利，结果如下所示：
Array
(
[0] => Array
(
[0] => 7
[1] => 4
[2] => 9
[3] => 5
[4] => 10
[5] => 3
)
[1] => Array
(
[0] => 7
[1] => 4
[2] => 9
[3] => 5
[4] => 11
[5] => 3
)
[2] => Array
(
[0] => 7
[1] => 4
[2] => 9
[3] => 5
[4] => 12
[5] => 3
)
[3] => Array
(
[0] => 32
[1] => 4
[2] => 9
[3] => 5
[4] => 10
[5] => 3
)
[4] => Array
(
[0] => 32
[1] => 4
[2] => 9
[3] => 5
[4] => 11
[5] => 3
)
[5] => Array
(
[0] => 32
[1] => 4
[2] => 9
[3] => 5
[4] => 12
[5] => 3
)
)
我的问题：我需要每匹马的数组"键"是"比赛ID"，而不是0,1,2,3。我需要结果是这样的：
Array
(
[0] => Array
(
[4] => 7
[8] => 4
[2] => 9
[12] => 5
[83] => 10
[9] => 3
)
[1] => Array
(
[4] => 7
[8] => 4
[2] => 9
[12] => 5
[83] => 11
[9] => 3
)
[2] => Array
(
[4] => 7
[8] => 4
[2] => 9
[12] => 5
[83] => 12
[9] => 3
)
[3] => Array
(
[4] => 32
[8] => 4
[2] => 9
[12] => 5
[83] => 10
[9] => 3
)
[4] => Array
(
[4] => 32
[8] => 4
[2] => 9
[12] => 5
[83] => 11
[9] => 3
)
[5] => Array
(
[4] => 32
[8] => 4
[2] => 9
[12] => 5
[83] => 12
[9] => 3
)
)
我怎样才能做到这一点？我知道这是一篇很长的帖子，但我需要绘制这个图表。我在函数递归方面遇到了问题，我完全迷失在每个循环中。
我遇到了同样的问题，丹尼的解决方案对我不好。我管理数千个排列并将它们存储在内存中是非常昂贵的。
这是我的解决方案：
/**
* Calculate permutation of multidimensional array. Without recursion!
* Ex.
* $array = array(
* key => array(value, value),
* key => array(value, value, value),
* key => array(value, value),
* );
*
* @copyright Copyright (c) 2011, Matteo Baggio
* @param array $anArray Multidimensional array
* @param function $isValidCallback User function called to verify the permutation. function($permutationIndex, $permutationArray)
* @return mixed Return valid permutation count in save memory configuration, otherwise it return an Array of all permutations
*/
function permutationOfMultidimensionalArray(array $anArray, $isValidCallback = false) {
// Quick exit
if (empty($anArray))
return 0;
// Amount of possible permutations: count(a[0]) * count(a[1]) * ... * count(a[N])
$permutationCount = 1;
// Store informations about every column of matrix: count and cumulativeCount
$matrixInfo = array();
$cumulativeCount = 1;
foreach($anArray as $aColumn) {
$columnCount = count($aColumn);
$permutationCount *= $columnCount;
// this save a lot of time!
$matrixInfo[] = array(
'count' => $columnCount,
'cumulativeCount' => $cumulativeCount
);
$cumulativeCount *= $columnCount;
}
// Save the array keys
$arrayKeys = array_keys($anArray);
// It needs numeric index to work
$matrix = array_values($anArray);
// Number of column
$columnCount = count($matrix);
// Number of valid permutation
$validPermutationCount = 0;
// Contain all permutations
$permutations = array();
// Iterate through all permutation numbers
for ($currentPermutation = 0; $currentPermutation < $permutationCount; $currentPermutation++) {
for ($currentColumnIndex = 0; $currentColumnIndex < $columnCount; $currentColumnIndex++) {
// Here the magic!
// I = int(P / (Count(c[K-1]) * ... * Count(c[0]))) % Count(c[K])
// where:
// I: the current column index
// P: the current permutation number
// c[]: array of the current column
// K: number of the current column
$index = intval($currentPermutation / $matrixInfo[$currentColumnIndex]['cumulativeCount']) % $matrixInfo[$currentColumnIndex]['count'];
// Save column into current permutation
$permutations[$currentPermutation][$currentColumnIndex] = $matrix[$currentColumnIndex][$index];
}
// Restore array keys
$permutations[$currentPermutation] = array_combine($arrayKeys, $permutations[$currentPermutation]);
// Callback validate
if ($isValidCallback !== false) {
if ($isValidCallback($currentPermutation, $permutations[$currentPermutation]))
$validPermutationCount++;
// *** Uncomment this lines if you want that this function return all
// permutations
//else
// unset($permutations[$currentPermutation]);
}
else {
$validPermutationCount++;
}
// Save memory!!
// Use $isValidCallback to check permutation, store into DB, etc..
// *** Comment this line if you want that function return all
// permutation. Memory warning!!
unset($permutations[$currentPermutation]);
}
if (!empty($permutations))
return $permutations;
else
return $validPermutationCount;
}
//
// How to?
//
$play = array(
'4' => array(7, 32),
'8' => array(4),
'2' => array(9),
'12' => array('5'),
'83' => array('10', '11', '12', ''), // <-- It accept all values, nested array too
'9' => array('3'),
);
$start = microtime(true);
// Anonymous function work with PHP 5.3.0
$validPermutationsCount = permutationOfMultidimensionalArray($play, function($permutationIndex, $permutationArray){
// Here you can validate the permutation, print it, etc...
// Using callback you can save memory and improve performance.
// You don't need to cicle over all permutation after generation.
printf('<p><strong>%d</strong>: %s</p>', $permutationIndex, implode(', ', $permutationArray));
return true; // in this case always true
});
$stop = microtime(true) - $start;
printf('<hr /><p><strong>Performance for %d permutations</strong><br />
Execution time: %f sec<br/>
Memory usage: %d Kb</p>',
$validPermutationsCount,
$stop,
memory_get_peak_usage(true) / 1024);
如果有人有更好的主意，我就在这里！
这是你需要的。我已在必要时发表评论：
function permutations(array $array)
{
switch (count($array)) {
case 1:
// Return the array as-is; returning the first item
// of the array was confusing and unnecessary
return $array;
break;
case 0:
throw new InvalidArgumentException('Requires at least one array');
break;
}
// We 'll need these, as array_shift destroys them
$keys = array_keys($array);
$a = array_shift($array);
$k = array_shift($keys); // Get the key that $a had
$b = permutations($array);
$return = array();
foreach ($a as $v) {
if(is_numeric($v))
{
foreach ($b as $v2) {
// array($k => $v) re-associates $v (each item in $a)
// with the key that $a originally had
// array_combine re-associates each item in $v2 with
// the corresponding key it had in the original array
// Also, using operator+ instead of array_merge
// allows us to not lose the keys once more
$return[] = array($k => $v) + array_combine($keys, $v2);
}
}
}
return $return;
}
看到它的实际效果。
顺便说一下，递归计算所有排列是整洁的，但您可能不想在生产环境中这样做。您绝对应该考虑进行健全性检查，以计算有多少排列，并且至少在它们超过某个限制时不允许继续处理。
我通过将 Jon 的算法与我最初使用的算法合并来改进他的函数。我所做的是检查函数是否正在执行递归，如果是，我使用原始的 array_merge（）（它正在工作），否则我使用 Jon 的 array_combine（）（以保留数组键）。
我将 Jon 的答案标记为正确，因为他提出了一个巧妙的解决方案来保持数组键的完整。
function permutations(array $array, $inb=false)
{
switch (count($array)) {
case 1:
// Return the array as-is; returning the first item
// of the array was confusing and unnecessary
return $array[0];
break;
case 0:
throw new InvalidArgumentException('Requires at least one array');
break;
}
// We 'll need these, as array_shift destroys them
$keys = array_keys($array);
$a = array_shift($array);
$k = array_shift($keys); // Get the key that $a had
$b = permutations($array, 'recursing');
$return = array();
foreach ($a as $v) {
if(is_numeric($v))
{
foreach ($b as $v2) {
// array($k => $v) re-associates $v (each item in $a)
// with the key that $a originally had
// array_combine re-associates each item in $v2 with
// the corresponding key it had in the original array
// Also, using operator+ instead of array_merge
// allows us to not lose the keys once more
if($inb == 'recursing')
$return[] = array_merge(array($v), (array) $v2);
else
$return[] = array($k => $v) + array_combine($keys, $v2);
}
}
}
return $return;
}
使用多种阵列组合成功测试。