トップページ -> AOJの解答例 -> ITP2_5の解答例

ITP2_5の解答例(Python)

並び替えと順列に関する問題です．

1. ITP2_5_A: Sorting Pairs

与えられたxy座標を昇順に並べ替える問題です．


# ITP2_5_A
n = int(input())
N = []

for _ in range(n):
    N.append(list(map(int,input().split(" "))))

N.sort()
for x in N:
    print(*x)

2. ITP2_5_B: Sorting Tuples

こちらも入力を昇順に並べ替える問題です．入力を適切な方に直してから並び替えを行います．


# ITP2_5_B
n = int(input())
N = []

for _ in range(n):
    item = input().split(" ")
    # 型を直さず 文字列のまま処理すると 30 > 110 のようなことになってしまう
    item[0] = int(item[0])
    item[1] = int(item[1])
    item[3] = int(item[3])
    
    N.append(item)

# sort で先頭からソートできる
N.sort()
for x in N:
    print(*x)

3. ITP2_5_C: Permutation

辞書順に並べた時の前の数字と次の数字を探す問題です．末尾の桁から順に切り出した数 n に対して「nの1桁目(n=123なら1)より大きい最小の数字を1桁目それ以外の数字を昇順に並べた数をそれ以降の桁」を作ることができれば次の数字が見つかります．例えば，n=13475という数字に対してこの操作を行うと，1桁目の1より大きい最小の数は3であるため3を1桁目残りの1,4,7,5を昇順に並べた数 1457を後ろに付けて31457になります．小さい数字についても同様に元の1桁目より小さい最大の数字を先頭，残りを降順にしたものを考えています．


# ITP2_5_C
n = int(input())
N = list(map(int,input().split(" ")))

pre_num = False
next_num = False

# 数字を1つしか含んでいなければ順列は1通り
if len(set(N)) == 1:
    print(*N)
else:
    for i in range(2,len(N)+1):
        origin = N[len(N)-i]
        # 元の数字より大きい最小の数字を見つける
        if not next_num:
            for j in range(origin+1,10):
                if N[len(N)-i:].count(j):
                    # 大きい最小の数字をスライスしたリストの先頭に持ってきて後ろを昇順にすれば次の数字になる
                    tail = N[len(N)-i:]
                    tail.remove(j)
                    next_num = N[:len(N)-i] + [j] + sorted(tail)
                    break
                    
        # 元の数字より小さい最大の数字を見つける
        if not pre_num:
            for j in range(1,origin):
                if N[len(N)-i:].count(origin-j):
                    # 小さい最大の数字をスライスしたリストの先頭に持ってきて後ろを降順にすれば次の数字になる
                    tail = N[len(N)-i:]
                    tail.remove(origin-j)
                    pre_num = N[:len(N)-i] + [origin-j] + sorted(tail,reverse=True)
                    break

        # 小さいほうも大きいほうも見つかっていれば終了
        if pre_num and next_num:
            break
    
    # 存在する場合は出力する
    if pre_num:
        print(*pre_num)

    print(*N)

    if next_num:
        print(*next_num)

4. ITP2_5_D: Permutation Enumeration

1からnまでの順列を全て挙げる問題です．再帰関数で順列を定義しました．


# ITP2_5_D

# 1桁なら一意
# 2桁は入れ替え
# 3桁は先頭を決めて2桁の入れ替え
# 4桁は先頭を決めて3桁の順列
# ...
    
# 再帰関数
def permutation(n,A):
    if n == 1:
        return [A]
    elif n == 2:
        swaped_list = A[:]
        swaped_list[-1] = A[-2]
        swaped_list[-2] = A[-1]
        if swaped_list < A:
            return [swaped_list,A]
        else:
            return [A,swaped_list]
    # 先頭を決めて n-1 の順列を考える
    else:
        result = []
        for i in range(1,n+1):
            tmp = A[i-1]
            B = A[:]
            B.remove(tmp)
            swaped_list = permutation(n-1,B)
            for x in swaped_list:
                result.append([tmp]+x)
            
        return result
        
n = int(input())
result = permutation(n,[(i+1) for i in range(n)])
for x in result:
    print(*x)

わざわざ自分で順列を定義しなくてもitertoolsのpermutationsを使って簡単に順列を求めることもできます．


from itertools import permutations

n = int(input())

# 1からnまでの整数の順列を生成
permutation_list = list(permutations(range(1,n+1)))

# 順列を表示
for perm in permutation_list:
    print(*perm)

<- 前へ戻る【目次に戻る】次へ進む ->