私は、ある与えられたアルゴリズムを探しています数{0,1,2,4,5 ...}と各要素の相対位置に関する一連の条件のうちの1つは、有効な順列が存在するかどうかをチェックする。条件は常に "元の配列の位置iの要素は、位置jまたはzの要素の次の（隣接する）"でなければなりません。
置換の最後の要素と最初の要素は隣接しているとみなされます。
ここでは簡単な例を示します：
数字を{0,1,2,3}とする。
a0はa1の次に、a0はa2の次に、a3はa1の次になければなりません
この例に対する有効な解決策は、{0,1,3,2}です。
このソリューションの回転/対称性も有効な解決策であることに注意してください。私はそのような解決策が存在することを証明する必要があります。
同じセットを使用する別の例：
a0はa1の次に、a0はa3の次に、a0はa2の次になければなりません。
この例では、数字は2つの数字にのみ隣接できるため、有効な解決策はありません。
今私が思いつくことができる唯一のアイデアは何らかのバックトラックを使うことでしょう。
解決策が存在する場合、これは静かに収束するはずです速い。解決策が存在しない場合は、すべての可能な順列をチェックすることを避けるための方法は想像できません。 すでに述べたように、回転や対称性は、与えられた順列の結果に影響を及ぼさないので、可能性の数を減らすことが可能でなければなりません。
回答：
回答№1は1これをグラフ問題として定式化する。 お互いの隣にいる必要があるすべての数字のペアを接続します。あなたは接続されたコンポーネントの束で終わるつもりです。各コンポーネントには多くの順列（ミニ順列と呼ぶことができます）があり、コンポーネントの順列を持つことができます。
グラフを作成するときは、各コンポーネントが一連のルールに従っていることを確認します。サイクルなし、2つ以上の頂点を持つ頂点なしなど
回答№2の場合は1
基本的に、作成できるかどうかを知りたい数字の連鎖それぞれの番号をチェーンに入れ、番号と最大2つの隣人を追跡します。ルールを使用してチェーンを結合します。 2つのチェーンに参加すると、2つの緩い端（隣人）があるチェーンで終わるでしょう。ゆるい端を使い果たすことなくすべてのルールをクリアすることができれば、それは機能します。
回答№3の場合は0
私は少し修正してグラフソリューションを実装しました。
ノードに隣接ノードが多すぎる場合、アルゴリズム1つのエッジをドロップし、グラフを再度チェックします。 私はその後、ロールバックし、次のエッジをドロップすることが可能かどうかを確認するバックトラックを使用して... このメソッドは、私が書いたブルートフォースメソッドと同じ結果を返します。
複雑さの面では、この解決策は私は20以上の数字（ブルートフォースの場合はわずか8）で実行することはできますが、ブルートフォースよりも優れています。このグラフは実際に有効なパーミュテーションのサブセットを生成することができます最悪の場合は、エッジの集合上のいくつかのコンポジションを見つけることと同じです。結局はバックトラックしています。
ローテーションが影響を及ぼさないことを考えれば順列の妥当性、私は最初の位置にa0を固定することを考えていました（これは、a0が最初の位置にくるまで有効な順列を回転するだけで実現できます）。そこから解を構築しようとします。
DPを使用すると、指数関数的な複雑さよりも優れたものが得られるかもしれません。しかし、私はまだどこで始めるべきか分からないと言わなければなりません:)