順列全列挙 (paizaランク B 相当)

巡回セールスマン問題とは、都市の集合と各都市間の距離が与えられ、全都市をちょうど1回ずつ訪れたのち出発した都市に戻ってくるような経路 (巡回路) のうち最も短いものを求める問題です。

この問題に対する直感的な解法として、巡回路を全列挙するというものがあります。つまり、都市の順列を全通り試して、それぞれについて巡回路長を計算し、巡回路長が最小のものを答えとする解法です。

ここでは、この解法を実装する前準備として、順列を全列挙してみましょう。整数 n が与えられるので、{1, 2, ..., n} の順列を全て求め、出力してください。順列は 1 行に 1 つ、半角スペース区切りで出力するものとします。順列の順番は問いません。

出力に同じ順列が複数含まれている場合や、順列でないものが含まれている場合、余計な空白や空行が含まれている場合などはすべて不正解になります。