集约简递归算法 - set reduction recursive algorithm

set reduction recursive algorithm

本文关键字：递归算法 | 更新日期: 2023-09-27

给定(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, D] = [D,C,A] = [D,C,A] =等等

是否有一种方法可以不生成幂集并减少它，因为7个元素的幂集是n^7，这很快就会耗尽

看一下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]，因此两者都在结果集中)