pythonで順列

会社で新卒の人が振ってきたネタ。ランチ邪魔しやがって。

http://odz.sakura.ne.jp/projecteuler/index.php?Problem%2024

順列とはモノの順番付きの並びのことである. たとえば, 3124は数1, 2, 3, 4の一つの順列である. すべての順列を数の大小でまたは辞書式に並べたものを辞書順と呼ぶ. 0と1と2の順列を辞書順に並べると

012 021 102 120 201 210
になる.

0,1,2,3,4,5,6,7,8,9からなる順列を辞書式に並べたときの100万番目を答えよ

これでパっと思いついたのはリスト内包表記でいい感じにできるんじゃないか。

HaskellかPython。

自分が使いやすい方でpython。

考えているうちに再起使わないと、って思ってきて以下。

#! /usr/bin/env python
# -*- coding: utf-8 -*-
def permutations(L):
  if L == []:
    return [[]]
  else:
    return [[h]+t for i,h in enumerate(L)
      for t   in permutations(L[:i]+L[i+1:])]

r = permutations(range(0, 10))
print r[999999]

レッツゴー

$ python permutations.py 
[2, 7, 8, 3, 9, 1, 5, 4, 6, 0]

これが効率よく処理しているというわけではないけど、答えは合っている、たぶん。

明日からランダムに1日1問解いていくことにした。