競技プログラミングのソート比較に関する質問

Question

ソートアルゴリズムに関する質問です。
競技プログラミングの問題(Python)なのですが、
> 数字の書かれた玉（数字は適当で重複もアリ）があり、左から一列に並べます。このとき任意の玉の数字より大きい数字の玉が左に2個以上こない並び方が何通りあるか求めよ。

> [入力形式]
> 玉の数
> 数字1,数字2,…

> [解答例]
> 3
> 2 1 3
> のとき
> ４通り

> 3
> 1 2 2
> のとき
> 4通り
これの解き方が分かりません。
実行時間とメモリの関係上、forを何重にもする方法は不適切かと思われます。
どなたか、Pythonのコードで解法を示していただけると幸いです。

Answer

まずは愚直な方法で解いてみて、結果から法則を読み取ってみてはいかがでしょうか。

すべての順列から条件に合うものを数えると(ついでに該当の順列を表示)、以下のようになります。
```python
import itertools

a = [1,2,3,4]
count = 0
for p in itertools.permutations(a):
    if all(sum(p[j] > p[i] for j in range(i)) <= 1 for i in range(2, len(p))):
        print(p)
        count += 1

print(count)
```

こちらの実行結果は以下のようになります。
```text
(1, 2, 3, 4)
(1, 2, 4, 3)
(1, 3, 2, 4)
(1, 4, 2, 3)
(2, 1, 3, 4)
(2, 1, 4, 3)
(3, 1, 2, 4)
(4, 1, 2, 3)
8
```

この並びを見て、法則を見いだせないでしょうか。
最大の数の位置が同じものを並べると、より分かりやすいかもしれません。
```text
(1, 2, 3, 4)
(2, 1, 3, 4)
(1, 3, 2, 4)
(3, 1, 2, 4)

(1, 2, 4, 3)
(2, 1, 4, 3)

(1, 4, 2, 3)

(4, 1, 2, 3)
```

Answer

大きい数字の玉から置いていくと計算しやすいですよ