2

私は現在Pythonで作業していますが、どこでストローをつかむべきかわからない問題に直面しています。これがどこかの最初のアルゴリズム CS クラスでカバーされている場合は許してください。私のバックグラウンドは実際には経済学です。私は財務データを扱っていて、出力と入力は知っていますが、操作の順序を取得する方法がわかりません。

たとえば、収益に対する最終的な価格の比率は 2 ですが、入力は 10 (価格) と 5 (収益) です。これを見ただけで、10/5 が 2 に相当することがわかります。ただし、問題は演算の順序です....これは、加算、乗算、除算、平方根のいずれかです。

この部分は、私が持っていれば実行可能のようです

inputs = [10,5]
output = 2

def deduction_int(inputs, output):
    initial_output = 0
    while initial_output != output:
    try adding, try subtracting (inverse), try dividing(inverse)

それ自体が理解されたとき、または答えがある場合は「yay」を出力します

上記のコードは明白で素早いように見えますが、3 つの変数を追加すると ....

入力：10、5、7 出力：2.14

(10 + 5) / 7 = 2.14 などの状況。

数値が異なる順序で実行される可能性がある状況に行き詰まっています。たとえば、7 で割る前に 10+5 が実行されます。これは一般的なアルゴリズム タイプの問題ですか? もしそうなら、教科書の説明（アルゴリズムの名前、教科書）をどこで探すのですか？

ありがとう！

4

2 に答える 2

2

これがブルートフォースアルゴリズムです。

from __future__ import division
import itertools as IT
import operator

opmap = {operator.add: '+',
         operator.mul: '*',
         operator.truediv: '/'}
operators = opmap.keys()

def deduction_int(inputs, output):
    iternums = IT.permutations(inputs, len(inputs))
    iterops = IT.product(operators, repeat=len(inputs)-1)
    for nums, ops in IT.product(iternums, iterops):
        for result, rstr in combine(nums, ops):
            if near(result, output, atol=1e-3):
                return rstr

def combine(nums, ops, astr=''):
    a = nums[0]
    astr = astr if astr else str(a)
    try:
        op = ops[0]
    except IndexError:
        return [(a, astr)]
    # combine a op (...)
    result = []
    for partial_val, partial_str in combine(nums[1:], ops[1:]):
        r = op(a, partial_val)
        if len(nums[1:]) > 1:
            rstr = '{}{}({})'.format(astr, opmap[op], partial_str)
        else:
            rstr = '{}{}{}'.format(astr, opmap[op], partial_str)
        assert near(eval(rstr), r)
        result.append((r, rstr))
    # combine (a op ...)
    b = nums[1]
    astr = '({}{}{})'.format(astr,opmap[op], b)
    for partial_val, partial_str in combine((op(a, b),)+nums[2:], ops[1:],
                                            astr):
        assert near(eval(partial_str), partial_val)
        result.append((partial_val, partial_str))
    return result

def near(a, b, rtol=1e-5, atol=1e-8):
    return abs(a - b) < (atol + rtol * abs(b))

def report(inputs, output):
    rstr = deduction_int(inputs, output)
    return '{} = {}'.format(rstr, output)

print(report([10,5,7], (10+5)/7))
print(report([1,2,3,4], 3/7.))
print(report([1,2,3,4,5], (1+(2/3)*(4-5))))

収量

(10+5)/7 = 2.14285714286
(1+2)/(3+4) = 0.428571428571
(1+5)/((2+4)*3) = 0.333333333333

主なアイデアは、入力値のすべての順序と演算子のすべての順序を単純に列挙することです。例えば、

In [19]: list(IT.permutations([10,5,7], 3))
Out[19]: [(10, 5, 7), (10, 7, 5), (5, 10, 7), (5, 7, 10), (7, 10, 5), (7, 5, 10)]

次に、入力値の各順序と演算子の各順序をペアにします。

In [38]: list(IT.product(iternums, iterops))
Out[38]: 
[((10, 5, 7), (<built-in function add>, <built-in function mul>)),
 ((10, 5, 7), (<built-in function add>, <built-in function truediv>)),
 ((10, 5, 7), (<built-in function mul>, <built-in function add>)),
 ((10, 5, 7), (<built-in function mul>, <built-in function truediv>)),
 ...

このcombine関数は、num の順序と op の順序を取り、num と op のすべての可能なグループを列挙します。 )

Out[65]: [(45, '10+(5*7)'), (45, '10+((5*7))'), (105, '(10+5)*7'), (105, '((10+5)*7)')]

タプルのリストを返します。各タプルは、数値とrstrその値に評価されるグループ化された操作の文字列表現 で構成される 2 タプルです。

したがって、すべての可能性をループしてrstr、評価すると に近い数値を生成する を返すだけoutputです。

for nums, ops in IT.product(iternums, iterops):
    for result, rstr in combine(nums, ops):
        if near(result, output, atol=1e-3):
            return rstr

参考文献:

于 2013-10-03T21:18:51.540 に答える