标准是最多允许一个空对象,每个对象只能重复一次。
这是我到目前为止的尝试。
假设 n = 3,k = 3。 设 0 表示为空对象。
一些可能的例子:
011 101 110 112
012 102 120 113
013 103 130 121
... ... ... ...
033 303 330 332
因此,我创建了一个 { 0, 1, 1, 2, 2, 3, 3 } 的"池"。 将使用逻辑向量的排列从池中选择三个对象(例如,逻辑向量 { 0, 1, 0, 0, 0, 1, 1 } 从池中选择 1, 3, 3(
然后将三个选定对象的所有排列添加到集合中。
然而。。。会有一些重复,因为 { 0
, 1, 0, 0, 0, 1, 1 } 被视为等效于 { 0, 0, 1, 0, 0, 1, 1, },因为两者都会从池中选择 1, 3, 3。对于较高的 n 和 k,此代码的计算成本非常高,例如当 n = 8 和 k = 6 时。 有没有更有效的方法可以做到这一点?
我的C++代码:
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 ----- */
观察一下,如果你生成pool
的所有排列,那么 length-k 前缀几乎就是你想要的,只是有大量连续的重复项。生成所有 k 排列的一种简单但体面的方法是通过在调用 next_permutation
之前将 n - k 后缀排序为降序来跳过重复项。也就是说,
#include <iostream>
#include <set>
#include <vector>
using std::cout;
using std::greater;
using std::sort;
using std::vector;
vector<vector<int>> generate_kperms(int n, int k) {
vector<vector<int>> kperms;
vector<int> pool(2 * n + 1);
pool[0] = 0;
for (int i = 1; i <= n; ++i) {
pool[2 * i - 1] = pool[2 * i] = i;
}
do {
kperms.push_back(vector<int>(pool.begin(), pool.begin() + k));
sort(pool.begin() + k, pool.end(), greater<int>());
} while (next_permutation(pool.begin(), pool.end()));
return kperms;
}
int main() {
for (const vector<int> &kperm : generate_kperms(8, 6)) {
for (int x : kperm) {
cout << x << ' ';
}
cout << 'n';
}
}
您可以通过实现自己的next_permutation
版本来提高速度,该版本将 n - k 后缀视为反向排序,但我现在似乎无法在 Knuth 4A 中找到它。