php - 如何修改传统的笛卡尔积以减少内存开销？

Question

对于我的问题，你要从5-10000个项目中选择多达24个项目换句话说，我们正在生成配置。
数字24来自项目类别，每个项目都与特定的安装位置相关联，位置1中的项目无法安装在位置10中，因此我已安排关联数组将数据分组组织。每个项目看起来像：

$items[9][] = array("id" => "0", "2" => 2, "13" => 20);

其中第一个参数（ $item[9]）告诉您允许它进入的位置。如果你想的话，可以考虑这样一个想法：你不能在排气管的位置安装轮胎。
这些项存储在mysql数据库中。用户可以指定对解决方案的限制，例如，属性2的最终值必须为25或更多。它们可以有多种竞争限制。查询检索对所考虑的属性具有任何值的项（存储了未指定的属性，但我们不对它们进行任何计算）然后，PHP脚本删掉所有多余的选项（例如：如果项1的属性值为3，而项2的属性值为5，则在没有其他选项的情况下
限制您永远不会选择项目1）。
所有处理完成后，获取一个关联数组，该数组如下所示：

$items[10][] = array("id" => "3", "2" => 2, "13" => 100);
$items[10][] = array("id" => "4", "2" => 3, "13" => 50);
$items[9][] = array("id" => "0", "2" => 2, "13" => 20);
$items[9][] = array("id" => "1", "2" => -1, "13" => 50);

我在 this pastebin link.发布了一个完整的示例数据集，有理由相信我可以对数据集中接受的内容进行更多限制，但即使每个选项限制2个元素，也会有问题。
在array（）值中，id是对数组中项的索引的引用，其他值是属性id和值对因此 $items[10][] = array("id" => "3", "2" => 2, "13" => 100);意味着在位置10中有一个id为3的项，该项在属性2中的值为2，在属性13中的值为100。如果它有助于思考由一对标识的项目，例如（10,0）是位置10中的项目0。
我知道我没有具体说明，有61个属性，我不认为它们会改变问题的结构如果我们愿意，我们可以把属性2看作权重，属性13看作成本用户希望解决的问题可能是生成一个配置，其中权重正好为25，并且成本最小化。
信封背面的数学表示，如果每个位置只有2个选项，粗略估计是2^24个选项x记录大小。假设一个32位整数可以通过某种方式编码来表示一条记录，那么我们看到的是16777216*4=67108864字节的内存（完全忽略了数据结构开销），没有理由相信这两个假设都是有效的，尽管一个内存上限为67megs的算法是可以接受的内存大小。
没有特别的理由坚持这种表示，我使用了关联数组，因为我有一个可变数量的属性来使用和计算，这将允许我避免一个大的，稀疏的数组。上面的“2”=>2实际上意味着id为2的过滤属性的值为2，类似的，属性13的值为100我很高兴把我的数据结构改成更紧凑的。
我的一个想法是，我确实有一个评估标准，可以用来丢弃大多数中间配置。作为一个例子，我可以计算75*“值为”2“+10*”值为”13“，以提供解的相对权重。换言之，如果对一个问题没有其他限制，则属性2中每增加1个值将花费75，属性13中每增加1个值将花费10。继续一个汽车零件的想法，把它想成购买一个库存零件，并让一个机械师修改它，以符合我们的规格。
我发现过早丢弃配置的一个问题是，权重函数没有考虑诸如“最终结果必须具有正好为25的值”之类的限制。所以，如果我有一个完整的24元素配置，我可以运行一个限制循环，丢弃不匹配的解决方案，然后根据函数对剩余的解决方案进行排序，但我不确定是否有一个有效的思路允许我更早地丢弃解决方案。
有人对如何前进有什么建议吗？尽管语言不可知的解决方案很好，但如果有一些相关的语言特性可能有用的话，我将在php中实现。

Answer 1

我通过执行深度优先笛卡尔积解决了内存问题我可以一次一个地权衡解决方案，如果我选择或只是像在这个代码片段中所做的那样输出它们，我可以保留一些解决方案。
这个解决方案的主要灵感来自the very concise answer on this question。这是我的代码，因为找到一个php深度优先笛卡尔积算法似乎不那么简单。

function dfcartesian ( $input, $current, $index ) {
    // sample use: $emptyArray = array();
    //             dfcartesian( $items, $emptyArray, 0 )
    if ( $index == count( $input ) ) {
        // If we have iterated over the entire space and are at the bottom
        // do whatever is relevant to your problem and return.
        //
        // If I were to improve the solution I suppose I'd pass in an
        // optional function name that we could pass data to if desired.
        var_dump( $current );
        echo '<br><br>';
        return;
    }

    // I'm using non-sequential numerical indicies in an associative array
    // so I want to skip any empty numerical index without aborting.
    //
    // If you're using something different I think the only change that
    // needs attention is to change $index + 1 to a different type of
    // key incrementer.  That sort of issue is tackled at
    // https://stackoverflow.com/q/2414141/759749
    if ( isset ( $input[$index] ) ) {
        foreach ( $input[$index] as $element ) {
            $current[] = $element;
            // despite my concern about recursive function overhead,
            // this handled 24 levels quite smoothly.
            dfcartesian( $input, $current, ( $index + 1 ) );
            array_pop( $current );
        }
    } else {
        // move to the next index if there is a gap
        dfcartesian( $input, $current, ( $index + 1 ) );
    }
}   

我希望这对其他人解决同样的问题是有用的。