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

  • 2
    $\begingroup$ There is an obvious recursive algorithm. $\endgroup$ Jan 12 at 9:58
  • $\begingroup$ Thank you @Gribouillis I am looking for state-of-the-art algorithms. $\endgroup$
    – user7060
    Jan 12 at 10:03
  • 1
    $\begingroup$ Most reasonable approaches will be close to optimal, as you can't do any better than the number of partitions in terms of time. $\endgroup$
    – Tassle
    Jan 12 at 10:23
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ordoshsen
    Jan 12 at 10:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.