> 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
