-1

I want to group them in all possible ways.

For example: If we have 5 stones, we will have 7 different ways to group them.

X   X   X   X   X
XX   X   X   X
XXX   X   X
XXX   XX
XX   XX   X
XXXX   X
XXXXX

I've been trying to get the algorithm out all day but I can not get it, do you have any idea how to do this?

Thanks

Akai shur
  • 187
  • 1
  • 18
  • Can you show some attempts and what was not working with these? – Willem Van Onsem Nov 17 '18 at 19:43
  • 1
    You can here use a form of *dynamic programming* for this. – Willem Van Onsem Nov 17 '18 at 19:43
  • This question has been asked here many times before, usually in a different context. Look at [this web site](https://en.wikipedia.org/wiki/Partition_(number_theory)) for more on this topic of *partitions*. – Rory Daulton Nov 17 '18 at 20:03
  • Yes, I currently have a formula that works for me in some cases but not very large numbers. The formula that I am implementing recursively is import math n = 10 p = [0,1,2] for i in range (3, n + 1): p.append ((sum (p) + 1-2) / 2 + 2) print (p) The idea is to add the previous possibilities and add the current one. – Akai shur Nov 17 '18 at 20:04

1 Answers1

2

This is equivalent to finding integer partitions of the number of stones you have. For example:

5 = 1 + 1 + 1 + 1 + 1    -->     X     X   X   X   X
5 = 2 + 1 + 1 + 1        -->     XX    X   X   X
5 = 3 + 1 + 1            -->     XXX   X   X
5 = 2 + 2 + 1            -->     XX    XX  X
5 = 4 + 1                -->     XXXX  X
5 = 3 + 2                -->     XXX   XX
5 = 5                    -->     XXXXX

Each line encodes a possible group configuration, where each integer on the right hand side represents the number of stones in a group.

arshajii
  • 127,459
  • 24
  • 238
  • 287
  • Or the stars and bars problem: https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) – slider Nov 17 '18 at 20:07
  • 1
    @slider They're slightly different: in this case we're distributing identical objects into *identical* bins, whereas stars+bars is _distinct_ bins. – arshajii Nov 17 '18 at 20:08
  • Agreed. Although you just need to account for the permutations of the bins. – slider Nov 17 '18 at 20:12
  • @slider: "just need to account" there is what we use to call "hand-waving". It's not nearly so simple. – rici Nov 18 '18 at 02:17
  • @rici "It's obvious". Ok I may have slightly underestimated the difficulty. – slider Nov 18 '18 at 03:23