The Computer Journal · 1988 · 37 citations · 0 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsSet TheoryAlgorithm AnalysisData PartitioningEnumerative CombinatoricsFinite Set PartitioningPartition AnalysisPartition Enumeration AlgorithmsPartitioning ProblemsRecursive Algorithm DesignRecursive PartitioningSet Partitioning ProblemSet Partitions
A recursive algorithm for generating all partitions of the set {1, 2, …, n} is presented. The average time complexity per partition generated of this algorithm is 𝛉(1.6). This algorithm runs faster than the previously fastest algorithm, whose average time complexity per partition is 𝛉(4). An empirical test confirms that this is indeed the case.