ランダムな順列

乱数を使ってランダムな順列を得る。
その前にpythonで擬似乱数を得る方法について。

>>> random.randint(1, 10)  # Integer from 1 to 10, endpoints included
7

はじめに効率の悪い方法。
アルゴリズムは、
(1)1~Nの乱数を１つ得る。これを順列の１番目のデータとする。
(2)以下をN-1回繰り返す
(a)1~Nの乱数をひとつ得る。
(b) (a)で求めた乱数が今まで作ってきた順列の中に入っていれば(a)に戻る

#!usr/bin/env/ python
# -*- coding: utf-8 -*-

#randomperm.py

import sys
import random

N = raw_input("random permutation? : ")
perms=[]
ra = random.randint(1,int(N))
perms = perms.append(str(ra))
print perms
for x in range(int(N)):
    ra = random.randint(1,int(N))
    print ra
    for perm in perms:
        if ra == perm:
            print "break"
            break
        else:
            perms =perms.append(str(ra))
            print "else"
perms = perms.append(str(ra))
print perms

保留。

次に、効率のよい別の方法。
a=[1,…,N]の配列を用意する
(1)1~N-1までの乱数Rに対してa[N]⇔a[R]の交換を行う。
(2)以下、N→N-1としてN=1まで繰り返す。

（例）
N=5のとき　a=[1 2 3 4 5]

乱数生成(N-1 = 4までの数) 3とする
1 2 5 4 3
乱数生成(N-1 = 3までの数)　2とする
1 4 5 2 3
乱数生成(N-1 = 2までの数)　2とする
1 5 4 2 3
乱数生成(N-1 = 1までの数)　1とする
5 1 4 2 3
完了
この繰り返しは2N＝10回となる。

#!usr/bin/env/ python
# -*- coding: utf-8 -*-

#randomperm_new.py

import sys
import random

N = raw_input("random permutation? : ")
perms =range(1,int(N)+1)
print perms
i=int(N)-1
for x in range(len(perms)-1):
    ra = random.randint(1,i)
    perms[i],perms[ra] = perms[ra],perms[i]
    i-=1
print perms

リスト要素の交換は以下のようにする。

a = [10, 20]
a[0], a[1] = a[1], a[0]
print a

a=[20,10]