代码之家 › 专栏 › 技术社区 › vxs8122

列出n个对象的所有k置换的有效方法,同时满足特定标准

permutation optimization algorithm c++

vxs8122 · 技术社区 · 6 年前

标准是最多允许一个空对象,并且每个对象只能重复一次。

这是我目前为止的尝试。

假设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  ----- */

1 回复 | 直到 6 年前

David Eisenstat 6 年前

注意,如果生成 pool ,那么length-k前缀几乎就是您想要的,只是有大量连续的重复项。生成所有k置换的一种简单但体面的方法是,在调用之前将n-k后缀排序为降序,从而跳过重复项 next_permutation .也就是说,

#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';
  }
}

通过实现自己版本的 下一个\u置换 这将n-k后缀视为反向排序,但我现在似乎在Knuth 4A中找不到它。

推荐文章

Hatsune Miku · 比较或if语句是否更快[已关闭]

1 年前

Sky Full Of Stars · 最小化工作流程以及部门和工作站之间的距离

1 年前

Black Swan · 无法解压缩的值太多(应为2)错误

1 年前

Kai · 有什么方法可以轻松优化VSCode中的锈迹?

2 年前

Balfar · 处理NumPy阵列上的循环最有效的方法是什么?

2 年前

santobedi · 使用内部支持的优化器优化scikit learn中用于探地雷达的RBF核的核参数

6 年前

Daniel · C#轻松存储快速访问的大型位矩阵

6 年前

halbe · 优化音频DSP程序的numpy计算

6 年前

Afsara · 是否有任何方法不能优化我们的应用程序?

6 年前

user7353167 · R中预算分配的优化(以前叫Excel Solver)

6 年前