Permutationを解決するための動的プログラミング

Question

私は "1"、 "2"、 "3"、 "4"の4桁を持っています。

プログラムの入力は、上記の4桁のみを含む整数です。多くのインプットがあるでしょう。入力の

例：1123、4123、4444

Iは、次の規則に準拠し、所与の入力の順列の数を計算する必要があります

1. どの2つの同様の数字はに隣接してはなりませんお互い。例：1223は許可されず、2123は許可されます。
2. 開始末尾の数字は同じであってはなりません。それらは環状に隣接しているとみなされます。例：2132は使用できません。
3. 入力が4桁の長さの場合、結果の置換も4桁の長さにする必要があります。

この問題を解決するために任意の種類のメモを使用できますか？どのように2次元配列に格納するのですか？ヒントを教えてください！

Answer 1

許可されている契約の数にのみ関心があるため、ほとんどの入力は同じ結果につながります。

• 入力の桁の順序が
• 問題ではない数字の唯一の周波数分布は、同じ答えに、すなわち1123年と1223年のリードが重要です。桁の周波数に応じた入力を分類

は、4桁の入力に対してわずか5別の例につながる：

class  examples 
4   4444, 2222, ... 
3 1  1211, 2232, ... 
2 2  1331, 4422, ... 
2 1 1  3413, 1123, ... 
1 1 1 1 1234, 4231, ... 

あなたはそれぞれのケースのための答えを考え出したら、新たな入力が非常に高速に処理することができます。