The criterion is that at most one empty object is allowed and each object can be repeated only once.
Here's my attempt so far.
Suppose that n = 3, k = 3. Let 0 denote as an empty object.
Some possible examples:
011 101 110 112
012 102 120 113
013 103 130 121
... ... ... ...
033 303 330 332
So, I create a "pool" of { 0, 1, 1, 2, 2, 3, 3 }. Three objects will be selected from the pool, by using a permutation of logical vector (ex. a logical vector { 0, 1, 0, 0, 0, 1, 1 } chooses 1, 3, 3 from the pool)
Then all the permutations of the three selected objects are added to the set.
However... there will be some repetition, since { 0, 1, 0, 0, 0, 1, 1 } is considered equivalent to { 0, 0, 1, 0, 0, 1, 1, } as both will choose 1, 3, 3 from the pool.
This code becomes pretty computationally expensive for higher n and k, such as when n = 8 and k = 6. Is there a more effective way to do this?
My C++ code:
set< vector<int> > generate_kperms ( int n, int k )
{
set< vector<int> > kperms;
// create vector of integers { 0, 1, 1, 2, 2, ..., n, n }
vector<int> pool( 2*n + 1 );
pool[0] = 0;
for ( int i = 1; i <= n; ++i )
pool[2*i-1] = pool[2*i] = i;
// create logical vector with k true values, to be permuted
vector<bool> logical( pool.size() );
fill( logical.end()-k, logical.end(), true );
do {
vector<int> kperm( k );
vector<int>::iterator itr = kperm.begin();
for ( int idx = 0; idx < (int) pool.size(); ++idx ) {
if ( logical[idx] )
*(itr++) = pool[idx];
}
do {
kperms.insert( kperm );
} while ( next_permutation ( kperm.begin(), kperm.end() ) );
} while ( next_permutation( logical.begin(), logical.end() ) );
return kperms;
} /* ----- end of function generate_kperms ----- */