生成差异度最高的前N%排列的算法技术问询

背景 #

我们需要用Monte Carlo方法估算一组含10个数值的数据集特征，但生成所有可能的排列不现实——仅10个元素的全排列数就有3628800个。目前采用随机生成少量排列子集的方式，但这种方法没有考虑排列间差异度不均的问题，无法高效覆盖差异显著的排列。

核心问题 #

是否存在一种排列生成算法，能够计算排列的差异度，并优先生成差异最显著的排列？这样我们就能在生成1000次排列后停止计算。

• 对差异度/相似度的度量方式无特定要求，距离、信息增益、熵、Spearman相关系数等指标均可。

当前使用的随机排列生成实现 #

当前采用的C++风格伪代码如下：

void permutate(const int n, int &out[])
{
  for(int k = 0; k < n; ++k) out[k] = k;
  for(int k = 0; k < n - 1; ++k)
  {
    int i1 = rand() % (n - k - 1) + 1;
    swap(out, k, k + i1);
  }
}

该方法通过重复执行预定义次数来生成排列，但存在一个问题：交换相邻元素与交换远距离元素的概率相同，无法保证生成的排列具有均匀的差异度分布。

内容的提问来源于stack exchange，提问作者Stan