我正在研究数学难题的蛮力解决方案，并且正在努力抽象我的解决方案，以便我可以轻松解决各种大小的难题。
拼图可以在https://www.think-maths.co.uk/uniquedistance处找到。如果您想在不破坏剧情的情况下自己解决难题，请不要继续阅读。如果您只想帮助我解决手头的Haskell编程问题，则无需花时间研究难题。
我在下面所示的解决方案中试图做的是从n个不同选项的池中找到大小为n^2的子集，这样，其中两个选项中的某些函数metric对于所有选择的子集中的选项对。
起初，我按照以下方式写了一个解决方案：>
combinations :: Int -> [a] -> [[a]] combinations 0 _ = [[]] combinations _ [] = [] combinations n xs = [ a:rec | (a:as) <- tails xs, rec <- combinations (pred n) as ]这给了我所有可能的子集，随后检查了对于使用该子集选择的所有可能的对，是否有任何单个子集满足给定
metric的唯一性要求
import qualified Data.IntSet as IS check :: [a] -> Bool check = noDupes . metrics where metrics ps = [ metric a b | (a:bs) <- tails ps, b <- bs ] noDupes = go IS.empty go _ [] = True go s (x:xs) | IS.member x s = False | otherwise = go (IS.insert x s) xs[从那里开始，
filter check (combinations n)将为我提供任何给定n的正确解决方案。但是，为了提高性能，我想更改计算方式，而不是先生成大小为n的所有子集，然后仅检查约束是否满足全部子集，而不是更早地丢弃小于n元素的子集。 ，这样我就可以更少地计算昂贵的metric。
我无法轻松地将上述解决方案转换为所需的解决方案，但到目前为止，我已经能够提出以下建议（其中还包括一些更具体的类型和指标的定义，但我认为如果您不在乎拼图的细节，则可以忽略它）：
import qualified Data.IntSet as IS import Data.Maybe import Control.Monad import Data.List import Linear.V2 (V2(..)) -- euclidean distance squared metric :: V2 Int -> V2 Int -> Int metric (V2 x1 y1) (V2 x2 y2) = ((x1-x2)^2) + ((y1-y2)^2) -- metric of a new candidate point to all previous points metrics p = map (metric p) -- check if the previously seen set of metrics are compatible with the metrics -- of a new candidate. Nothing if they're not, and Just the union of the -- previous and new metrics. checkCompatibility :: IS.IntSet -> [Int] -> Maybe IS.IntSet checkCompatibility s [] = Just s checkCompatibility s (x:xs) | IS.member x s = Nothing | otherwise = checkCompatibility (IS.insert x s) xs -- all combinations of choosing 1 points from the input combinations1 :: [V2 Int] -> [[V2 Int]] combinations1 xs = do (a:bs) <- tails xs let ret = [a] return ret -- all combinations of choosing 2 points from the input combinations2 :: [V2 Int] -> [[V2 Int]] combinations2 xs = do (a:bs) <- tails xs let ret = [a] (b:cs) <- tails bs let sset = checkCompatibility IS.empty (metrics b ret) guard (maybe False (not . IS.null) sset) let ret' = b:ret return (reverse ret') -- all combinations of choosing 3 points from the input, where the "metric" between any pair of points is unique combinations3 :: [V2 Int] -> [[V2 Int]] combinations3 xs = do (a:bs) <- tails xs let ret = [a] (b:cs) <- tails bs let sset = checkCompatibility IS.empty (metrics b ret) guard (maybe False (not . IS.null) sset) let ret' = b:ret (c:ds) <- tails cs let sset' = checkCompatibility (fromJust sset) (metrics c ret') guard (maybe False (not . IS.null) sset') let ret'' = c:ret' return (reverse ret'') -- all combinations of choosing 4 points from the input, where the "metric" between any pair of points is unique combinations4 :: [V2 Int] -> [[V2 Int]] combinations4 xs = do (a:bs) <- tails xs let ret = [a] (b:cs) <- tails bs let sset = checkCompatibility IS.empty (metrics b ret) guard (maybe False (not . IS.null) sset) let ret' = b:ret (c:ds) <- tails cs let sset' = checkCompatibility (fromJust sset) (metrics c ret') guard (maybe False (not . IS.null) sset') let ret'' = c:ret' (d:es) <- tails ds let sset'' = checkCompatibility (fromJust sset) (metrics c ret'') guard (maybe False (not . IS.null) sset'') let ret''' = d:ret'' return (reverse ret''')请注意，如果没有递归地使用
n参数编写它，那么对于combinations的不同值的各种实现如何极其相似，就像我上面上面的原始n函数一样。
我正在尝试解决的问题是如何对我的combinations1，combinations2，combinations3等参数进行参数化，这样我就不必为n的每个值编写繁琐的解决方案。
-- all combinations of choosing n points from the input, where the "metric" between any pair of points is unique combinationsN :: Int -> [V2 Int] -> [[V2 Int]] combinationsN 0 _ = [[]] combinationsN _ [] = [] combinationsN n xs = undefined出于教育目的，我想我主要对如何完成此任务感兴趣，同时在步骤之间手动插入状态，以便以后可以使用
Control.Monad.State将其完善为解决方案，但是我也希望了解步骤之间保持状态的其他方法。
我也希望获得更好的问题标题的建议。我真的不知道该怎么做，我真的不知道该问什么。
谢谢！
我正在研究数学难题的强力解决方案，并且正在努力抽象我的解决方案，以便我可以轻松解决各种大小的难题。可以在https：//www.think-maths ....
嗯，你有主意。在IntSet中组合的旁边增加combinations：
我相信算法首先是效率的关键因素，然后才是实现有效数据结构的关键。因此，像大多数情况下，蛮力是浪费的。