OT: algorithm for generating all possible combinations with replacement

[Deron Meranda]

> I have n objects and I want to select k of these with replacement.
> Do you know of code which would generate all the possible
> arrangements?

Here's some python code.  It is also a generator, which
means it can be used in a for loop and only consumes
a constant amount of memory and time (per output)... O(1).

Use it like,

   items = ['red','blue','green','yellow']
   k = 5
   for choice in choices_with_replacement( items, k ):
       print choice

The code...

def choices_with_replacement( list_of_items, number_of_picks ):
    k = number_of_picks
    n = len(list_of_items)
    if k==0 or n==0:
        return
    b = [0]*k      # make list [0,0,0,....,0] - of length k
    bdone = [0]*k
    while True:
        choice = [list_of_items[i] for i in b]
        yield tuple(choice)
        # Modify b in place (an addition operation in base-n)
        for i in range(k):
            b[i] += 1
            if b[i] < n:
                break  # break our of for loop, no need to carry
            b[i] = 0  # carry
        if b == bdone:
            break # break out of while loop, no more choices left
    return


If you want to run it from the command line, create a file
"choices.py" and put

#!/usr/bin/env python

as the first line.  And then the function defintion above,
and then this at the bottom of the file:

import sys
if __name__ == '__main__':
   k = int( sys.argv[1] )
   for choice in choices_with_replacement( sys.argv[2:], k ):
      print choice

You can then call it on the shell command line, with 'k' as
the first argument and the rest of the arguments are your
possible choices, like,

$ ./choices.py 5 red blue green yellow
--
Deron Meranda