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

[gksato]

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)

[Shimuuar]

I think adding full complement of {next,prev}Permutation{,By} is quite reasonable whenever we have function which works with Ord we provide way to supply comparison function as parameter. And adding prev variant seems sensible too even if they could be made using Down

I'm not sure about primed versions. Whether it's good idea to expand API that much. That's also poor naming prime s usually reserved for indication of strictness

P.S. I didn't get to benchmarking of PR yet. It's pity we don't have way to ask GHC to specialize large functions very aggressively instead of inlining them

[gksato]

Thanks for your comment. It looks like we're on the same page. By versions are absolute necessity, prev versions are sensible, and primed version is... um, questionable. Even if we put necessity aside (which is a big premise!), it's a terrible name. Maybe nextPermutationGoBack? It's not like the intension is crystal clear with this name... Oh, nextPermutationCpp... just joked but I don't even know if I can forget this as a joke.

Or can we just add some guide to the doc comment:

-- | 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 not be updated, unlike the behavior of the C++ function 
-- @std::next_permutation@.
--
-- If you want to align the behavior with the C++ version, you need to write the
-- following wrapper yourself:
-- > nextPermutationGoBack v = do
-- >   res <- VGM.nextPermutation v
-- >   if res then return () else VGM.reverse v
-- >   return res

Reply to P.S.: Indeed, it's pity. Take your time, it's only a day from the submission of my PR.

[Shimuuar]

I think we should first add four {next,prev}Permutation{,By}. They should be added in any case and naming is clear. After that we could return whether we want them and how they should be called

[gksato]

I think we should first add four {next,prev}Permutation{,By}. They should be added in any case and naming is clear.

I'm working on it in #498.

[gksato]

For the sake of the readability of this issue itself: we have added {next,prev}Permutation{,By} in #498.

During the implementation of #498, I think I have devised a suitable naming convention: {next,prev}PermutationBijective{,By}. "Bijective" may be unfamiliar to some users, though.

Regarding the necessity of the primed/"bijective" versions, they have many useful properties for testing and benchmarking {next,prev}Permutation themselves. However, I'm still uncertain about their value to end users. We could keep this issue open until someone comes in.

[Shimuuar]

Another naming possibility is to use cycle. It's both shorter and I think clearer but I'm not sure where to add it to identifier name

[gksato]

True. If we prioritize grammatical readability, we could add Cyclically or InCycle at end of the ident, but it's longer (the latter is shorter than Bijective, though).