Hacktoberfest 2026: los issues que los mantenedores marcaron para octubre, abiertos y aptos para principiantes. Explorar issues de Hacktoberfest

Feat: add `prevPermutation`, `nextPermutationBy` and a version of `nextPermutation` that goes back to the first perm?

Abierto
  • ¿Algo no está bien?
#499 7 comentarios 0 reacciones 0 asignados Ver en GitHub

@gksato ya está trabajando en esto.

Desde el 3/8/2024.

Evaluación

Dificultad
5/5
Tiempo estimado
Más de una semana
Aptitud para principiantes
25/100
Tipo de issue
Nueva funcionalidad
Claridad
Bastante claro
Estado de actividad
Estancado
Stack tecnológico
haskell
Área
data

Línea de trabajo

Empieza leyendo Data.Vector.Generic.Mutable y los cambios de permutación referenciados como completados en #498. Revisa la API existente de nextPermutation y nextPermutationBy y las variantes primed propuestas; después, consulta la discusión del issue para comprobar las preocupaciones sobre los nombres. Se considera terminado cuando haya una decisión aprobada por un maintainer sobre si las variantes restantes deben formar parte de la API pública y cómo deberían llamarse.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

When I was authoring #498, I noticed that there is no implementation of prevPermutation or nextPermutationBy. I also got surprised that nextPermutation, unlike in C++, does not go back to the first permutation when the argument holds the last permutation (I understand the reason for the decision, though). What do you think of adding the functions below? I'm not sure especially about the prime versions of the functions, but it doesn't hurt to record the idea, anyway.

Update: In #498, we have added (next|prev)Permutation(By)?. The only remaining task is to decide whether we should add the primed versions (next|prev)Permutation(By)?' and devise a better naming convention instead of using primes.

module Data.Vector.Generic.Mutable where

-- | Compute the (lexicographically) next permutation of the given vector in-place.
-- Returns False when the input is the last permutation; in this case the vector
-- will be updated to the first permutation, as aligned with the behavior of the C++ function 
-- @std::next_permutation@.
nextPermutation' :: (PrimMonad m, Ord e, MVector v e) => v (PrimState m) e -> m Bool

nextPermutationBy' :: (PrimMonad m, MVector v e) => (e -> e -> Ordering) -> v (PrimState m) e -> m Bool
prevPermutation' :: (PrimMonad m, Ord e, MVector v e) => v (PrimState m) e -> m Bool
prevPermutationBy' :: (PrimMonad m, MVector v e) => (e -> e -> Ordering) -> v (PrimState m) e -> m Bool

-- DONE in #498
-- nextPermutationBy :: (PrimMonad m, MVector v e) => (e -> e -> Ordering) -> v (PrimState m) e -> m Bool
-- prevPermutation :: (PrimMonad m, Ord e, MVector v e) => v (PrimState m) e -> m Bool
-- prevPermutationBy :: (PrimMonad m, MVector v e) => (e -> e -> Ordering) -> v (PrimState m) e -> m Bool

Note: the implementation can be done in one function:

nextPermutationByLtUtil :: (PrimMonad m, MVector v e) => Bool -> (e -> e -> Bool) -> v (PrimState m) e -> m Bool
nextPermutationByLtUtil always lt v
   | dim < 2 = return False
   | otherwise = stToPrim $ do
       !vlast <- unsafeRead v (dim - 1)
       !k <- decrLoop (dim - 1) vlast
       when (always || k > 0) $ reverse $ unsafeSlice k (dim - k) v
       return $ k > 0
   where
     dim = length v
     -- find the largest index k such that a[k] < a[k + 1], and then pass to the rest.
     decrLoop !i1 !vi1 | i1 > 0 = do
       let !i = i1 - 1
       !vi <- unsafeRead v i
       if vi `lt` vi1 then i1 <$ swapLoop i vi i1 vi1 dim else decrLoop i vi
     decrLoop _ !_ = return 0
     -- find the largest index l greater than k such that a[k] < a[l], and swap a[k] and a[l].
     swapLoop !k !vk = go
       where
         -- binary search.
         go !l !vl !r | r - l <= 1 = do
           -- Done; do the rest of the algorithm.
           unsafeWrite v k vl
           unsafeWrite v l vk
         go !l !vl !r = do
           !vmid <- unsafeRead v mid
           if vk `lt` vmid
             then go mid vmid r
             else go l vl mid
           where
             !mid = l + (r - l) `shiftR` 1

nextPermutation = nextPermutationByLtUtil False (<)
nextPermutation' = nextPermutationByLtUtil True (<)
nextPermutationBy cmp = nextPermutationByLtUtil False (\x y -> cmp x y == LT)
nextPermutationBy' cmp = nextPermutationByLtUtil True (\x y -> cmp x y == LT)
prevPermutation = nextPermutationByLtUtil False (>)
prevPermutation' = nextPermutationByLtUtil True (>)
prevPermutationBy cmp = nextPermutationByLtUtil False (\x y -> cmp x y == GT)
prevPermutationBy' cmp = nextPermutationByLtUtil True (\x y -> cmp x y == GT)
Lenguaje dominante
Haskell
Estrellas
404
Forks
146
Merge medio
1 d 22 h
PR fusionados (30 d)
3

Preparar el entorno

Este proyecto no incluye contenedor de desarrollo, Dockerfile ni guía de contribución, así que la configuración corre por tu cuenta: empieza por su README y consulta nuestra guía para la primera contribución para los pasos generales.

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de haskell/vector

Todos los issues de haskell/vector

Issues similares

Más issues de Haskell

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.