An efficient algorithm for a special case of the set partition problem
Alan Jackson, Prakash V. Ramanan · International Journal of Computer Mathematics · 1990
In this paper, we study the Two Functions Set Partition Problem, which is defined as follows:Given a set S of n elements, functions f 1 and f 2 from S to S, and an initial partition B= (B 1 B 2,…,B s) of S, find the coarsest refinement E = (E 1,E 2,…E t) of B such that for each i i= 1,2, and j, 1 ≦ j≦t,f i (E j ) ⊆ E k for some k. For the special case when f 1consists of a single cycle, we present an 0(n β(n)) algorithm, where β(n) is the number of distinct prime factors of n. β(n) is loglog n+ o(loglog.n) for almost all n, and is Θ(log n/log log n) in the worst case. This algorithm represents an improvement over the previously known O(nlogn) algorithm.