3

我有一个 3 x 3 的布尔值网格，我对我可以拥有三个“活”单元格的方式感兴趣（据我计算，有 56 个排列）。旋转对称无关紧要，但活细胞彼此无法区分。

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

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

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

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

4

4 回答 4

4

您可以使用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;
}
于 2012-05-28T23:04:22.433 回答
1

从 Wikipedia尝试此过程。

以下算法在给定排列之后按字典顺序生成下一个排列。它就地改变了给定的排列。

  1. 找到满足 a[k] < a[k + 1] 的最大索引 k。如果不存在这样的索引，则排列是最后一个排列。
  2. 找到最大的索引 l 使得 a[k] < a[l]。由于 k + 1 是这样一个索引，所以 l 是很好定义的并且满足 k < l。
  3. 将 a[k] 与 a[l] 交换。
  4. 反转从 a[k + 1] 到最后一个元素 a[n] 的序列。
于 2012-05-28T23:04:02.900 回答
0

你可以使用这个方法：

假设你用一个数组表示你的网格，你的元素在哪里

[(-1,-1), (0,-1),(1,-1)...]

依此类推，你基本上在第一行取元素，然后是第二行，然后是第三行。

所以现在，你只需要获取所有可用的数字，也就是说：

[1,1,1,0,0,0,0,0,0]

正如你所说，你只需要 3 个活细胞。

现在我们已经确定了不同字符串的含义，您可以简单地采用执行置换的代码，例如此链接如何在 C 中生成置换？ hich 完全符合您的要求，或者算法库中的任何 ohte 等效代码，例如 std::next_permutation。

于 2012-05-28T23:14:10.033 回答
0

你更喜欢“更智能”的循环还是“更理智”的循环？

//c++ --std=c++11 test.cc

#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <algorithm>
#include <utility>

using std::string;
using std::list;
using std::vector;

const string show[8] = { "(-1,-1)","( 0,-1)","( 1,-1)"
                       , "(-1, 0)",          "( 1, 0)"
                       , "(-1, 1)","( 0, 1)","( 1, 1)"
                       };

auto permutations_of_living_cells =
    [] (int number_of_living_cells) -> list<vector<string>>
    {
    typedef list<vector<string>> (*recT)( void*
                                        , int
                                        , int
                                        , vector<string> &&
                                        , list<vector<string>> &&
                                        );
    recT rec = []( void*r
                 , int n
                 , int i
                 , vector<string> && prefix
                 , list<vector<string>> && l
                 ) -> list<vector<string>>
        {
        if( n==0 )
            {
            l.push_back(std::move(prefix));
            return std::move(l);
            }
        if( i>8-n ) return std::move(l);
        vector<string> psi(prefix);
        psi.push_back(show[i]);
        return  ((recT)r)(r,n  ,i+1,std::move(prefix),
                ((recT)r)(r,n-1,i+1,std::move(psi   ),
                    std::move(l)
                )
                );
        };
    return rec( (void*)rec
              , number_of_living_cells
              , 0
              , vector<string>()
              , list<vector<string>>()
              );
};

template<class T>
std::ostream& operator<<( std::ostream & out,const vector<T> & v )
{
    if( v.empty() ) return out << "[]";
    out << "[ " << *v.begin();
    std::for_each( v.begin()+1, v.end(), [&](T x){out<<", "<<x;} );
    return out << " ]";
}

int main()
{
    for( auto v : permutations_of_living_cells(3) )
        std::cout << v << "\n";
    std::cout << std::flush;
    return 0;
}
于 2012-05-29T02:26:01.153 回答