2

順列を生成するための Steinhaus-Johnson-Trotter アルゴリズムを実装しようとしています。私のコードは以下の通りです：

permutations :: [a] -> [[a]]
permutations [] = []
permutations (x:[]) = [[x]]
permutations xs = [ys ++ [xs !! i] | i <- [len,len-1..0], ys <- permutations (delete i xs)]
  where len = (length xs)
        delete i xs = take i xs ++ drop (succ i) xs

これはPython コードからの直訳です:

def perms(A):
    if len(A)==1:
        yield A
    for i in xrange(len(A)-1,-1,-1):
        for B in perms(A[:i]+A[i+1:]):
            yield B+A[i:i+1]

Python コードは機能しますが、Haskell コードは無限再帰に入ります。permutations (delete i xs)リスト内包表記は、フローを基本ケースに近づける必要があります。無限再帰はなぜ起こるのか?

編集: @augustss言います:

リスト上の関数に複数の基本ケースがある場合は常に注意してください。

だから私はベースケースを

permutations [] = []
permutations (x:[]) = [[x]]

よりシンプルに

permutations [] = [[]]
4

2 に答える 2

4

あなたのループは同じではありません。

i <- [len,len-1..0]

対

for i in xrange(len(A)-1,-1,-1):

最初のケースでiは、長さから 1 を引いたものではなく、長さにバインドしています。結果は をdelete i xs返すxsので、無限再帰が得られます。

また、いくつかの補足事項があります。

最初!!は線形時間です。!!、delete、および入力に対する反復を 1 つのリスト トラバーサルに結合するヘルパー関数を作成する方がはるかに優れています。のようなものselect :: [a] -> [(a, [a])]。それを効率的に行うことができます。

第二に、++線形時間でもあります。これを使用して単一の要素を既存のリストに追加すると、処理が遅くなります。特定の順列ではなく、すべての順列を生成することが目標である場合は、(xs !! i) : ys返す式として を使用する必要があります。(最初のポイントに対応して行われた変更に合わせて適切に変更されています。)

于 2013-06-06T16:06:49.467 に答える
1

select

@Carlの回答に基づいて、select :: [a] -> [(a, [a])]関数を実装しました。タプル(a, [a])の最初の部分はリストの要素であり、タプルの2番目の部分はその要素を除くリストのすべての要素です。

select :: [a] -> [(a, [a])]
select [] = []
select (x:xs) = select' x [] xs
  where
    select' x left [] = [(x, left)]
    select' x left right@(r:rs) = (x, left++right) : select' r (x:left) rs

selectしかし、Haskell Libraries メーリング リストで、さらに簡単な実装を見つけました。

select :: [a] -> [(a,[a])]
select [] = []
select (x:xs) = (x,xs) : [(y,x:ys) | (y,ys) <- select xs]

これら 3 つは同等であることに注意してください (secondは の関数ですControl.Arrow)。

[(y,x:ys) | (y,ys) <- select xs]
map (\(y,ys) -> (y,x:ys)) (select2 xs)
map (second (x:)) (select2 xs)

使用方法の例を次に示しますselect。

select [1,2,3] -- [(1,[2,3]),(2,[1,3]),(3,[2,1])]

を実装する前に、Hayooselectで型を持つ関数を見つけようとしました。さまざまなライブラリにいくつかの実装があります。[a] -> [(a, [a])]

permutations

問題は、すべての順列selectを生成するのに十分ではないということです。タイプが である を使用して、各タプルの両方の部分を cons できますが、すべてではなく一部の順列しか得られません。uncurry (:)(a, [a]) -> [a]

map (uncurry (:)) (select [1,2,3]) -- [[1,2,3],[2,1,3],[3,2,1]]

select [1,2,3]リストを作成する理由は明らかですが[(1,[2,3]),(2,[1,3]),(3,[2,1])]、各タプルの 2 番目の部分でもあるサブリストを並べ替える必要があります。言い換えると、 がある場合は(1, [2,3])、 も追加する必要があり(1, [3,2])ます。

リストのすべての順列を見つけるための完全なコードは次のとおりです。

select :: [a] -> [(a,[a])]
select [] = []
select (x:xs) = (x,xs) : map (\(y,ys) -> (y,x:ys)) (select xs)

permutations :: [a] -> [[a]]
permutations [] = [[]]
permutations xs = [cons s2 | s <- select2 xs, s2 <- subpermutations s]
  where cons :: (a, [a]) -> [a]
        cons = uncurry (:)
        subpermutations :: (a, [a]) -> [(a, [a])]
        subpermutations (x,xs) = map (\e -> (x, e)) $ permutations xs

関数の順列の順序は とは異なることに注意してくださいData.List.permutations。私たちの関数には辞書式の順序がありますが、そうでData.List.permutationsはありません:

permutations [1,2,3]           -- [[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]]
Data.List.permutations [1,2,3] -- [[1,2,3],[2,1,3],[3,2,1],[2,3,1],[3,1,2],[1,3,2]]

permutations最後に、関数をさらに単純化すると、 Rosetta Codeにある実装が得られます。

select :: [a] -> [(a,[a])]
select [] = []
select (x:xs) = (x,xs) : map (\(y,ys) -> (y,x:ys)) (select xs)

permutations :: [a] -> [[a]]
permutations [] = [[]]
permutations xs = [ y:zs | (y,ys) <- select xs, zs <- permutations ys]

また、挿入ベースのアプローチを使用する Rosetta Code の実装には、 と同じ (非辞書式) 順序があることに注意してくださいData.List.permutations。

ノート

FWIWscc :: [(a, [a])] -> [[a]] 、パッケージの関数があり、グラフの強く接続されたコンポーネントuhc-utilを見つけます。タプルの最初の部分は頂点で、2 番目の部分はすべての頂点であり、頂点からのエッジがそこに向かいます。IOW、グラフになります。1 --> 2 --> 3[(1, [2]), (2, [3])]

scc [(1,[2,3,4]),(2,[1,3,4]),(3,[2,1,4]),(4,[3,2,1])] -- [[3,4], [1,2]]
于 2015-08-23T21:32:45.880 に答える