haskell / haskell/vector

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

未关闭
#499 7 条评论 0 个 reaction 已指派 0 人 在 GitHub 查看
主要语言
Haskell
星标
400
派生
145
PR 合并指标
30 天内没有已合并 PR

描述

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.

```haskell
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:

```haskell
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)
```

贡献指南

这个仓库没有索引到贡献指南

评估

这个 Issue 还没有评估数据。

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。