読者です 読者をやめる 読者になる 読者になる

DELAEMON BLOG

Live as if you were to die tomorrow. Learn as if you were to live forever.

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万番目を答えよ


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

HaskellPython

自分が使いやすい方で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問解いていくことにした。