Здравствуйте, BulatZiganshin, Вы писали:
BZ>Здравствуйте, hexamino, Вы писали:
H>>Надо получить все беспорядки [0..n], то есть все перестановки этого списка где ни один элемент не стоит на своем исходном месте.
H>>H>>disorders n = filter (and . (zipWith (/=) [0..n])) (permutations [0..n])
H>>
BZ>filter (/=[0..n]) (permutations [0..n])
Не, тут пролезают неполные беспорядки. Сравни
>let disorders' n = filter (and . (zipWith (/=) [0..n])) (permutations [0..n])
>let disorders'' n = filter (/= [0..n]) (permutations [0..n])
> disorders' 2
[[1,2,0],[2,0,1]]
> disorders'' 2
[[1,0,2],[2,1,0],[1,2,0],[2,0,1],[0,2,1]]
H>>А можно ли не фильтровать, а сразу строить только нужные перестановки?
BZ>disorders n = inserts n (disorders (n-1)) ++ dropLast (inserts n [0..n-1])
Типы слагаемых в ++ разные
BZ>-- вставляет x во все возможные позиции списка xs
BZ>inserts x [] = [х]]
BZ>inserts x xs = (x:xs) : map (head xs (inserts x (tail xs) )
BZ>dropLast = reverse.tail.reverse