content: {- 
   - Next lexicographical permutation algorithm
   - by Project Nayuki, 2016. Public domain.
   - https://www.nayuki.io/page/next-lexicographical-permutation-algorithm
   -}
  
  module NextPerm (nextPermutation) where
  
  
  {- 
   - Computes the next lexicographical permutation of the specified finite list of numbers.
   - Returns Nothing if the argument is already the highest permutation.
   -}
  nextPermutation :: Ord a => [a] -> Maybe [a]
  nextPermutation xs =
  	let
  		len = length xs
  		revSuffix = findPrefix (reverse xs)  -- Reverse of longest non-increasing suffix
  		suffixLen = length revSuffix
  		prefixMinusPivot = take (len - suffixLen - 1) xs
  		pivot = xs !! (len - suffixLen - 1)
  		suffixHead = takeWhile (<= pivot) revSuffix
  		newPivot : suffixTail = drop (length suffixHead) revSuffix
  		newSuffix = suffixHead ++ (pivot : suffixTail)
  	in
  		if suffixLen == len then Nothing else Just (prefixMinusPivot ++ (newPivot : newSuffix))
  	where
  		findPrefix [] = []
  		findPrefix (x:xs) = x : (if xs /= [] && x <= (head xs) then (findPrefix xs) else [])
  
  -- Example: nextPermutation [0, 1, 0] -> Just [1, 0, 0]
  