生成所有输入组合/排列的高效 PHP 算法

Question

我正在尝试为多个输入计算数组中一组值的所有组合。类似于这个问题：

PHP 算法从单个集合生成特定大小的所有组合

例如：

function sampling($chars, $size, $combinations = array()) {

  if (empty($combinations)) {
      $combinations = $chars;
  }

  if ($size == 1) {
      return $combinations;
  }

  $new_combinations = array();

  foreach ($combinations as $combination) {
      foreach ($chars as $char) {
          $new_combinations[] = $combination . $char;
      }
  }
  return sampling($chars, $size - 1, $new_combinations);
}

$chars = array('a', 'b', 'c');
$output = sampling($chars, 2);
echo implode($output,', ');

输出：

aa, ab, ac, ba, bb, bc, ca, cb, cc

但问题是当我把它提升到一个更大的列表时，例如：

$chars = array('a', 'b', 'c', 'd');
$output = sampling($chars, 12);

排列的数量急剧增加，PHP 内存不足。显然，解决方案是使用生成器并在整个循环中产生结果。不过，生成器的唯一示例是针对略有不同的问题集：

参见：https : //stackoverflow.com/a/27160465/345086

关于如何使用生成器来解决这个问题的任何想法？

Answer 1

试一试：

<?php
$chars = array('a','b','c');
$count = 13;

$generator = genCombinations($chars,$count);
foreach ($generator as $value) {
  // Do something with the value here
  echo $value;
}

function genCombinations($values,$count=0) {
  // Figure out how many combinations are possible:
  $permCount=pow(count($values),$count);

  // Iterate and yield:
  for($i = 0; $i < $permCount; $i++)
    yield getCombination($values, $count, $i);
}

// State-based way of generating combinations:
function getCombination($values, $count, $index) {
  $result=array();
  for($i = 0; $i < $count; $i++) {
    // Figure out where in the array to start from, given the external state and the internal loop state
    $pos = $index % count($values);

    // Append and continue
    $result[] = $values[$pos];
    $index = ($index-$pos)/count($values);;
  }
  return $result;
}

它是一种基于状态的固定长度组合生成器，有望满足要求。它只接受数组并返回数组项的组合，而不管数组中实际存储的是什么。