Next Composition of n into k parts - does anyone have a working algorithm? [closed]

Question

Composition of n into k parts - I want to list all the possible compositions of n into k parts - does anyone have an algorithm (preferably in R)? Or know if it's in library anywhere?

For example, if I have n cubes, and k bags, and want to list all the possible arrangements of the cubes in the bags. e.g. there are 3 ways you can arrange 2 cubes into 2 bags:

(2, 0) (1, 1) (0, 2)

I've found the NEXCOM alogarithm. I've found a version of it here (page 46) in Fortran, but don't code in Fortran so really understand what's going on - any help?

Answer 1

Since it took me a bit of effort to read the intention of the other c++ solution here a translation to python (also as generator result instead of string):

def weak_compositions(boxes, balls, parent=tuple()):
  if boxes > 1:
    for i in xrange(balls + 1):
      for x in weak_compositions(boxes - 1, i, parent + (balls - i,)):
        yield x
  else:
    yield parent + (balls,)

test:

>>> for x in weak_compositions(3, 5): print x
(5, 0, 0)
(4, 1, 0)
(4, 0, 1)
(3, 2, 0)
...
(0, 1, 4)
(0, 0, 5)