generating all possible k partition of an array

Question

actually, I confronted a problem for generating all possible k partitions of an array. I tried to write the algorithm but actually, I am not able to.

can anybody please give me the idea, how to code this problem ?

for example

suppose I am given an array A[] = {1, 2, 3, 4, 5} and k = 3, then I have to write the code for all possible partition for k =3. in this example, our all possible partitions are for k =3 is as follows
{1}, {2}, {3, 4, 5}
{1}, {2, 3}, {4, 5}
{1, 2}, {3}, {4, 5}
{1, 2}, {3, 4}, {5}
{1, 2, 3} , {4}, {5}
{1}, {2, 3, 4}, {5}

thanks, any effort is appreciatable.

Answer 1

If we look closely at the problem, the only thing to determine here is the $k-1$ places in the array where to put "breaks" to separate it into $k$ sets. You can generate all those combinations with nested loops or recursion. For reference, see Stars and Bars.

Is it maybe that one such partition you are looking for would also be, say $$\{2\},\{3,4\},\{5,1\}?$$

If yes, then you will also need to generate all permutations of an array before doing the stars and bars. You can generate all permutations with Heap's algorithm.