Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

競プロでよく出る順列全探索をpythonで実装してみる

初めに

アルゴリズムの学習中をしていて順列全探索を覚えたのでアウトプットとして記事を書いています。
まだまだ浅学の身ですので、誤りがあればどんどんご指摘ください。

順列全探索とは

ある異なる要素を含むリストについてその要素を並べ替えたリストを全て列挙する全探索の手法です。
例えば、[1,2,3]を順列全探索すると[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]の6通りの順列を得ます。

実装例

permutations.rb
from itertools import permutations
list=[1,2,3]
per=permutations(list,2)
for i in per:
    print(i)

出力

ans.py
(1, 2)
(1, 3)
(2, 1)
(2, 3)
(3, 1)
(3, 2)

ポイント

・ライブラリのitertools.permutationsを用いて順列を生成する。
・permutationsはイテレータであるため、そのままでは出力できない。
例えば、上記のコードでprint(per)としても出力されない
・permutationsの第二引数に数字を指定することでその個数だけ含まれた順列を生成できる

競プロ例題

https://atcoder.jp/contests/abc150/tasks/abc150_c

順列全探索が理解できる初心者向けの良問です。
ここでindex関数の使い方もおぼえてしまいましょう

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away