У меня есть массив из 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 слотов, не обращая внимания на порядок.
Ответ 1
Вы можете использовать решение, найденное здесь 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, ' ';
Вывод будет таким:
12345 12346 12347 12356 12357 12367 12456 12457 12467 12567 13456 13457 13467 13567 14567 23456 23457 23467 23567 24567 34567
Ответ 2
php код:
<?php
echo "<pre>";
$test = array("test_1","test_2","test_3");
// получить комбинацию
$return = uniqueCombination($test);
//сортировка
sort($return);
// вывод
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
)
Ответ 3
Библиотека «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
Ответ 4
Еще одно решение, основанное на стеке. Оно очень быстрое, но потребляет много памяти. Надеюсь, это кому-нибудь поможет. Подробнее:
function _combine($numbers, $length) {
$combinations = array();
$stack = array();
// все комбинации могут быть упорядочены
sort($numbers);
// запуск
array_push($stack, array(
'store' => array(),
'options' => $numbers,
));
while (true) {
// открыть элемент
$item = array_pop($stack);
// конец стека
if (!$item) {
break;
}
// действительное хранилище
if ($length <= count($item['store'])) {
$combinations[] = $item['store'];
continue;
}
// обход, когда опций недостаточно
if (count($item['store']) + count($item['options']) < $length) {
continue;
}
foreach ($item['options'] as $index => $n) {
$newStore = $item['store'];
$newStore[] = $n;
// каждая комбинация может быть упорядочена
// поэтому принимаем только варианты, которые больше, чем максимальное число вариантов
$newOptions = array_slice($item['options'], $index + 1);
// вставляем новые элементы
array_push($stack, array(
'store' => $newStore,
'options' => $newOptions,
));
}
}
return $combinations;
}
Ответ 5
Улучшаем предыдущий ответ, чтобы он работал и с ассоциативным массивом:
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
)
)
Ответ 6
Новое решение, оптимизирующее скорость и память для алгоритма комбинирования.
Задача: генерировать комбинации 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;
}
}
// выполнение
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);
Ответ 7
Мне нужна была объединяющая функция, включающая подмножества, поэтому я взял предыдущий ответ и изменил его для своих нужд. Если передать в функцию [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();
// все комбинации могут быть упорядочены
sort($numbers);
// запуск
array_push($stack, array(
'store' => array(),
'options' => $numbers,
));
while (true) {
// открыть элемент
$item = array_pop($stack);
// конец стека
if (!$item) break;
// действительное хранилище
if ($length <= count($item['store'])) {
$result[] = $item['store'];
continue;
}
// обход, когда опций недостаточно
if (count($item['store']) + count($item['options']) < $length) {
continue;
}
foreach ($item['options'] as $i=>$n) {
$newStore = $item['store'];
$newStore[] = $n;
// каждая комбинация может быть упорядочена, поэтому принимайте только те варианты, которые больше, чем номера индексов в массиве
$newOptions = array_slice($item['options'], $i + 1);
// array_unshift для сортировки по числам, array_push для обратной сортировки
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)';
Web
