Repository navigation
Feat: add prevPermutation, nextPermutationBy and a version of nextPermutation that goes back to the first perm? #499
Description
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 BoolNote: 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)
Activity
Shimuuar commentedon Jul 22, 2024
I think adding full complement of
{next,prev}Permutation{,By}is quite reasonable whenever we have function which works withOrdwe provide way to supply comparison function as parameter. And addingprevvariant seems sensible too even if they could be made usingDownI'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 commentedon Jul 22, 2024
Thanks for your comment. It looks like we're on the same page.
Byversions are absolute necessity,prevversions are sensible, and primed version is... um, questionable. Even if we put necessity aside (which is a big premise!), it's a terrible name. MaybenextPermutationGoBack? 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:
Reply to P.S.: Indeed, it's pity. Take your time, it's only a day from the submission of my PR.
Shimuuar commentedon Jul 26, 2024
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 calledgksato commentedon Aug 3, 2024
I'm working on it in #498.
gksato commentedon Aug 19, 2024
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}Permutationthemselves. However, I'm still uncertain about their value to end users. We could keep this issue open until someone comes in.Shimuuar commentedon Aug 22, 2024
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 namegksato commentedon Aug 22, 2024
True. If we prioritize grammatical readability, we could add
CyclicallyorInCycleat end of the ident, but it's longer (the latter is shorter thanBijective, though).