# Efficient way of partitionning a set into a fixed number of parts

I am looking for a way of efficiently partitionning a set of consecutive integers in to a set where the number $$K$$ of parts is given.

For instance, for the set {1, 2, 3, 4}, I would like the best way of generating the list of $$K=2$$ parts.

The result should be the list of partitions, for instance :

{{1},{2, 3, 4}}

{{1, 2},{3, 4}}

{{1, 3},{2, 4}}

and so on...

I am looking for references, or names of algorithm.

Thank you very much

• There is an obvious recursive algorithm. Commented Jan 12, 2022 at 9:58
• Thank you @Gribouillis I am looking for state-of-the-art algorithms. Commented Jan 12, 2022 at 10:03
• Most reasonable approaches will be close to optimal, as you can't do any better than the number of partitions in terms of time. Commented Jan 12, 2022 at 10:23
• There will be $K^n$ different partitions (assuming empty partitions are permissible). If you want the algorithm to list them all, printing the solution will dictate the complexity and any naive approach will do. If you need just one solution that can be solved trivially. Commented Jan 12, 2022 at 10:42