3

ブール値の 3 x 3 グリッドがあり、正確に 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

ウィキペディアからこの手順を試してください。

次のアルゴリズムは、与えられた順列の後に辞書編集的に次の順列を生成します。指定された順列をその場で変更します。

  1. a[k] < a[k + 1] となる最大のインデックス k を見つけます。そのようなインデックスが存在しない場合、順列は最後の順列です。
  2. a[k] < a[l] となる最大のインデックス l を見つけます。k + 1 はそのようなインデックスであるため、l は明確に定義され、k < l を満たします。
  3. a[k] を a[l] と交換します。
  4. a[k + 1] から最後の要素 a[n] までの順序を逆にします。
于 2012-05-28T23:04:02.900 に答える
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 に答える