Нахождение четных перестановок с использованием Haskell

Question

Я попытался выяснить, как найти четные перестановки из множества {permutations [1..n]}. Я задал этот вопрос раньше на другом форуме, и получил ответ, который работал, а именно код:

Import Data.List

-- number of inversions in a permutation
inversions as = sum $ map go (tails as)
where go [] = 0
go (x:xs) = length $ filter (<x) xs

evenPerm as = even (inversions as)

alternating n = [ p | p <- permutations [1..n], evenPerm p ]

Я понимаю последнюю строку в коде: alternating n =[p | p <- permutations [1..n], evenPerm p], Это p из набора {permutations [1..n]} такие, что они даже перестановки. Функция evenPerm как я думаю, я тоже понимаю. Это просто четные элементы множества {inversion as}, То, что я действительно не понимаю, как это работает, это инверсия как функция. Наивно, как я мог бы представить, что все работает, - это взять элемент из набора {permutations [1..n]} [1..n] т.е. (1,2,3,..,n) и сравнить все остальные элементы в установите для этого и посчитайте, сколько ходов вам нужно сделать, чтобы получить его в этой форме, но как вы поступите с этим в Haskell?

Answer 1

Чтобы взглянуть с высоты птичьего полета, нам нужно посчитать, сколько свопов нам понадобится, чтобы отсортировать список по месту. (Эквивалентно, на языке теории групп, чтобы разложить перестановку на транспонирования.) Какой алгоритм сортировки мы используем для подсчета перестановок, не имеет значения для корректности: четная перестановка будет генерировать четное число перестановок, а нечетная перестановка - нечетное число свопов независимо от того, как мы сортируем.

Давайте сначала посмотрим на:

go [] = 0
go (x:xs) = length $ filter (<x) xs

Отступ в этом образце сбивает с толку, но go является вложенной локальной функцией inversions, Похоже, внутри where пункт. go Функция подсчитывает количество элементов в списке, которые необходимо переместить до первого элемента в списке, то есть элементов, меньших, чем заголовок списка. Это происходит путем фильтрации хвоста и определения его длины. Пустой список не имеет заголовка, поэтому существует другой шаблон, соответствующий ему для полноты. (В противном случае компилятор будет жаловаться, что некоторые входные данные не соответствуют ни одному шаблону.)

inversions as = sum $ map go (tails as)

tails функция от Data.List библиотека, которую мы импортировали. Он генерирует список более коротких и коротких конечных сегментов: tails [1,2,3] = [[1,2,3] [2,3], [3]], Затем мы карту go на каждый последний сегмент в списке, давая нам список счетчиков инверсии для каждого последнего сегмента. Наконец, мы подводим итоги.

Вы часто будете видеть такие вещи, написанные как набор функций: inversions = sum . map go . tails, Это только применяет каждую функцию справа налево: tails, затем map go на результат, то sum на результате этого.

Например.

list == [4,3,2,1]
tails list == [[4,3,2,1], [3,2,1], [2,1], [1]]
map go (tails list) == [3,2,1,0]
sum $ map go (tails list) == 6

Это подсчитывает количество обменов для пузырьковой сортировки. Мы могли бы теоретически выполнить следующие перестановки для сортировки списка:

[4,3,2,1] -- 0 swaps needed to sort [1]
[4,3,1,2] -- 1 swap to sort final sequence [2,1]
[4,1,3,2] -- Which equals go [2,1]
[4,1,2,3] -- 2 additional swaps to sort [3,2,1]
[1,4,2,3] -- Which equals go [3,2,1]
[1,2,4,3]
[1,2,3,4] -- 3 additional swaps to sort [4,3,2,1]
          -- Which equals go [4,3,2,1]

Это далеко не минимальное количество перестановок, но нам просто нужно немного подсчитать для какого-то алгоритма сортировки, и этот прост.

Следующий шаг

evenPerm as = even (inversions as)

Это предикат, который просто говорит нам, был ли результат вычисления, на которое мы только что смотрели, четным или нечетным. Это также можно было бы определить как even . inversions, или же even . sum . map go . tails,

alternating n = [ p | p <- permutations [1..n], evenPerm p ]

Это понимание списка. Вызывает другую функцию из Data.List, permutations, чтобы сформировать список всех перестановок. Затем он добавляет перестановку p в наш список вывода, если и только если evenPerm p правда.

Это также могло быть написано как evenPerms = filter evenPerm . permutations, который короче и работает с большим количеством типов, с alternating n = evenPerms [1..n], То есть, учитывая входной список, генерируйте его перестановки и применяйте к ним фильтр. (Это версия alternating работает только на числах, потому что он использует [1..n], но алгоритм может работать так же хорошо на чем угодно с оператором меньше чем.)

Очищенная версия

import Data.List

{- In the type signatures below, capitalized type names are specific types.
 - Lowercase type parameters are generic.  Ord, to the left of the => sign,
 - is the type class of all types with an ordering relation.  So, the argu-
 - ment is a list of some type a that can be ordered, and the return value
 - is a Bool, True or False.
 -}
isEvenPerm :: Ord a => [a] -> Bool
isEvenPerm = even . sum . map go . tails
  where go []     = 0
        go (x:xs) = length . filter (<x) $ xs

evenPerms :: Ord a => [a] -> [[a]]
evenPerms = filter isEvenPerm . permutations

{- This only makes sense for positive whole numbers. -}
alternating :: Integral a => a -> [[a]]
alternating n | n >= 1    = evenPerms [1..n]
              | otherwise = error "Argument must be positive."

Ты можешь попробовать evenPerms "abcd" а также alternating 4,

Answer 2

Я знаю, что ОП хочет код "голыми руками", но вот способ с combinat пакет (я большой поклонник этого пакета), который может быть полезным для будущих читателей. Поскольку мне потребовалось определенное время, чтобы достичь этого, я думаю, что стоит поделиться.

import           Data.List hiding (permutations) -- just in case
import           Math.Combinat.Permutations

foo :: [[Double]]
foo =
  [[ permuteList p [phi/2, 1/2, 1/2/phi, 0]  | p <- permutations4, isEvenPermutation p] ++
  [ permuteList p [phi/2, 1/2, -1/2/phi, 0]  |  p <- permutations4, isEvenPermutation p] ++
  [ permuteList p [phi/2, -1/2, 1/2/phi, 0]  |  p <- permutations4, isEvenPermutation p] ++
  [ permuteList p [-phi/2, -1/2, 1/2/phi, 0]  |  p <- permutations4, isEvenPermutation p] ++
  [ permuteList p [-phi/2, -1/2, 1/2/phi, 0]  |  p <- permutations4, isEvenPermutation p] ++
  [ permuteList p [-phi/2, -1/2, -1/2/phi, 0]  |  p <- permutations4, isEvenPermutation p] ++
  [ permuteList p [-phi/2, 1/2, -1/2/phi, 0]  |  p <- permutations4, isEvenPermutation p] ++
  [ permuteList p [phi/2, 1/2, -1/2/phi, 0]  |  p <- permutations4, isEvenPermutation p]]
  where
    permutations4 = permutations 4
    phi = (1 + sqrt 5) / 2