ランダムな順列

今日は、１～Nの値を１回使ってできるランダムな順列をつくるアルゴリズムです。

ランダムな順列とは、たとえばNが５なら、［３、２、５、１、４］というような順列をつくることです。

さあ、やってみましょう。

【問題】

１～Nの値を１回使ってできるランダムな順列を作るには？

 【答え】

import random

N = 20

ret = []

ret.append(random.randint(1, N))

for i in range(2, N+1):

  while 1:

    r = random.randint(1, N)

    if r not in ret:

      break

    ret.append(r)

print ret

【実行結果】
[2, 8, 3, 16, 17, 15, 19, 10, 11, 18, 12, 4, 5, 6, 1, 14, 7, 20, 9, 13]

しかし、上記のアルゴリズムだと、繰り返し回数が最悪でNの２乗となってしまうので
効率が悪いらしい。

そこで、繰り返し回数が２Nになる効率のよいアルゴリズムが以下だ。

【答え】

import random

N = 20

ret = range(1, N+1)

for i in range(N-1, 0, -1):

  j = random.randint(0, i)

  ret[i], ret[j] = ret[j], ret[i]

print ret

【実行結果】
[2, 8, 3, 16, 17, 15, 19, 10, 11, 18, 12, 4, 5, 6, 1, 14, 7, 20, 9, 13]

確かに、実行スピードの効率はよさそうだけど、メモリは下のほうが食うかな。