Zope - Plone - pLatex - Tex - Wiki - qmail

異なるものの順列や、同じものを含む順列を生成させたいときは、再帰呼び出しのできるプログラミング言語であれば、比較的簡単にプログラミングできます。

高校生のころ、クラスの友人が BASIC で順列を生成させたり、ハノイの塔を解いたりしていましたが、ソースは、For Next ループの嵐で大変だったようです。

一方、Haskell は数学的な言語です。まさに関数型言語で、紙に直接関数を書いていくのに近い形で、関数を定義できます。というわけで、同じものを含む順列を生成させるプログラムを作ってみました。樹形図を描く要領でプログラミングしていきます。

ソースは次の通りです。関数のネーミングは適当です。英語が苦手なので、ご勘弁を。

pGen :: String -> [String]
pGen s
 | length s == 1 = [s]
 | otherwise     = 
       concat [addOneChar c (pGen (dropOnlyOneChar c s)) | c <- mSet s ]

addOneChar :: Char -> [String] -> [String]
addOneChar c ls = [c : s | s <- ls]

isElement :: Char -> String -> Bool
isElement c s = length [ch | ch <- s,ch == c] /= 0

dropOnlyOneChar :: Char -> String -> String
dropOnlyOneChar c s
 | c == (head s) = tail s
 | otherwise     = (head s) : (dropOnlyOneChar c (tail s))

mSet :: String -> String
mSet s
 | (length s) <= 1 = s
 | isElement (head s) (tail s) =
           (head s):(mSet (dropOneChar (head s) (tail s)))
 | otherwise = (head s):(mSet (tail s))

dropOneChar :: Char -> String -> String
dropOneChar c s = [ ch | ch<-s, ch /= c]

haskell を起動して、計算してみます。

*Main> pGen "abc"
["abc","acb","bac","bca","cab","cba"]
*Main> pGen "aabbc"
["aabbc","aabcb","aacbb","ababc","abacb","abbac","abbca","abcab","abcba","acabb"
,"acbab","acbba","baabc","baacb","babac","babca","bacab","bacba","bbaac","bbaca"
,"bbcaa","bcaab","bcaba","bcbaa","caabb","cabab","cabba","cbaab","cbaba","cbbaa"
]

樹形図を使って書いていくように、順列が生成されていることがわかります。

PermuTation