README

内存高效的PHP排列组合生成器。

这两个类都是生成器，它们不会产生比输入集多一个额外副本的额外内存需求。

这个库是为了回答FreeNode上的##php频道的一个关于排列/组合生成的问题而编写的，在简要调查了替代方案后，发现只有内存中递归生成越来越大的结果集的解决方案。

我还想在这个文档中加入“组合数学”这个词，以便搜索引擎能找到它。 :)

注意事项

• 迭代器的输入数组必须以数字索引方式索引，索引之间不能有间隔。[参见：array_values()]
• 这两个生成器都不考虑间隔或重复，所有元素都假定是唯一的。
• 如果你存储这些生成器的结果，你仍然会遇到内存问题。
• 这不是计算可能排列和组合数量的理想方法。[参见：数学]
• 这不是生成类似“所有可能的非顺序、非重复ID”的理想方法。[参见线性反馈移位寄存器或直接使用UUID]

类

• CombinationIterator: 从输入集中生成所有可能的N个元素的组合。
  • 使用递归的Gray Code方法。
  • 栈深度不应超过输出集中元素的数量。
• PermutationIterator: 生成输入集的所有可能的排列。
  • 使用非递归形式的Heap算法。
  • 在输入集的副本上就地操作。

安装

composer require wrossmann/pc-iters

用法

CombinationIterator

函数签名和docblock

/**
 * Given a set of items, generate all unique combinations of the
 * specified number of items using a Gray Code-ish method.
 * 
 * @param	array	$set	The set of items
 * @param	int		$count	The number of items in the output set
 * @param	int		$begin	Offset in the set to start.
 * @param	int		$end	Offset in the set to end. [non-inclusive]
 */
public static function iterate($set, $count, $begin=NULL, $end=NULL)

示例

use wrossmann\PCIters\CombinationIterator;

foreach( CombinationIterator::iterate([1,2,3,4,5], 3) as $comb ) {
	printf("%s\n", json_encode($comb));
}

输出

[1,2,3]
[1,2,4]
[1,2,5]
[1,3,4]
[1,3,5]
[1,4,5]
[2,3,4]
[2,3,5]
[2,4,5]
[3,4,5]

PermutationIterator

函数签名和docblock

/**
 * Given a set of items generate all possible unique arrangements
 * of items. Uses Heap's Algorithm.
 * 
 * @param	array	$set	The set of items on which to operate.
 */
public static function iterate($set)

示例

use wrossmann\PCIters\PermutationIterator;

foreach( PermutationIterator::iterate([1,2,3]) as $comb ) {
	printf("%s\n", json_encode($comb));
}

输出

[1,2,3]
[2,1,3]
[3,1,2]
[1,3,2]
[2,3,1]
[3,2,1]