c++ - 更智能的排列循环

Question

我有一个 3 x 3 的 bool 值网格，我感兴趣的是我可以拥有恰好三个“活”单元格的方法的数量(根据我的计算，有 56 种排列)。旋转对称性无关紧要，但活细胞彼此无法区分。

假设我正在索引网格中相对于质心的值:

-------------------
|-1,-1| 0,-1| 1,-1|
-------------------
|-1,0 |     | 1,0 |
-------------------
|-1,1 | 0,1 | 1,1 |
-------------------

是否有一个很好的循环可以用来计算 56 种排列？ (我刚刚把它全部打完，我很想知道我是否可以更聪明一点)。

我使用的是 C++，但基本算法在任何语言或伪语言中都会很棒，如果它很清楚的话。

Answer 1

您可以使用 next_permutation .

例如，假设字符串下面 x 中的每个字符代表网格中的一个单元格(质心单元格除外)从左上角开始到右下角。您可以运行此代码来查找所有可能的排列，在循环内，字符串 x 将代表一种可能的排列，其中 1 是活细胞，0 是死细胞。

int main() {
  string x = "00000111";
  int cnt = 0;
  do {
    ++cnt;

    // do something useful with this configuration...

  } while(next_permutation(x.begin(),x.end()));
  cout<<cnt<<endl;
  return 0;
}