1

I am trying to generate all partitions of a given set. Let's say we have the set {1, 2, 3}. All of its partitions would be:

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

Looking at the output, I am headed in the direction that I should generate combinations for i elements from the set, with i being from 1 to [set length], and while on combination i I should recursively generate combinations for elements j- j being from 1 to [set length - i]. I tried that idea on paper and it looks like it checks out, but I'm having a difficulty writing it in code.

I am using C++ and for my idea to work I need to have an algorithm that can yield the next combination, not just all combinations. But the thing is I don't want to use yield operators, generators and so on as they will make the algorithm non trivial to implement.

P.S. I know there a lot of duplicates on this question, but I did not find any of them helpful. P.S. 2 I've not shown any code as all I have is work scribbles and not anything concise.

MultiValidation
  • 823
  • 7
  • 21
  • At least give it a try. Don't give up. If you can do it on paper you can code it. – Nikhil Badyal Nov 07 '19 at 08:11
  • I did give it a lot of tries haha. I'm not even sure that my idea is feasible. I've not given up at all, but I need a nudge in the right direction :) – MultiValidation Nov 07 '19 at 08:13
  • https://www.informatik.uni-ulm.de/ni/Lehre/WS03/DMM/Software/partitions.pdf and https://www.informatik.uni-ulm.de/ni/Lehre/WS03/DMM/Software/partitions-source.tar.gz – Jerry Jeremiah May 04 '22 at 02:18

0 Answers0