在 PHP 中更改了 Combinations/Permutations 算法

Question

我很难编写一个接受数组和 returns 数组数组的函数。我不确定这是否会被视为组合、排列或其他。结果应该与我看到的其他一些排列组合算法类似，但不完全相同。

假设函数签名是这样的

function variable_length_permutations_with_duplicates($set_array, $max_subset_length)

然后这个代码：

$sets = variable_length_permutations_with_duplicates(array('a', 'b'), 2);

应该return像这样的数组：

[ ['a'], ['a','a'], ['a','b'], ['b], ['b','b'], ['b','a'], ]

它确实需要使用数组，因为值可以是任何东西，它们不一定是那个例子中的字符串。 return 数组中的子集不需要以任何特定顺序出现。

您是否知道任何 PHP 函数或类我可以用于这个或我可以翻译成 PHP 的另一种语言的参考实现？

Answer 1

您可以使用这段代码——我将函数名称缩短了一点 :) :

function perm($set_array, $max_subset_length, $prefix = []) {
    $result = [$prefix];
    if ($max_subset_length) {
        foreach ($set_array as $el) {
            $result = array_merge($result, 
                perm($set_array, $max_subset_length-1, array_merge($prefix, [$el])));
        }
    }
    return $result;
}

$sets = perm(array('a', 'b'), 2);   

print_r($sets);

请注意，在此逻辑中，空数组也包含在结果中。使用 if 您可以在函数的第一行中排除它，如下所示：

    $result = count($prefix) ? [$prefix] : [];

在 PHP 中更改了 Combinations/Permutations 算法

Altered Combinations/Permutations Algorithm in PHP

php

arrays

algorithm

combinations

permutation