PHP 中的排列和大数组 - 性能问题

Question

我有一个数字数组（int 或 float），我需要通过组合数组值来找到一个值。一旦找到最小可能的组合，该函数就会返回数组值。因此，我从样本大小=1开始并不断增加它。

这是给定数据的简化示例：

$values = [10, 20, 30, 40, 50];
$lookingFor = 80;

有效结果：

[30, 50] // return this
[10, 20, 50], [10, 30, 40] // just to demonstrate the possible combinations

排列解决了这个问题，我尝试了许多不同的实现（例如：排列 - 所有可能的数字组, 获取 PHP 数组的所有排列？, https://github.com/drupol/phpermutations）。我最喜欢的是这个，它带有使用生成器模式的排列大小参数：https://stackoverflow.com/a/43307800

我的问题是什么？性能！我的数组有 5 - 150 个数字，有时需要 30 个数组数字的总和才能找到搜索的值。有时找不到该值，这意味着我需要尝试所有可能的组合。基本上与排列大小> 5 任务变得太耗时。

另一种但不精确的方法是对数组进行排序，获取前 X 和后 X 数字并与搜索到的值进行比较。像这样：

sort($values, SORT_NUMERIC);
$countValues = count($values);

if ($sampleSize > $countValues)
{
    $sampleSize = $countValues;
}

$minValues = array_slice($values, 0, $sampleSize);
$maxValues = array_slice($values, $countValues - $sampleSize, $sampleSize);

$possibleMin = array_sum($minValues);
$possibleMax = array_sum($maxValues);

if ($possibleMin === $lookingFor)
{
    return $minValues;
}

if ($possibleMax === $lookingFor)
{
    return $maxValues;
}

return [];

希望有人处理过类似的问题并能引导我走向正确的方向。谢谢你！

Answer 1

• 您必须使用组合而不是排列{例如：P(15) = 130767436800 vs C(15) = 32768}

• if array_sum

  target_number 则不存在解决方案

• 如果 in_array(target_number,numbers) 找到包含 1 个元素的解

• 从最低到最高排序

• 从 C(n,2) 开始，其中 2 代表第 1 个、第 2 个、然后是第 1 个、第 3 个等（静态的是第一个元素）

• 如果上面的循环没有找到解决方案，则继续第 2 个第 3 个，然后是第 2 个第 4 个，等等）

• 如果 C(n,2) 没有解决方案，则跳转到 C(n,3)s，但这次是 2 个静态数字和 1 个动态数字< /p>

• 如果循环结束且无解，则不存在解

，我会调整这个问题并在堆栈交换的统计分支（交叉验证）中询问，因为数字总和的平均值、中值和累积分布可能暗示减少迭代次数意义重大，这是他们的职业。