我有一个由7个数字（1,2,3,4,5,6,7）组成的数组，我想从这些数字中选择5个数字，如(1,2,3,4,5)、(1,2,3,4,6)、(1,2,3,4,7)。请注意，(1,2,3,4,5)等同于(4,5,3,1,2)，因此只应该包含其中一个在输出中。
我想知道PHP或任何算法是否有可以实现这一功能的函数？我不知道从哪里开始。你能帮我吗？
我想将所有给定的7个数字组合成5个槽位，忽略顺序。
PHP数组组合
26
- NVG
4
你能提供更多的规格说明吗？我很难从示例集中抽象出来 - 考虑到我参加 SAT 已经有十年了。 - Jason McCreary
你想生成将1到7的数字放入5个插槽中的所有组合，不考虑顺序吗？ - erisco
你想要元素的子集，对吗？ - Shamim Hafiz - MSFT
@erisco - 我想要将给定数组中的7个数字的所有组合放入5个插槽中，不考虑顺序。 - NVG
8个回答
42
您可以使用此处找到的解决方案http://stereofrog.com/blok/on/070910。
如果链接失效，这是代码...
class Combinations implements Iterator
{
protected $c = null;
protected $s = null;
protected $n = 0;
protected $k = 0;
protected $pos = 0;
function __construct($s, $k) {
if(is_array($s)) {
$this->s = array_values($s);
$this->n = count($this->s);
} else {
$this->s = (string) $s;
$this->n = strlen($this->s);
}
$this->k = $k;
$this->rewind();
}
function key() {
return $this->pos;
}
function current() {
$r = array();
for($i = 0; $i < $this->k; $i++)
$r[] = $this->s[$this->c[$i]];
return is_array($this->s) ? $r : implode('', $r);
}
function next() {
if($this->_next())
$this->pos++;
else
$this->pos = -1;
}
function rewind() {
$this->c = range(0, $this->k);
$this->pos = 0;
}
function valid() {
return $this->pos >= 0;
}
protected function _next() {
$i = $this->k - 1;
while ($i >= 0 && $this->c[$i] == $this->n - $this->k + $i)
$i--;
if($i < 0)
return false;
$this->c[$i]++;
while($i++ < $this->k - 1)
$this->c[$i] = $this->c[$i - 1] + 1;
return true;
}
}
foreach(new Combinations("1234567", 5) as $substring)
echo $substring, ' ';
这是一组数字，它们代表着 6 个球员参加的一个游戏。每个球员都会选择一些数字来组成一个集合。这个集合由 5 个数字组成，选法有很多种。这里列出了所有可能的集合。
- Galen
3
2感谢您在这里发布此内容，因为链接现在似乎已经失效了 :) - Jason M
这段程序相关的内容需要翻译成中文。请仅返回翻译后的文本：对于范围为
array(1, 2, 3, 4, 5, 6, 7) 的情况，一切正常。但是如果范围是 1-80 呢？我会得到 Out of memory (allocated 1837629440) 的错误提示。 - devpro3组合数量的增长速度像阶乘一样快，甚至比指数函数还要快。对于50个元素，C(50,25) = 50!/(25! x 25!) = 126,410,606,437,752。假设生成序列不需要成本，并且您可以在1微秒内处理任何给定的序列（每秒一百万个序列），您需要大约四年的时间来处理C(50,25)个序列。使用生成器可能可以避免内存问题，但您仍然无法使用结果进行任何有用的操作，因为CPU不够用。 - kuroi neko
21
<?php
echo "<pre>";
$test = array("test_1","test_2","test_3");
// Get Combination
$return = uniqueCombination($test);
//Sort
sort($return);
//Pretty Print
print_r(array_map(function($v){ return implode(",", $v); }, $return));
function uniqueCombination($in, $minLength = 1, $max = 2000) {
$count = count($in);
$members = pow(2, $count);
$return = array();
for($i = 0; $i < $members; $i ++) {
$b = sprintf("%0" . $count . "b", $i);
$out = array();
for($j = 0; $j < $count; $j ++) {
$b{$j} == '1' and $out[] = $in[$j];
}
count($out) >= $minLength && count($out) <= $max and $return[] = $out;
}
return $return;
}
?>
输出
Array
(
[0] => test_1
[1] => test_2
[2] => test_3
[3] => test_1,test_2
[4] => test_1,test_3
[5] => test_2,test_3
[6] => test_1,test_2,test_3
)
- lalu tale
3
欢迎来到 Stack Overflow！虽然这段代码可能有助于解决问题，但它并没有解释为什么以及如何回答这个问题。提供这种额外的上下文将显著提高其长期价值。请编辑您的答案以添加说明，包括适用的限制和假设。 - Toby Speight
2并且也请帮我翻译一下！但是解释它的运作方式将非常有帮助！特别是
sprintf() 和 and 的用法。 - cyadvert这在范围是
array(1, 2, 3, 4, 5, 6, 7) 的情况下没问题，但是如果范围是 1-80 呢？我会收到 Out of memory (allocated 1837629440) 的错误提示。 - devpro16
Math_Combinatorics是PEAR存储库中的一个包，它会完美地实现您需要的功能：
该包返回给定集合和子集大小的无重复组合和排列。关联数组将被保留。
require_once 'Math/Combinatorics.php';
$combinatorics = new Math_Combinatorics;
$input = array(1, 2, 3, 4, 5, 6, 7);
$output = $combinatorics->combinations($input, 5); // 5 is the subset size
// 1,2,3,4,5
// 1,2,3,4,6
// 1,2,3,4,7
// 1,2,3,5,6
// 1,2,3,5,7
// 1,2,3,6,7
// 1,2,4,5,6
// 1,2,4,5,7
// 1,2,4,6,7
// 1,2,5,6,7
// 1,3,4,5,6
// 1,3,4,5,7
// 1,3,4,6,7
// 1,3,5,6,7
// 1,4,5,6,7
// 2,3,4,5,6
// 2,3,4,5,7
// 2,3,4,6,7
// 2,3,5,6,7
// 2,4,5,6,7
// 3,4,5,6,7
- Salman A
3
这段程序相关的内容需要翻译成中文。请仅返回翻译后的文本：当范围是
array(1, 2, 3, 4, 5, 6, 7) 时，一切正常，但如果范围是 1-80 呢？我会得到 Out of memory (allocated 1837629440) 的错误提示。 - devpro80个项目中每次取5个会得到24,040,016种组合。这太多了！ - Salman A
是的，Salman，这是真的，但我需要它可以处理50个项目，有没有解决方案？ - devpro
3
另一种基于堆栈的解决方案。它非常快速但会消耗大量内存。
希望这能帮助到某些人。
详细信息：
function _combine($numbers, $length)
{
$combinations = array();
$stack = array();
// every combinations can be ordered
sort($numbers);
// startup
array_push($stack, array(
'store' => array(),
'options' => $numbers,
));
while (true) {
// pop a item
$item = array_pop($stack);
// end of stack
if (!$item) {
break;
}
// valid store
if ($length <= count($item['store'])) {
$combinations[] = $item['store'];
continue;
}
// bypass when options are not enough
if (count($item['store']) + count($item['options']) < $length) {
continue;
}
foreach ($item['options'] as $index => $n) {
$newStore = $item['store'];
$newStore[] = $n;
// every combine can be ordered
// so accept only options which is greater than store numbers
$newOptions = array_slice($item['options'], $index + 1);
// push new items
array_push($stack, array(
'store' => $newStore,
'options' => $newOptions,
));
}
}
return $combinations;
}
- Nguyen Van Vinh
1
改进了这个答案，使其能够与关联数组一起使用：
function uniqueCombination($values, $minLength = 1, $maxLength = 2000) {
$count = count($values);
$size = pow(2, $count);
$keys = array_keys($values);
$return = [];
for($i = 0; $i < $size; $i ++) {
$b = sprintf("%0" . $count . "b", $i);
$out = [];
for($j = 0; $j < $count; $j ++) {
if ($b[$j] == '1') {
$out[$keys[$j]] = $values[$keys[$j]];
}
}
if (count($out) >= $minLength && count($out) <= $maxLength) {
$return[] = $out;
}
}
return $return;
}
例如：
print_r(uniqueCombination([
'a' => 'xyz',
'b' => 'pqr',
]);
结果：
Array
(
[0] => Array
(
[b] => pqr
)
[1] => Array
(
[a] => xyz
)
[2] => Array
(
[a] => xyz
[b] => pqr
)
)
它仍然适用于非关联数组：
print_r(uniqueCombination(['a', 'b']);
结果：
Array
(
[0] => Array
(
[1] => b
)
[1] => Array
(
[0] => a
)
[2] => Array
(
[0] => a
[1] => b
)
)
- Prince Dorcis
1
这对于10个项目非常有效，但如果我尝试100个项目就会出现内存错误。 - Linesofcode
0
我发现这里的其他答案令人困惑或过于复杂，所以我写了自己的方法。我认为这是一种使用递归方法的简单解决方案。基本思路是遍历数组，并针对每个项目决定它是否在组合中（实际上，你不需要决定，你可以递归尝试两种方式）。你首先选择第一个项目，然后将其与剩余数组的递归生成的组合相结合。该解决方案将结果数组填充为数组的每个组合作为子数组。它按顺序使用项目并保留关联，包括数字键。
function combinations(array $items, int $numToChoose, array &$results, $comb = []): void {
if (count($items) < $numToChoose) {
throw new \Exception("Asked to choose $numToChoose items from an array of length ". count($items));
}
// if nothing left to choose, we have a complete combination
if ($numToChoose === 0) {
$results[] = $comb;
return;
}
// if we have to choose everything at this point, then we know what to do
if (count($items) == $numToChoose) {
$results[] = $comb + $items;
return;
}
// The recursive cases: either use the first element or not and find combinations of the rest
$val = reset($items);
$key = key($items);
unset($items[$key]);
// not using it
combinations($items, $numToChoose, $results, $comb);
// using it
$comb[$key] = $val;
combinations($items, $numToChoose - 1, $results, $comb);
}
// Do a test run
$combs = [];
combinations([1=>1, 2=>2, 3=>3], 2, $combs);
var_dump($perms);
这将导致以下输出：
array(3) {
[0]=>
array(2) {
[2]=>
int(2)
[3]=>
int(3)
}
[1]=>
array(2) {
[1]=>
int(1)
[3]=>
int(3)
}
[2]=>
array(2) {
[1]=>
int(1)
[2]=>
int(2)
}
}
- Daniel Skarbek
2
@mickmackusa，是的，那也可以。当然，我也想要值，所以我必须使用该键来访问该值，仍然需要两行代码。在我看来，这似乎相当等效。但是，感谢您指出array_key_first，我没有将该方法放在首要位置，它肯定可以在某些情况下提供帮助。 - Daniel Skarbek
0
优化速度和内存的新解决方案，用于组合算法
思路：生成由数字数组组成的K个数字的组合。新解决方案将使用K个“for”语句。一个“for”语句对应一个数字。 例如：$K = 5表示使用5个“for”语句
$total = count($array);
$i0 = -1;
for ($i1 = $i0 + 1; $i1 < $total; $i1++) {
for ($i2 = $i1 + 1; $i2 < $total; $i2++) {
for ($i3 = $i2 + 1; $i3 < $total; $i3++) {
for ($i4 = $i3 + 1; $i4 < $total; $i4++) {
for ($i5 = $i4 + 1; $i5 < $total; $i5++) {
$record = array();
for ($i = 1; $i <= $k; $i++) {
$t = "i$i";
$record[] = $array[$$t];
}
$callback($record);
}
}
}
}
}
代码的详细信息，生成了实际将由eval()函数执行的代码
function combine($array, $k, $callback)
{
$total = count($array);
$init = '
$i0 = -1;
';
$sample = '
for($i{current} = $i{previous} + 1; $i{current} < $total; $i{current}++ ) {
{body}
}
';
$do = '
$record = array();
for ($i = 1; $i <= $k; $i++) {
$t = "i$i";
$record[] = $array[$$t];
}
$callback($record);
';
$for = '';
for ($i = $k; $i >= 1; $i--) {
switch ($i) {
case $k:
$for = str_replace(['{current}', '{previous}', '{body}'], [$i, $i - 1, $do], $sample);
break;
case 1:
$for = $init . str_replace(['{current}', '{previous}', '{body}'], [$i, $i - 1, $for], $sample);
break;
default:
$for = str_replace(['{current}', '{previous}', '{body}'], [$i, $i - 1, $for], $sample);
break;
}
}
// execute
eval($for);
}
如何合并K个数组
$k = 5;
$array = array(1, 2, 3, 4, 5, 6, 7);
$callback = function ($record) {
echo implode($record) . "\n";
};
combine($array, $k, $callback);
- Nguyễn Văn Vinh
-1
我需要一个包含子集的组合函数，所以我采用了@Nguyen Van Vinh的答案，并根据我的需求进行了修改。
如果您将[1, 2, 3, 4]传递给该函数，它会返回每个唯一的组合和子集，已排序：
如果您将[1, 2, 3, 4]传递给该函数，它会返回每个唯一的组合和子集，已排序：
[
[1,2,3,4], [1,2,3], [1,2,4], [1,3,4], [2,3,4], [1,2], [1,3], [1,4], [2,3], [2,4], [3,4], [1], [2], [3], [4]
]
这是函数：
function get_combinations_with_length( $numbers, $length ){
$result = array();
$stack = array();
// every combinations can be ordered
sort($numbers);
// startup
array_push($stack, array(
'store' => array(),
'options' => $numbers,
));
while (true) {
// pop a item
$item = array_pop($stack);
// end of stack
if (!$item) break;
// valid store
if ($length <= count($item['store'])) {
$result[] = $item['store'];
continue;
}
// bypass when options are not enough
if (count($item['store']) + count($item['options']) < $length) {
continue;
}
foreach ($item['options'] as $i=>$n) {
$newStore = $item['store'];
$newStore[] = $n;
// every combine can be ordered, so accept only options that are greater than store numbers
$newOptions = array_slice($item['options'], $i + 1);
// array_unshift to sort numerically, array_push to reverse
array_unshift($stack, array(
'store' => $newStore,
'options' => $newOptions,
));
}
}
return $result;
}
function get_all_combinations( $numbers ){
$length = count($numbers);
$result = [];
while ($length > 0) {
$result = array_merge($result, get_combinations_with_length( $numbers, $length ));
$length--;
}
return $result;
}
$numbers = [1,2,3,4];
$result = get_all_combinations($numbers);
echo 'START: '.json_encode( $numbers ).'<br><br>';
echo 'RESULT: '.json_encode( $result ).'<br><br>';
echo '('.count($result).' combination subsets found)';
- designosis
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接