PHP获取所有组合

Question

我看到了这个算法，它可以接受数字或单词，并找出所有可能的组合。

我正在使用它，但它并没有返回所有“真实”的组合。

PHP：

<?php
    require_once 'Math/Combinatorics.php';
    $words = array('cat', 'dog', 'fish');
    $combinatorics = new Math_Combinatorics;
    foreach($combinatorics->permutations($words, 2) as $p) {
        echo join(' ', $p), "\n"; 
    }
?>

它返回：

cat dog
dog cat
cat fish
fish cat
dog fish
fish dog

但这些并不是所有真实的组合，所有真实的组合也包括这些：

cat cat
dog dog
fish fish

这就是我所需要的，获取所有真实组合的方法：

cat dog
dog cat
cat fish
fish cat
dog fish
fish dog
cat cat
dog dog
fish fish

- Minion

---

为什么不自己添加这些组合呢？循环遍历数据并手动添加这些对似乎很容易。 - laurent

这不是之前的同一个问题吗？你似乎只是对答案有疑虑。为什么不在那里继续讨论呢？ - Nanne

“Math_Combinatorics”是一个软件包，它能返回给定集合和子集大小的所有组合和排列，而且不会重复。该软件包还保留关联数组。关键要点在于“不会重复”。 - strkol

如果这只是为了好玩，编写自己的函数来添加重复项并不难。如果不仅仅是为了好玩，可能有更好的方法来实现你想要的功能。 - jasonlfunk

看一下我的代码... :-) - Dr.Kameleon

这是因为您正在使用排列的代码，而不是组合。 - Juan Antonio Orozco

Answer 1

好的，这是你的代码（顺便说一句，感谢您发布这样一个有趣和具有挑战性的问题-至少对我来说是这样）- 使用递归 来获取给定元素数组的所有可能排列（按N）

代码:

<?php

function permutations($arr,$n)
{
     $res = array();

     foreach ($arr as $w)
     {
           if ($n==1) $res[] = $w;
           else
           {
                 $perms = permutations($arr,$n-1);

                 foreach ($perms as $p)
                 {
                      $res[] = $w." ".$p;
                 } 
           }
     }

     return $res;
}

// Your array
$words = array('cat','dog','fish');

// Get permutation by groups of 3 elements
$pe = permutations($words,3);

// Print it out
print_r($pe);

?>

输出：

Array
(
    [0] => cat cat cat
    [1] => cat cat dog
    [2] => cat cat fish
    [3] => cat dog cat
    [4] => cat dog dog
    [5] => cat dog fish
    [6] => cat fish cat
    [7] => cat fish dog
    [8] => cat fish fish
    [9] => dog cat cat
    [10] => dog cat dog
    [11] => dog cat fish
    [12] => dog dog cat
    [13] => dog dog dog
    [14] => dog dog fish
    [15] => dog fish cat
    [16] => dog fish dog
    [17] => dog fish fish
    [18] => fish cat cat
    [19] => fish cat dog
    [20] => fish cat fish
    [21] => fish dog cat
    [22] => fish dog dog
    [23] => fish dog fish
    [24] => fish fish cat
    [25] => fish fish dog
    [26] => fish fish fish
)

提示：通过permutations($words,2)，您将能够得到您想要的东西...

- Dr.Kameleon

---

我正在尝试将其转换为返回一个数组的数组，而不是一个字符串的数组。因此，每个内部数组将有$n$个元素。这比看起来应该更困难... - still_dreaming_1

现在可以使用组合计算的pear类。 - still_dreaming_1

实际上，组合数学课确实对某些事情有帮助，但它与此不同，因为它不会像这个解决方案一样生成具有重复值的子集。我仍然需要一个适用于数组而不是字符串的版本。 - still_dreaming_1

Answer 2

您当前的代码提供了排列，只需添加重复项：

foreach($words as $w) {
    echo "$w $w\n";    
}

有什么问题吗？

- William R

---

问题在于这不是通用的，如果你要处理超过2维的情况，它就无法工作：在3维中，他需要添加 cat cat fish，cat fish cat，fish cat cat。等等...这是组合数学。 - Ellert van Koperen