c++ - 条件字典排列

Question

因此，我阅读了可以生成字典顺序排列的算法。如:1-2-3-4-5->1-2-3-5-4->1-2-4-3-5->...->5-4-3-2-1

但是我想在跳过一些排列的地方强加一些 bool 条件。

假设我有:1-2-3-4-51-2-3-5-4...我想跳过所有其他 1-2-X-X-X然后转到 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 并采用级别和排列(引用)的函数的指针 vector ，如果条件在给定级别失败，则返回而不做任何事情，所以假设您可以创建这样的乐趣:

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，您可以从 vector 中删除它们。