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

Question

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

PHP algorithm to generate all combinations of a specific size from a single set

例如:

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;
}

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