1つの最適化問題を研究して、オプションの直接列挙で構成の対称性の問題に遭遇しました。 8人の女王問題のいくつかの解決策で同様の問題が起こります 。 長方形グリッドの中心対称性を調べると、「シフター」番号を使用して対称構成を決定および確認するための対称性について少し
中心対称または点を中心とする対称性は、点Xを点Xにマップする空間の変換です。これにより、対称中心はセグメントXXの中心になります。 図形の各点について、点Aに関して対称な点もこの図形に属する場合、図形は点Aに関して対称と呼ばれます。
セルで構成されるグリッドの中心対称性について話している場合、ポイントについてではなく、グリッドのセルについて話します。 たとえば、チェス盤の中心対称の変換後、セルA1がH8を置き換え、A2がH7を置き換え、B1がG8を置き換えます。
この記事では、長方形のグリッドを使用します。 長方形のように、このようなグリッドには対称軸が2つと中心が1つありますが、中心の対称性のみに焦点を当てています。
問題の本質
3 x 6セルのグリッドがあります。 また、14個のコンポーネントのリストも使用できます。これらのコンポーネントはいずれも任意のセルに配置でき、繰り返し可能です。 繰り返しのあるこのようなグリッドの塗りつぶしオプションの数は14 18です。すでにテストされたものと中心的に対称な塗りつぶしオプションを破棄することにより、それらを半分にすることは当然良いことです。 出力を簡単にするために、コンポーネントは0から13までの数字とします。 18個のコンポーネントのリストがitertoolsパッケージのproduct関数によって生成されます （正確には、この関数は反復タプルを返します。これは走行距離計のように、各反復で右側の要素を変更します）。 このリストには、列がグリッドで表示されます。
ゼロ、1番目、2番目、および178番目のグリッド構成の例 
目的：すでに検証されたオプションと中心的に対称なグリッド塗りつぶしオプションを除外します。
実装
セルには、左上隅から0〜17までの列に番号を付けます。各構成について、中心に対して対称な番号を見つけようとします。 構成の番号付けは、通常どおり、最初から。
構成0 （ゼロを持つすべてのセル）は、明らかにそれ自体に対して対称です：0-> 0。
構成1.セル17は1を取得し、残りはゼロを取得します 。 それに対称的なのは、セル0に「1」があり、残りがゼロである構成です。 セル17は、最初の14回の繰り返しで14個の値（0〜13）を渡します。 セル16も14を超えていますが、各構成には14のセル17の繰り返しがあります。 14 2など したがって、セル0は14 17回の繰り返しで1をダイヤルします。
構成2.セル番号17は2を取得し、残りはゼロを取得します。 構成2⋅1417はそれと対称になり、セル0のコストは2、残りのゼロになります。
構成3- >構成3-14 14
構成4- >構成4-14 14など 13->13⋅1417まで。
この論理に従って、バリアントの数を、最初の対称なもの、1 the14 17として、ゼロに対称なもの、0⋅1417として書き留める価値があります。
互いに対称的な構成番号のリストが既にあります。
- 0および0⋅1417
- 1および1⋅1417
- 2および2⋅1417
など 13日まで
構成14. 1は最後から2番目のセルにあり、残りはゼロです。 それに対称なのは1× 14 16です。
構成15.最後の2つのセルの単位、残りのゼロ。 それに対称的で、最初の2つのセルに1がある場合、残りはゼロです。 1は、反復14 17でセル番号0になり、14 16の後、セル番号1にも1が表示されます。したがって、希望の構成には14 16 + 14 17の番号が付けられます。
構成16.セル番号16の要素「A」、セル番号17の「B」 それに対称、明らかに14 16 +2⋅1417。
...
構成 27->1⋅1416 +13⋅1417。
設定 28-> 2-14 14 。
構成 29->2⋅1416 + 14 17 。
この話は、反復195まで続きます。反復195は対称的な13⋅1416 +13⋅1417です。 繰り返し196では、セル番号15に1が入れられ、残りは空です。 反復14はそれに対称です。
繰り返し197では、ユニットもセル番号17に配置されます。したがって、ユニットは対称です-14 15 + 14 17など。
グリッド構成の対称性の一般的な法則は次のとおりです。
それから、左の式は私に馴染みがあるように見えました。 これは、任意の基数を持つ数値システムから数値を10進数に変換するための式です。 それに応じて
右側に番号が左側から逆の順序で書き込まれていることに気付くのは簡単です-左側で番号を右から左に、次に左に「書き込む」場合、同じ番号で左から右に。 簡単に言えば、右側の数字は左側の数字の「反転側」であり、どちらも14を基数とする長さ18の数字体系で書かれています。
基準と検証アルゴリズム
構成番号がセルの数で長く、要素数に等しい基数で自身の「反転」番号よりも小さい番号システムに記録されている場合、対称構成はまだ検出されていません。 それら（数）が等しい場合、回文は1回だけ発生するため、検証の対象となります。
検証アルゴリズム自体は次のとおりです。
- 構成番号を、基数が要素数に等しい数値システムに変換します
- 長さ18の「変化」という数字を書き留めます
- 「変更」が構成番号よりも大きい場合、この構成のシミュレーションと対称的な構成はまだ実行されていません。 そうでない場合、構成は対称であり、対称であるため、スキップします。
またはコードとして
def validate(number, radix, length): fingers = '0123456789abcdefghijklmnopqrstuvwxyz' n = number # radix turn = '' while n > 0: turn += fingers[n % radix] n = n // radix # turn += '0' * (length - len(turn)) return number <= int(turn, radix)
おわりに
明らかに、このアルゴリズムは、2次元グリッドの中心対称性を決定するだけでなく、任意の次元のグリッドを決定するためにも適用できます。そのような構成はリストに縮小したり、グリッドを1行ごとにリストで埋めることができるためです。
アルゴリズム自体は非常に重いため、実際の適用可能性の問題が生じます。 しかし、各構成をチェックするのにさらに多くのコンピューティングリソースが必要な場合は、おそらくそれを使用する価値があります。