1

最初に: 私の英語はあまり上手ではありません。申し訳ありません :(

だから、これは私が解決しなければならない問題です：

-- Based on a simple math game: given a list of numbers use the four basic 
-- operations (+, -, /, *)  between them to find (or be as close as possible to) 
-- another given number

私の問題の例がありますが、解決するにはもっと具体的にする必要があり、「haskell モード」では考えられません。私は C++ プレーヤーです :(

だから、私はこれを行っています：

-- Find all possible 2-combinations of the elements of xs.
   pairs :: [Int] -> [(Int, Int)]
   pairs xs = [(x, y) | (x:ys) <- tails xs, y <- ys]

 operations :: (Int, Int) -> [(Int, Int, Char, Int)]
 operations (x, y) =
         [ (x, y, '+', x + y) ] ++
         [ (x, y, '*', x * y) ] ++
         [ (x, y, '-', x - y) | x > y ] ++
         [ (x, y, '/', x `div` y) | x >= y, x `mod` y == 0]

次のことを行うには、別の関数 (「解決」) を実装する必要があります。

「解決」関数は、結果のすべてのノードを含むリストを返し、使用可能な数字のリストから数字のペアを選択し、選択したパートナーに可能な操作を適用します。

使用可能な番号のリスト (使用されている番号を削除して新しい番号を追加) と操作のリスト (最新の操作を反映するため) を更新する必要があります。

例：

solve ( 100 , [1,4,5] , [] )

[ ( 100 , [5,5] , [(1,4,'+',5)] ), -- take first tuple 1,4 add and subs into "new tuple"5,5
( 100 , [3,5] , [(4,1,'-',3)] ),
( 100 , [6,4] , [(1,5,'+',6)] ),
( 100 , [4,4] , [(5,1,'-',4)] ),
( 100 , [9,1] , [(4,5,'+',9)] ),
( 100 , [1,1] , [(5,4,'-',1)] ),
( 100 , [20,1] , [(4,5,'*',20)] ) ]

最初にいくつかの数字を取り (ペア関数を使用)、

[number,number,'operation',result]「操作」ができることの2 番目のショー。

私はこのようなものを持っています:

solve(n,ns) = [ e | ns' <- pairs ns
                  , e   <- operations ns']

しかし、私はそれを機能させることはできません。

編集：

私は本当にあなたの答えに感謝します、どうもありがとう、しかし私が求めている機能を実行できない場合、私はHaskellで本当に新しいので、あなたの開発を理解できません:(

私が言うように、数値のリストと、メインの投稿で書いた 2 つの操作 (操作とペア) を使用して、これを行う別の関数を作成する関数が必要です。

例）

solve ( 100 , [1,4,5] , [] )

[ ( 100 , [5,5] , [(1,4,'+',5)] ),
( 100 , [3,5] , [(4,1,'-',3)] ),
( 100 , [6,4] , [(1,5,'+',6)] ),
( 100 , [4,4] , [(5,1,'-',4)] ),
( 100 , [9,1] , [(4,5,'+',9)] ),
( 100 , [1,1] , [(5,4,'-',1)] ),
( 100 , [20,1] , [(4,5,'*',20)] ) ]

迅速な回答をありがとうございますが、回答をより具体的にする必要があります。

4

1 に答える 1

2

これは実に巧妙な問題ですが、最初は思ったよりややこしい問題です。

、'+'、'-'、'*'および'/'

data Op = Plus | Minus | Mult | Div deriving (Eq, Ord)

ops = [Op]
ops = [Plus, Minus, Div, Mult]

instance Show Op where
  show Plus  = "+"
  show Minus = "-"
  show Div   = "/"
  show Mult  = "*"

および一連の数値ns、ある目標に最も近い式について、各数値を 1 回だけ使用するすべての可能な算術式を検索します。これを解決するには、問題を抽象的に表現し、明らかに正しい方法で解決してから、いくつかの最適化を適用します。

式を表すデータ型を考えてみましょう。各用語は、 と呼び、 とそれが作用する他の 2 つの組み合わせ、または「純粋な」値、つまりそれ自体である整数のいずれかTermである必要があります。OpTerms

data Term = Ap Op Term Term | Pure Double

として(2 + (3 * 4))表したものApp Plus (Pure 2) (App Mult (Pure 3) (Pure 4))です。そのような が与えられたTerm場合、それを再帰的にトラバースして、それを出力したり、結果を計算したりできます。

instance Show Term where
  show (Pure x)    = show x
  show (Ap op l r) = "(" ++ show l ++ " " ++ show op ++ " " ++ show r ++ ")"

これについては後ほど詳しく調査しますが、今のところは世代に焦点を当てる必要があります。

数のリストにある任意の数を指定すると、、、またはのいずれかの 3つの異なる方法でそれを含むn <- nsaを構成できます。これは、から構築できるすべてのものの完全に有効な再帰的定義です。構築しましょう。TermPure nTerm op n otherTerm op other nopopsotherData.List.delete n nsnsnTermsns

まず、 の各要素を選択または「フォーカス」する方法が必要nsです。これを行うには、元のリストの要素ごとに 1 つずつ、リストをトリプルのリストに変換するnsasのジッパーを形成します。pares :: [a] -> [([a], a, [a])]中央の要素は「フォーカスされた」値で、左側のリストはフォーカスされた値の左側にあった要素で、右側のリストは右側にあった値です。これはやり過ぎのように思えるかもしれませんが、後で役に立ちます。

pare :: [a] -> Int -> ([a], a, [a])
pare xs n = pare' n ([], xs) -- accumulate the left and right sides
  where
    -- we end up storing the left list in reverse, which is the style of zippers
    -- it seems a little weird, but it makes the code very simple and it shouldn't
    -- affect our problem
    pare' 0 (left, x:right) = (left, x, right)
    pare' n (left, x:right) = pare' (n-1) (x:left, right)

-- 'pare' is a little dangerous since it can have out of bounds errors,
-- but 'pares' can not.
pares :: [a] -> [([a], a, [a])]
pares xs = map (pare xs) [0..length xs - 1]

そして今、私たちは取得するために呼び出すことができpares [1,2,3]ます

[ ( []    , 1 ,  [2,3] )
, ( [1]   , 2 ,  [3]   )
, ( [2,1] , 3 ,  []    ) ]

ここからは、内包表記allTerms :: [Double] -> [Term]を使用した簡単な定義Listです。

allTerms ns =
  [ result
  | (left, n, right) <- pares ns
  , result <- Pure n : (concat [ [ Ap op (Pure n) term, Ap op term (Pure n) ]
                               | op   <- ops
                               , term <- allTerms (left ++ right)
                               ])
  ]

さて、それほど簡単ではありません。常に「少なくとも」 を返したいので(Pure n) Term、再帰項を処理するリスト内包表記を分離する必要があります。それ以外の場合、[]リストは の再帰的な部分項を返すことができないため、常に結果として得られallTerms []ます。

Monadこの表記法は少し難しいので、 ic 表記法に変更しましょう。すべてのList内包表記はList Monad.

allTerms ns = do
  (left, n, right) <- pares ns
  let branches = do
        op <- ops
        term <- allTerms (left ++ right)
        [ Ap op (Pure n) term, Ap op term (Pure n) ]
  Pure n : branches

do記法を使用すると、不要なブラケットを取り除くことができ、後で最適化するためのより良い基盤が得られます。とりあえず、テストするだけです。

*Main> mapM_ print $ allTerms [1,2]
1.0
(1.0 + 2.0)
(2.0 + 1.0)
(1.0 - 2.0)
(2.0 - 1.0)
(1.0 / 2.0)
(2.0 / 1.0)
(1.0 * 2.0)
(2.0 * 1.0)
2.0
(2.0 + 1.0)
(1.0 + 2.0)
(2.0 - 1.0)
(1.0 - 2.0)
(2.0 / 1.0)
(1.0 / 2.0)
(2.0 * 1.0)
(1.0 * 2.0)

これが包括的であることを確認するのは簡単なはずです。また、私たちの定義の弱点も示しています。問題の対称性の多くを無視していました。たとえば、すでに訪れた数値の部分項を生成する必要はありません (これらの項は後の項によって再び生成されます。さらに、opがPlusまたはの場合Mult、可換性を利用できます。これを修正するために簡単に書き直します。 .

allTerms ns = do
  (left, n, right) <- pares ns
  let branches = do
        op <- ops
        term <- allTerms right -- we no longer visit the left terms
                               -- this is the value of using 'pares'
        makeApps op (Pure n) term
  Pure n : branches
  where
    -- makeApps only applies symmetry when the operator is Div or
    -- Minus.
    makeApps Plus t1 t2 = [Ap Plus t1 t2]
    makeApps Mult t1 t2 = [Ap Mult t1 t2]
    makeApps op   l  r  = [Ap op l r, Ap op r l]

その場合ns = [1,2,3]、最初のバージョンでは 195 が生成されTermます。2 つ目は、対称性を利用して 57 秒しか生成しませTermん。これはある程度理にかなっていますので、先に進みましょう。

考えられるすべての を生成したTermので、それらを評価する必要があります。例のように、Showこれは比較的単純な再帰的な定義です。

calcTerm :: Term -> Double
calcTerm (Pure x) = x
calcTerm (Ap Plus  l r) = calcTerm l + calcTerm r
calcTerm (Ap Minus l r) = calcTerm l - calcTerm r
calcTerm (Ap Mult  l r) = calcTerm l * calcTerm r
calcTerm (Ap Div   l r) = calcTerm l / calcTerm r

Termに最も近い値を持つ を探しているとしましょうgoal :: Double。Term tすべてに「エラー」の注釈を付けて、abs (goal - calcTerm t)それで並べ替えることができます。特殊なsortBy :: (a -> a -> Ordering) -> [a] -> [a]fromを使用する必要がありますData.List。

import Data.List (sortBy)

bestTerm :: Double -> [Term] -> (Double, Term)
bestTerm g =
  minimumBy (\(a, _) (b, _) -> a `compare` b)
  . map (\t -> (abs (g - calcTerm t), t))

または、いくつかの特殊な関数を使用すると、Control.Arrow.&&&最もData.Ord.comparing速く書くことができます

bestTerm :: Double -> [Term] -> (Double, Term)
bestTerm g =
  minimumBy (comparing fst) . map (first error) where error t = abs (g - calcTerm t)

そして私たちは質問に答え始めることができます

*Main> bestTerm 31 $ allTerms [1..5]
(0.0,(1.0 + ((3.0 * (4.0 * 5.0)) / 2.0)))

length $ allTerms [1..10]しかし、待つことは私の忍耐を打ち負かすので、時々だけです。数値(7^n-1)/6に関する用語があるように見えるので ( Sloaneを参照)、47,079,208秒を計算するのを待ちます。nTerm

これにより、問題に対する答えを計算する方法が示され、結果を最適化する方法を検索するためのさまざまな場所が得られることを願っています。

そして、あなたの例に対する答えは(79.0, (1.0 + (4.0 * 5.0)))

于 2013-07-11T19:35:49.843 に答える