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
