php - 集合归约递归算法

Question

给定(A、B、C、D)

什么算法可以将其缩减为大小为 n 的唯一非重复集。

例如，如果 n 是 3。

[A,B,C]
[A,C,D]
[A,B,D]
[B,C,D]

你会注意到 A,A,A 不可能有效，A,A,B 和 [A,C,D] = [C,A,D] = [A,C,D] = [D ,C,A] = 等..

有没有办法不生成幂集并减少它，因为 7 个元素的幂集是 n^7，这很快就会穷尽。

Answer 1

看看Math_Combinatorics .

<?php
require 'Combinatorics.php';

$combinatorics = new Math_Combinatorics;
$result = $combinatorics->combinations( ['A','B','C','D'], 3 );
var_export($result);

打印

array (
  0 => 
  array (
    0 => 'A',
    1 => 'B',
    2 => 'C',
  ),
  1 => 
  array (
    0 => 'A',
    1 => 'B',
    3 => 'D',
  ),
  2 => 
  array (
    0 => 'A',
    2 => 'C',
    3 => 'D',
  ),
  3 => 
  array (
    1 => 'B',
    2 => 'C',
    3 => 'D',
  ),
)

它还有一个 permutations 方法(即 [A,B,C]!=[A,C,B] 因此两者都在结果集中)