c++ - 条件词典排列

Question

所以我读过可以生成字典排列的算法。如：1-2-3-4-5->1-2-3-5-4->1-2-4-3-5->...->5-4-3-2-1

但是，我想在跳过一些排列的情况下强加一些布尔条件。

假设我有： 1-2-3-4-5 1-2-3-5-4 。. . 我想跳过所有其他 1-2-XXX 并转到 1-3-2-4-5

交换 2 和 3 并对剩余的三个数字进行排序是最好的方法吗？或者还有其他更快的方法吗？

Answer 1

我仍然不太明白你的问题，但从我看到的你可以基于这段代码：

vector<int> permutation;
for (int i = 1; i < N; ++i)
   permutation.push_back(i);
void gen_perm(int level, vector<int>& per){
  if (level < N-1);
    for (int i = level; i < N; ++i) {
        swap(per[level], per[i]);
        gen_perm(level + 1, per);
        swap(per[level], per[i]);
    }
  else
    print(per) or return per or whatever you want to do with perms.
}

现在，条件呢？您可以将它们传递给 gen_perm 函数，例如指向返回 bool 并采用级别和排列（引用）的函数的指针向量，如果条件在给定级别失败，则不做任何事情返回，所以假设您可以创建这样的乐趣：

bool check_3(int level, vector<int>& perm) {
   if (level == 2)
      if (perm[0] + perm[1] == 3) return false;
   return true;
}

我建议你首先：

typedef bool (*cond_fun)(int, vector<int>&);

在 gen_loop 中使用它们，例如：

void gen_perm(int level, vector<int>& per, vector<cond_fun>& conds){
  if (level < N-1);
    for (int i = 0; i < conds.size(); ++i) {
       if (!(*conds[i])(level, per)) return;
    }
    for (int i = level; i < N; ++i) {
        swap(per[level], per[i]);
        gen_perm(level + 1, per, conds);
        swap(per[level], per[i]);
    }
  else
    print(per) or return per or whatever you want to do with perms.
}

当然，如果你有额外的知识，你可以改进它：每个条件最多可以失败一次，所以如果它们返回 false，你可以从向量中删除它们。

Answer 2

您所询问的内容称为阶乘基数，您可以在需要时以正确的数量推进计数器。您可以在这里阅读更多相关信息：http: //efesx.com/2009/11/14/enumerating-permutations/（以及http://marknelson.us/2002/03/01/next-permutation/）