Скоби алгоритъм

Например, ако имаме числата:
1234
Трябва ми програма, която да ги "скобира" по всички възможни начини:
(((12)3)4)
((12)(34))
(1((23)4))
и т.н.
Задачата е свързана с задачата за предсавяне на число чрез няколко други числа само със събиране, зваждане, умножение и деление.

айде, само идеята ти давам - всеки разделител му назначаваш един бит. в случая, четири цифри, значи три разделителя, значи 3 бита. пробягваме всички възможни стойности на трите бита, което са 8 числа. където имаме 1, цифрите ги слепяме, а където 0, ги отделяме. оставям на тебе да си сложиш скобите.




NE SUTOR ULTRA CREPIDAM

Това алгоритъма с битовете нещо не ми харесва, защото ми се струва неестествен. Аз предлагам друг рекурсивен алгоритъм:

1. Първият резултат се получава samo като числото се загради със скоби.
2. Следващите резултатите са всички разделяния на числото на две части и пускането на всяка част на т. 1.

Това е всичко. Ето и решението на Python:

def skobi(num):

    if len(num) == 1:

        yield  num

    else: 

        yield  "(" + num + ")"

    if len(num)>2:

        for k in range(1,len(num)):

            for a in skobi(num[:k]):

                for b in skobi(num[k:]):

                    yield "(" + a+b +")"

    

# example with 1234    

for s in skobi( str(1234) ):

    print s

Ето резултата за 1234:

(1234)
(1(234))
(1(2(34)))
(1((23)4))
((12)(34))
((123)4)
((1(23))4)
(((12)3)4)

Благодаря, Лук.
На мене през седмицата ми хрумна тая идея и всико стана.
Мислех си и дали няма да стане с полски запис...
"не мож ли се оправи сам" - все пак съм само осми клас.

Сега остава само да лепна към скобите и по една функция, и се получава приятна програмка.

Като за 8-ми клас много добра цел си си поставил. Aз пък в осми клас четях списание "Kомпютър за вас" и "Млад техник" и учех Basic и не съм питал по Интернет как се решават задачите по програмиране, ама ако имаше Интернет сигурно и аз щях да питам.

А твоята задача има доста по просто решение. Не знам защо си тръгнал въобще да разбиваш на скоби.

from __future__ import division



ops= ['', '+', '-', '/', '*']



def test( digits, val, cmd="" ):

    if len(digits) < 2:

        if val == eval(cmd+digits):

            print cmd+digits

        #print eval(cmd+digits)

    else:

        for o in ops:

            test( digits[1:], val, cmd+ digits[0]+o )



test("1234", 9)  

test("123456789", 1280) # това второто е бавно на бавен компютър

Така 9 има 2 решения:
12*3/4
1*2+3+4

А пък 1280 има повече.

Благодаря.
Само че задачата възникна при един математически въпрос, и чак после я свързах с програмирането. Не съм я зел от някой конкурс, примерно, макар че изглежда че си е за конкурс.