SetPartition uses, as internal representation, a CloneableArray with each element being a Set. The latter makes the creation and manipulation of set partitions very slow.

Moreover, the current iterator over set partitions is much slower than necessary.

For example, to generate a list containing the set partitions of a 7 element set, I currently use about 3.3 seconds. Replacing the iterator with a straightforward algorithm from Ruskey's book I can achieve 470 ms. Removing the call to Set, this goes down to 16 ms.

Depends on #25497

CC: @alauve @tscrim @zabrocki

Component: combinatorics

Author: Martin Rubey, Travis Scrimshaw

Branch/Commit: ba6a115

Reviewer: Mike Zabrocki, Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/25462