Expressing algorithmic problem as a mathematical problem

98 Views Asked by At

I'm working in an algorithmic problem, which can surely be solved without any math involved, however I'm practicing (translating problems to formal definitions). I've done some baby steps however I need some expert help.

algorithmic problem:
Given Two stacks a and b , stack a contains some random amounts of numbers and stack b is empty. and given exactly 11 operations , sort the numbers with the lease amount of operations.

~ sa: swap the first 2 elements at the top of stack a.
~ sb: same as above for b.
~ ss: sa and sb at the same time.
~ pa: take the first element of b and put it at the top of a.
~ pb: same as above for b.
~ ra: shift up all elements of stack a by 1 The first element becomes the last one.
~rb: same as above for b.
~rr: ra and rb at the same time.
~rra: shift down all elements of stack a by one The last element becomes the first one.
~ rrb: same as above for b.
~ rrr : rra and rrb at the same time.

one cannot compare without comparison and in the algorithmic problem its allowed because its not a movement per se, in algo problem you can compare what you're at, and you're arrive at what you're at by looping, so I thought lets just say

cab: compare any or all elements in a and b any time.

my baby steps:

  • given a sequence $A$ of $n$ numbers $\left\langle a_{1}, a_{2}, ...a_{n} \right\rangle $ and an empty sequence $B$. produce a permutations (reordering) of the input $\left\langle a_{1}, a_{2}, ...a_{n} \right\rangle $ so that $\left\langle a_{1} \le a_{2} \le a_{n} \right\rangle $

My main problem is how to formalize these operations (sa,sb ...) in math entities, one idea is functions, but I'm not that good to complete the formalization. What do you think ?