OT: algorithm for generating all possible combinations with replacement

[Ryan James]

On Thu, 2005-11-24 at 21:22 -0800, Globe Trotter wrote:
> Dear all,
> 
> 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? Note that this is
> different from the selection of k of n objects without replacement and wanting
> to generate all the possible permutations.
> 
> Any suggestions? Existing C code would be fantastic btw, but I would be happy
> with an algorithm.
> 

this won't compile without a bit of tweaking, but it should be easy
(import some stl stuff, etc):

Vector calPerm(char[] n, int l, int k)
{
	Vector out();
	String base = "";
	add(base, n, l, k, out);
	return out;
}

void add(string prev, char[] n, int l, int k, Vector out)
{
	for(int i = 0; i < l; i++)
	{
		String temp = prev;
		temp += n[i];
		if(k == 1)
		{
			out.append(temp);
		}
		else
		{
			add(temp, n, l, k-1, out);
		}
	}
}

note that this takes O(n^k) time and plenty of space.  it's basically k
nested for loops but with k determined at run time.  l is the number of
elements in n, n is the set of items you're picking from (assumed chars
here), k is the number of times you pick, out is the vector with all
combinations in the form of strings.

-ryan