text:
How does math work in Anastasiya's world?
Background:
Standard operation math like basic addition and multiplication in the real world work like these:
12 + 123 = 135

and
12 * 123 = 1476

That's not interesting and boring! Many schools are already interpreting this as practice, practice, practice of formal algorithms. That implies a pretty rigid and boring mathematical diet and is not what is intended in this challenge. Get ready to play some fun on our beloved site.
Consider the process of adding two positive integer numbers, then adding again all the digits of its result. Repeating with the addition until only a single digit is obtained. For example:

The result of 12 + 123 is 135.
Adding all the digits of 135 we obtain 1 + 3 + 5 = 9.

The number of steps required to obtain a single digit value 9 in this repeated addition is 2.
As with the previous process of the addition, the multiplication of two positive integer numbers follows the same process. Multiply all the digits of its result and then repeating this process until only a single digit remains. Take the above example:

The result of 12 * 123 is 1476.
Multiply all the digits of 1476 we obtain 1 * 4 * 7 * 6 = 168.
Multiply again all the digits of 168 we obtain 1 * 6 * 8 = 48.
Multiply again all the digits of 48 we obtain 4 * 8 = 32.
Multiply once again all the digits of 32 we obtain 3 * 2 = 6.

The number of steps required to obtain a single digit value 6 this repeated multiplication is 5.
For this challenge's sake and avoiding any misuse of math notations, I introduce these two dummy notations: (+) and (*), but you may use any notation you like, which work like the followings:

The operation of repeated addition process to obtain a single value is 12 (+) 123 = 9.
The operation of repeated multiplication process to obtain a single value is 12 (*) 123  = 6.

Challenge:
The challenge is to write either a program or a function which can perform both of operations as explained in the background section: (+) and (*).
Input:
The inputs of the program or the function are two positive integers and one operation either (+) and (*). The format of the input is an arbitrary choice of the programmer. You may format the input, for example, a (+) b or F(a, (+), b) or any format you wish.
Output:
The output of the program or the function must contain the result of operation and the number of steps required with freestyle format as you wish.
Test Cases (ignore the input and output format):
    81 (+) 31       -->   (4 ; 2)
    351 (+) 14568   -->   (6 ; 3)
    21 (*) 111      -->   (8 ; 3)
    136 (*) 2356    -->   (0 ; 2)

General rules:

This is code-golf, so the shortest answer in bytes wins the challenge.
Don't let esolangs discourage you from posting an answer with regular languages. Enjoy this challenge by providing an answer as short as possible with your programming language. If you post a clever answer and a clear explanation, your answer will be appreciated (hence the upvotes) regardless of the programming language you use.
Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/ method with the proper parameters, full programs, etc. The choice is yours.
If possible, your program can properly handle large numbers. If not, that will just be fine.

Let the game begin!!

The repeated addition part (digital root) is essentially a duplicate of http://codegolf.stackexchange.com/q/1128/194

@PeterTaylor The addition part might be true, but there are additive and multiplicative persistence part here, so they're semi-related but not a dup, IMHO.

Great first question! And I recognize the general rules format and sentences from my own Questions. ;)

@KevinCruijssen Yup. that's right. Since it has no copyright so I duplicate it without your permission. Hehehe :D

Related: Manhattan and Fuzzy-Logic.

@Anastasiya-Romanova秀 "no copyright"? In XXI century? Nope; everything here is CC-BY-SA 3.0. Permission is granted when the content is submitted. Check the site footer.

Can the input to the function be (12, &[+], 123), where &[+] is short for &infix:< + > a reference to the infix numeric addition operator subroutine?

@BradGilbertb2gills Yes, of course. It's stated in the post by the way. Quote: "The format of the input is an arbitrary choice of the programmer".

Dyalog APL, 33 32 30 29 bytes
This extends APL to include the prefix notation +/A n₁ n₂ and ×/A n₁ n₂. (In fact, you can use any operation to the left of the /A.) Returns a list of {result, repetition count}.
A←{(⊃,≢)⍺⍺{∪⍵,⍨⍺⍺⍎¨⍕⊃⍵}⍣≡⍺⍺⍵}

A←{ define a higher-order function in terms of left-hand function ⍺⍺, and right-hand argument ⍵

(⊃,≢) the first element of, followed by the count of
⍺⍺{ the supplied function (+/ for sum or ×/ for product) fed to the higher-order function

∪ the unique elements of
⍵,⍨ the argument appended to
⍺⍺ the fed function applied to
⍎¨ the evaluation of each character of
⍕ the character representation of
⊃⍵ the first element of the argument

}⍣≡ applied repeatedly until the result is identical to the argument, beginning with
⍺⍺⍵ the originally fed function (+/ or ×/) applied to the original argument

} [end of higher-order function definition]

TryAPL online! (⍎ has been emulated with e for security reasons.)
Thanks to @ngn for saving a byte.

0 bytes (in jest)
Dyalog APL actually already has full support for Anastasiyan math; instead of (+) and (×), it uses +{n←0⋄n,⍺⍺{n+←1⋄⍺⍺/⍎¨⍕⍵}⍣=⍵⍺⍺⍨⍺} and ×{n←0⋄n,⍺⍺{n+←1⋄⍺⍺/⍎¨⍕⍵}⍣=⍵⍺⍺⍨⍺}.
Try 81 +{(⊃,≢)⍺⍺{∪⍵,⍨⍺⍺e¨⍕⊃⍵}⍣≡⍺⍺/⍺⍵} 31 and 21 ×{n←0⋄n,⍺⍺{n+←1⋄⍺⍺/e¨⍕⍵}⍣=⍵⍺⍺⍨⍺} 111.

Thanks for the answer, (+1). Can it handle large number inputs?

If you set ⎕FR←1287 (i.e. use IEEE 754-2008 128-bit decimal Floating-point Representation) and ⎕PP←34 (i.e. use 34 characters' Print Precision), you can use integers below 10³⁴.

Hmm, even though it has full support, aren't +{n←0⋄n,⍺⍺{n+←1⋄⍺⍺/⍎¨⍕⍵}⍣=⍵⍺⍺⍨⍺} and ×{n←0⋄n,⍺⍺{n+←1⋄⍺⍺/⍎¨⍕⍵}⍣=⍵⍺⍺⍨⍺} still quite a few bytes? I'm confused about how this is 0 bytes.. :S

@KevinCruijssen The OP allows any input notation. So, if a language happened to support default-notation Anastasiyan math out-of-the box, the multi-char glyph (+) would be the Anastasiyan +. Dyalog APL does support Anastasiyan math, but it uses a different multi-char glyph, just as * means power and you need × for multiplication, while / means replication and you need ÷ for division.

@Adám Ah ok, that makes sense. It's kinda bending OP's rules, but not breaking them. It's still pretty odd that instead of (+) you have +{n←0⋄n,⍺⍺{n+←1⋄⍺⍺/⍎¨⍕⍵}⍣=⍵⍺⍺⍨⍺} as input, but since OP indeed stated any input format will do, you can use the function as parameter. Hmm, I wonder if this is also possible in other programming languages which support functions as input.

@KevinCruijssen in Pyke it would be 1 byte and in Python 2 it would be input().

If I'm understanding this correctly, with the right golfing language, any task could be done with zero bytes.

@Acccumulation Well, sure, if you make a golfing language for the task. However, here we are just dealing with a task description which is permissive. Btw, APL isn't a golfing language.

Haskell, 108 bytes
f=map(read.pure).show
g h=(\x->(h.f$last x,length x+1)).takeWhile(>10).iterate(h.f)
(a#b)o=g(foldr1 o)$o a b

Defines the function # which first takes a and b and then the operator o. Fun fact: this works with any operator (actually, any function) you want!

Thanks for the answer, (+1). Can it handle large number inputs?

@Anastasiya-Romanova秀 Yes, it can handle numbers as big as your RAM since Haskell's Integer type is unbounded.

Pyke, 16 bytes
RE`DltImbRoKr)oh

Try it here!
RE               - evaluate the input as Pyke code
                 -  (`B` is product and `s` is sum, the second line is a tuple)
  `              - i = str(^)
    ltI      )   - if len(i) != 1:
       mb        -   map(i, int)
         R       -   get the `B` or `s` from input
          oK     -   o++
            r    -   goto_start()
              oh - o++ + 1

Takes multiply as B and add as s. The two numerical inputs are separated by commas.

Nice! Can we get an explanation?

Thanks for the answer, (+1). Can it handle large number inputs?

@Anastasiya-Romanova秀 it should be able to handle arbitrary numbers

I cannot test your code because the web is blocked since it's in violation of my parents' internet usage policy. T_T

Something like this:
Web Page Blocked!
You have tried to access a web page which is in violation of your internet usage policy.
URL: pyke.catbus.co.uk/?code=RE%60DltImbRoKr%29oh&input=B%0A21%2C+111&warnings=0
Category: Unrated

Hmm... I've no idea why it would be blocked... Image of output here

JavaScript (ES6), 59
Recursive function, the input format is tailored to simplify the recursive call:

operator : '+' or '*'
operands : array of two values

f=(o,v,s=1,t=eval(v.join(o)))=>t>9?f(o,[...t+''],s+1):[t,s]

Test

f=(o,v,s=1,t=eval(v.join(o)))=>t>9?f(o,[...t+''],s+1):[t,s]

;[
  [81,'+',31,     /* -> */ 4, 2]
, [351,'+',14568, /* -> */ 6, 3]
, [21,'*',111,    /* -> */ 8, 3]
, [136,'*',2356,  /* -> */ 0, 2]
].forEach(t=>{
  var [a,o,b,k1,k2] = t,
      [r,s]=f(o,[a,b]);
  console.log(k1==r && k2==s ? 'OK':'KO',a,o,b,'->',r,s)
})

Thanks for the answer, (+1). Can it handle large number inputs?

@Anastasiya-Romanova秀 up to the limit of javascript numeric format, 53 bits of precision (17 decimal digits)

Python 2, 60 bytes
f=lambda s,c=0:s[1:]and f(min(s).join(`eval(s)`),c+1)or(s,c)

Input is a string like 81+31, output is a tuple of a singleton string and a counter (e.g., ('4', 2).
Test it on Ideone.

If taking input as an array of strings and a single string is allowed, e.g., f(['81', '31'],'+'), a further byte can be saved, but that feels like stretching the rules a bit too far...

"The format of the input is an arbitrary choice of the programmer"

...in which case I'd even go as far and consider passing operator.add or operator.mul respectively ;)

ARM Machine Code, 48 bytes
Hex dump:
b570 2a00 bf0c 1840 4348 2101 230a e00c 3101 0015 fbb0 f6f3 fb06 0413 2a00 bf0c 192d 4365 0030 d1f5 0028 280a d2f0 bd70

This function doesn't depend any system calls or library functions. This is Thumb-2 code, which is a variable-length instruction encoding (2 or 4 bytes) for 32-bit ARM. Thus, the maximum value it can process is 2^32-1. 2 bytes could be dropped if it didn't conform to the AAPCS (46 bytes), since we wouldn't have to stack registers at the beginning.
Ungolfed assembly (GNU syntax):
.syntax unified
.text
.global anastasiya
.thumb_func
anastasiya:
    @Input:
    @r0 - First number
    @r1 - Second number
    @r2 - 0 for add, 1 for multiply
    @Output:
    @r0 - Resultant value
    @r1 - Number of steps
    push {r4,r5,r6,lr}
    cmp r2,#0
    ite eq @if r2==0
    addeq r0,r0,r1 @r0+=r1
    mulne r0,r0,r1 @else r0*=r1
    movs r1,#1 @r1 is the number of steps
    movs r3,#10
    b endloop
    loop:
        adds r1,r1,#1 @Increment number of steps
        movs r5,r2 @r5=1 if multiply, 0 if add
        parseDigits:
            udiv r6,r0,r3 @r6=r0/r3
            mls r4,r6,r3,r0 @r4=r0 - r6*r3
            @Last two operations were r4=r0%r3 (r3==10)
            cmp r2,#0
            ite eq @if r2==0
            addeq r5,r5,r4 @r5+=r4
            mulne r5,r5,r4 @else r5*=r4
            movs r0,r6 @r0=r6 (Set r0 to r0/10)
            bne parseDigits @while (r0!=0)
        @Now our new total is in r5
        movs r0,r5 @Put it in r0
    endloop:
        cmp r0,#10
        bhs loop @while (r0 >=10)
    pop {r4,r5,r6,pc} @Return

Testing script in C:
#include <stdio.h>
unsigned long long anastasiya(unsigned,unsigned,unsigned);

int main(void) {
    unsigned x,y,op;
    printf("Enter first operand, second operand, and 0 for addition or 1 for multiplication.\n");
    scanf("%u%u%u",&x,&y,&op);
    unsigned long long res = anastasiya(x,y,op);
    printf("Result = %u, steps = %u\n",(unsigned)res ,(unsigned)(res >> 32));
}

R, 175 167 164 140 134 127 126 119 bytes
function(G,S,D){i=1;O=switch(S,"+"=sum,prod);x=O(G,D);while(x>9){i=i+1;x=O(strtoi(strsplit(paste(x),"")[[1]]))};c(x,i)}

Ungolfed :
f=function(G,S,D) #The function takes : the left operand, the operation symbol (between quote marks)
                  #and then the right operand
i=1               #That's the counter

O=switch(S,"+"=sum,prod)     #`O` takes the value `sum` if `S` matches `+`, `prod`
                             #(which is the next agument) if not.

x=O(G,D)                     #Does the first operation

while(nchar(x)>1)                 #While the number of character of the result
                                  #of the operation is not of length 1, i.e., an integer :

    i=i+1                                    #Increase the counter
    x=O(strtoi(strsplit(paste(x),"")[[1]]))  #Apply the operation `O` to the first operation and
                                             #the eventual subsequent ones

c(x,i)                                 #Outputs the result and the counter

ifelse is back ! Yeah !
Nop
Usage :
Special addition
> f(31,"+",81)
[1] 4 2

Special multiplication
> f(136,"*",2356)
[1] 0 2

Thanks a lot to @plannapus for golfing out 24 bytes !
-7 bytes thanks to a good idea from @Vlo !

Yes, please do add explanations since I love R! This is my second language after VBA. (+1)

@Anastasiya-Romanova 秀 : Done !

@plannapus : Really nice ! Thanks a lot !

@Frédéric nice use of strtoi! 4 more bytes are you have me beaten.

@plannapus : I'm trying, I'm trying ! :D

It might be possible to overload Ops and save some bytes? That would cover + and * in one go, but the input has to be classed.

Can save some money with while(x>9)

@Vlo : Brilliant !

If you change the input to use 1 to represent (+) and 2 to represent (*), then you can have switch(S,sum,prod), saving 4 bytes. I think this is acceptable as the specification says you can have input in whatever format you like. Additionally, prod() is equivalent to *(), so you can save another byte by having switch(S,sum,*).

Looks like you can further golf off a byte by including the definition of O within the assignment of x in the first operation: x=(O=switch(S,sum,`*`))(G,D);.

Okay, one more, I promise. Since T is not a reserved variable name, it can be redefined at will, which means we can use it in place of i. So i=1; can be removed (since T is already TRUE which is the same as 1), and i=i+1; and c(i,x) replaced with T=T+1; and c(T,x), thus saving four bytes. Yes, it's a terrible abuse!

Pyth, 16
eJ.uvjhQ`N.vQ)lJ

Takes input like "+ 123 12" for addition, and "* 123 12" for multiplication. Outputs like result<linefeed>steps.
Try it here, or run a Test Suite, but note that this relies on eval, so only the addition variant will work in the online interpreter. Multiplication works correctly with the offline interpreter.
This uses the cumulative reduction function to create a list of intermediate results, so for "+ 351 14568" we get [14919, 24, 6]. This works because single digit numbers are a fixed point of the Anastasiya addition and multiplication. Then we just get the last element of the array as well as the length of the array.
This will work for arbitrarily large numbers, at least until you run out of memory.

Jelly, 11 10 bytes
Dj⁹VµÐĿḊĖṪ

Input is a pair of numbers and either + or ×.
Try it online! or verify all test cases.
How it works
Dj⁹VµÐĿḊĖṪ  Main link. Left argument: [x, y] (integers). Right argument: + or ×

    µÐĿ     Repeatedly execute the chain to the left, initially with argument
            [x, y], then with the previous return value. Stop when the results are
            no longer unique, and return the array of all intermediate results.
D           Decimal; convert the integers [x, y] or the return value z to base 10.
 j⁹         Join, separating by the link's right argument, i.e., '+' or '×'.
   V        Evaluate the result. This casts the previous return value to string,
            so, e.g., [8, 1, '+', 3, 1] becomes "81+31" before evaluation.
       Ḋ    Dequeue; discard the first intermediate result, i.e., [x, y].
        Ė   Enumerate; prefix each integer in the array with its 1-based index.
         Ṫ  Tail; extract the last index-value pair.

05AB1E, 20 15 bytes
[¼¹iOëP}Dg#S]¾‚

Explanation
[       Dg# ]    # loop until number is single digit
 ¼               # increase counter
  ¹iO            # if operation is addition, sum list
     ëP}         # else take product of list
           S     # split into a list of digits
             ¾‚  # pair final number with counter and output

Operator is 1 for addition, 0 for multiplication.
Try it online

Thanks for the answer, (+1). Can it handle large number inputs?

@Anastasiya-Romanova秀 I don't see a reason why not. Do you have an example?

Your program's been tested for that kind of inputs, so it perfects :)

Jelly, 17 bytes
+×⁵?µDSP⁵?$ÐĿµL;Ṫ

Try it online!
Given arguments like x y 1, this computes the Anastasiya sum x (+) y.
Given arguments like x y 0, this computes the Anastasiya product x (*) y.
Output is given as [number of steps, result].

Thanks for the answer, but your program output doesn't contain the number of steps required part? Am I missing something here?

Octave, 85 bytes MATLAB, 123, 114, 105, 94 bytes
Decided to translate this to Octace, to take advantage of  the direct indexing, and incrementing capabilitites. Takes the input on the form: f(a,operator), where a = [number1, number2],  and operator==1 gives the product, and operator==2 gives the sum.
function[x,i]=f(a,o)
g={@prod,@sum}{o};x=g(a);i=1;while(x=g(num2str(x)-48))>9;i++;end

Explanations:
g={@prod,@sum}{o} : Chooses the appropriate function, product or sum and assigns it to g
x=g(a) takes the sum or product of the inputs
i=1; ... i++ : Incrementer to count the number of steps
while(x=g(num2str(x)-48))>9;
          num2str(x)-48)     % turns a number 123 into an array [1 2 3].
        g(num2str(x)-48))    % Takes the sum or product of the array
      x=g(num2str(x)-48))    % Assign that value to the variable x
      x=g(num2str(x)-48))>9  % Checks if x > 9, continue looping if yes

Removed two newlines, a space, and placed both input numbers in a vector instead of separate arguments. This saved 9 bytes, thanks to pajonk!
Removed k=@(x)... to save another 11 bytes thanks to beaker =) Finally, translated the whole thing to Octave to save another 9 bytes...

Java, 164 159 146 bytes
int[]p(int t,int m,String[]d){int r=m;for(String i:d){int x=Integer.decode(i);r=m<1?r+x:r*x;}return r>9?p(++t,m,(r+"").split("")):new int[]{r,t};}

First argument is just the counter, always 0
Second argument is method, 0 for ADD and 1 for MULTIPLY.
Third argument is an array of Strings, which contains the values to add/multiply.
Ungolfed
public static int[] p(int t, int m, String[] d) {
    int r = m;
    for (String i : d) {
        int x = Integer.decode(i);
        r = m < 1 ? r + x : r * x;
    }
    return (r + "").length() > 1 ? p(++t, m, (r + "").split("")) : new int[]{r, t};
}

thanks to @Kevin Cruijssen for cutting a few bytes.
thanks to @milk for shaving 5 bytes.
Test Program
public static final int ADD = 0;
public static final int MULTIPLY = 1;

public static void main(String[] args) {
    System.out.println(Arrays.toString(p(0, ADD, new String[]{"12", "123"}))); //9
    System.out.println(Arrays.toString(p(0, MULTIPLY, new String[]{"12", "123"}))); //6
}

public static int[] p(int t, int m, String[] d) {
    int r = m;
    for (String i : d) {
        int x = Integer.decode(i);
        r = m < 1 ? r + x : r * x;
    }
    return (r + "").length() > 1 ? p(++t, m, (r + "").split("")) : new int[]{r, t};
}

Nice, shorter than my Java answer. However, you're also supposed to print the steps as well as the answer which is currently missing from your answer..

@KevinCruijssen Ahh. That's boring.. I'll try fix that now.

Btw, you can golf your current answer a bit. m==0 can be m<1, and Integer.parseInt can be Integer.decode.

I don't use Java much, but do you need that j var at the end? Inlining (r+"") twice looks like it would shave a few bytes.

@milk Well spotted.

Hmmm... I guess I unwittingly approved this by suggesting @todeale's edit include changes to the byte count in review. Please double the change carefully.

Can we not change my posts in future? If you want to suggest an edit do so in the comments.

Comment by Todeale: "Changing (r + "").length() > 1 by r > 9 saved a few bytes. I'm sorry I couldn't comment because I don't have enough reputation."

R, 130 124 chars
A somewhat different approach from @Frédéric's:
f=function(a,f,b){b=c(a,b);n=1;while((m<-nchar(d<-switch(f,'(+)'=sum,prod)(b)))>1){b=d%%10^(1:m)%/%10^(1:m-1);n=n+1};c(d,n)}

Indented, with newlines:
f=function(a,f,b){
    b=c(a,b) # Take both numbers
    n=1 #Counter
    while((m<-nchar(d<-switch(f,'(+)'=sum,prod)(b)))>1){
#My own special digit splitter! (d is the result and m is the nb of char of d)
        b=d%%10^(1:m)%/%10^(1:m-1)
        n=n+1
    }
    c(d,n) #Print results
    }

Line 4 probably needs more explanations:
switch(f,'(+)'=sum,prod) #pick which operator to use
switch(f,'(+)'=sum,prod)(b) # apply it to b
d<-switch(f,'(+)'=sum,prod)(b) #Saves the result in d
nchar(d<-switch(f,'(+)'=sum,prod)(b))#Measures the number of character of d
m<-nchar(d<-switch(f,'(+)'=sum,prod)(b)) #Saves it in m
(m<-nchar(d<-switch(f,'(+)'=sum,prod)(b)))>1 #Checks if it is more than 1

Test cases:
> f(12,"(+)",123)
[1] 9 2
> f(12,"(*)",123)
[1] 6 5
> f(351,"(+)",14568)
[1] 6 3

Quite unfortunate you came late with this answer, but you have my upvote. Thanks for creating this in R.

Why unfortunate?

Because if you had come first, then you'd have got more upvotes

@Anastasiya-Romanova秀 Fair enough :)

Bonus points for having f be both the function name and one of its arguments :)

I wrote a solution but it turned out to be 130+. The bottleneck was the strsplit part as a Reduce approach is more byte efficient than a switch solution. So by replacing the inefficient splitter with your splitter, we can golf it down even further. f=function(A,F,B){r=Reduce;x=r(F,A,B);y=1;while(x>9){m=nchar(x);x=r(F,x%%10^(1:m)%/%10^(1:m-1));y=y+1};cat(x,y)} `112 bytes

@Vlo That's a cool and original solution (i never think of Reduce!), you should write it down as a new answer!

R, 110 bytes
Using @plannapus' splitter.
function(A,F,B){r=Reduce;x=r(F,A,B);y=1;while(x>9){m=nchar(x);x=r(F,x%%10^(1:m)%/%10^(1:m-1));y=y+1};cat(x,y)}
f=function(A,F,B){
  r=Reduce                                  # Shortcut for Reduce
  x=r(F,A,B)                                # A operator B
  y=1                                       # Initiate counter
  while(x>9)                                # If number of digits > 2, or number > 9
  {m=nchar(x)                               # Count number of digits
    x=r(F,x%%10^(1:m)%/%10^(1:m-1))         # @plannapus's splitter, then feed into the A operator B operator C, etc while condition true
    y=y+1}                                  # Increment counter
  cat(x,y)}                                 # Print

Output
> f(136,"*",2356)
0 2
> f(31,"+",81)
4 2
> f(2,"+",3)
5 1
> (function(A,F,B){r=Reduce;x=r(F,A,B);y=1;while(x>9){m=nchar(x);x=r(F,x%%10^(1:m)%/%10^(1:m-1));y=y+1};cat(x,y)})(21,"*",111)
8 3

edit: I can't count.

R is fantastic because allowing us to shorten its function, something that's valuable in golfing. (+1)

Python, 160 146 129 bytes
def r(s):
 n=str(eval(s));c=0
 while n[1:]:exec("n=str(reduce(lambda a,b:a%sb,map(int,list(n))))"%"*+"["+"in s]);c+=1
 return n,c

Will post an explanation soon.
Input is in the form 12+12 or 5*35 (with normal + and * signs), and assumes that those are the only two operators.
It can handle number inputs as large as your computer's memory allows.
I'm almost certainly confident that this can be further.
EDIT: 16 31 bytes saved thanks to @Copper.

Thanks for the answer, (+1). Can it handle large number inputs?

@Anastasiya-Romanova秀 Uhmmm... I'm fairly sure they can. Can you give me examples of large inputs? I'll try and calculate from those.

Maybe: 3218753647208435810122106*29349566754?

@Anastasiya-Romanova秀 Yeah, it worked in ~0.5 seconds, didn't properly time it.

You can change "+" if "+" in s else "*" to "*+"["+"in s], and then instead of assigning it to t, just add it inline in the exec call.

You can also change [n,c] to n,c, [int(x) for x in list(n)] to map(int,list(n)), and "n=...a,b"+t+"b,..." to "n=...a,b%sb,..."%t.

Finally: while len(n)!=1 can be changed to while n[1:].

@Copper You, sir, are a legend. Thanks for all the tips!

you can change ["+" in s] to ["+"in s], just like @Copper originally suggested (the space in front of in can be omitted)..

Clojure 126 bytes
(defn f [o a b] (loop [n (o a b) c 1] (if (< n 10) [n c] (recur (reduce #(o %1 %2) (map #(- (int %) 48) (str n))) (inc c)))))

Function is called like so:
(f + 81 31)

Here is the code ungolfed:
(defn f [o a b]
  (loop [n (o a b) c 1]
    (if (< n 10)
      [n c]
      (recur (reduce #(o %1 %2)
                     (map #(- (int %) 48) (str n)))
             (inc c)))))

(def test-cases [[+ 81 31]
                 [+ 351 14568]
                 [* 21 111]
                 [* 136 2356]])

(map #(apply f %) test-cases)
;;=> ([4 2] [6 3] [8 3] [0 2])

Bear in mind that Clojure is still new to me, so this is likely not the best solution. The challenge was fun all the same. Additionally, the code ran with very large numbers without any difficulty.

This is very late, but you can reduces most of the spaces in there.

Groovy, 102 bytes
def p,e,r;p={t,m,d->e=d*.toInteger();r=m<1?e.sum():e.inject{a,b->a*b};r>9?p(++t,m,""+r as List):[r,t]}

Degolfed
def p,e,r
p = { t, m, d ->
    e = d*.toInteger()
    r = (
            m<1
                ? e.sum()
                : e.inject { a, b -> a * b }
        )
    r > 9
        ? p(++t, m, "" + r as List)
        : [r,t]
}

Explanation
Based on @Sean Bean 's excellent solution for Java.

p: The closure (function, lambda, whatever) that implements the solution
t: The current call depth (number of iterations), p should always be invoked with t=1
m: The operation to perform, 0 for "add", 1 for "multiply"
d: The list of operands, each operand is a String object
e: The elements of d, each converted to an Integer
r: The sum or product of e, depending on the operation m
result statement, starting with r > 9:

If multi-digit (r > 9), reinvoke, incrementing depth t and converting r to a list of digit strings (and return result).
If single-digit, return r and t as a list.

Test Program
final ADD = 0
final MULTIPLY = 1
println p(1, ADD, ["12", "123"]) //9, 2
println p(1, MULTIPLY, ["12", "123"]) //6, 5
println p(1, ADD, ["2", "3"]) //5, 1

Results
[9, 2]
[6, 5]
[5, 1]

Haskell, 76 70 bytes
 (x#y)f=until(<[10])(\[s,i]->[foldr(f.read.pure)0$show s,i+1])[f x y,1]

Returns a two element list with the result and number of steps. Works for arbitrary large numbers. Usage example: (351#14568)(+) -> [6,3].
Edit: Thanks to @BlackCap for 6 bytes.

You can replace (-48+).fromEnum with read.pure

Perl 6 53 bytes
{$/=(&^b($^a,$^c),{[[&b]] .comb}...10>*);$/[*-1],+$/}

Since ( 12, &[+], 123 ) is acceptable for the input, I can get it down to 53 bytes.
( &[+] is short for &infix:<+> which is a "reverence" to the numeric infix addition operator )
If the second argument had to be a string (+) it would be 87 bytes
{my&b=::("&infix:<$^b.substr(1,1)>");$/=(b($^a,$^c),{[[&b]] .comb}...10>*);$/[*-1],+$/}

Explanation:
# bare block lambda with 3 parameters declared using placeholder syntax
{
  # store list into ｢$/｣
  # ( used ｢$/｣ so that I don't have to declare a variable )
  $/ = (

    # declare second placeholder parameter, and call it
    &^b(
      # with the first and third placeholder parameters
      $^a, $^c
    ),

    # bare block lambda with implicit parameter ｢$_｣
    {
      # list reduce using the second parameter from outer block
      [[&b]]

      # a list of the digits of ｢$_｣ (implicit method call)
      .comb
    }

    # keep doing that until
    ...

    # it produces something smaller than 10
    # ( Whatever lambda )
    10 > *
  );

  # returns

  # final result ( last value from list )
  $/[ * - 1 ],
  # and count of values in list
  +$/
}

Test:
#! /usr/bin/env perl6
use v6.c;
use Test;

my &anastasiya-math = {$/=(&^b($^a,$^c),{[[&b]] .comb}...10>*);$/[*-1],+$/}

my @test = (
  (  81, &[+], 31    ) => (4, 2),
  ( 351, &[+], 14568 ) => (6, 3),
  (  21, &[*], 111   ) => (8, 3),
  ( 136, &[*], 2356  ) => (0, 2),
);

plan +@test;

for @test -> $_ ( :key(@input), :value(@expected) ) {
  cmp-ok anastasiya-math(|@input), &[»==«], @expected;
}

Normal Usage:
# override built-in Bag operator ｢(+)｣ in current lexical scope
my &infix:<(+)> = &anastasiya-math.assuming: *, &[+], *;

# add a new operator
my &infix:<(*)> = &anastasiya-math.assuming: *, &[*], *;

say 12 (+) 123; # (9 2)
say 12 (*) 123; # (6 5)

Python 2, 107 97 bytes
g=lambda x,o,i=1:x<10and[x,i]or g(eval(o.join(`x`)),o,i+1)
lambda a,o,b:g(eval('%s'*3%(a,o,b)),o)

An anonymous function that takes input via argument of a first operand a, an operator o ('+' or '*') and a second operand b, and returns a list of the form [result, steps].
How it works
The anonymous function creates a string by concatenating the operands with the operator between them, and then evaluates it; this is the first step described in the question. Then, this value and the operator are passed to the recursive function g. Here, a counter i, which is incremented for every recursive call, is used. If the input is less than 10, a single digit must have been reached, so this and i are returned. If not, the input is converted to a string and each character in this string is joined with the operator, giving the desired calculation, which is then evaluated and passed to the function recursively.
Try it on Ideone

(+1) while waiting the explanation :)

R, 91 bytes
Using @Vlo's code, which makes use of @plannapus's splitter, and some ideas I generated while golfing @Frédéric's answer, this is the shortest R answer yet. (An unusually large number of R answers here today...)
function(A,F,B){x=F(A,B);while(x>9){m=nchar(x);x=F(x%%10^(1:m)%/%10^(1:m-1));T=T+1};c(x,T)}

Crucially, this requires that the input for the operator be either sum for (+) or prod for (*). Under the rules of the challenge, this seems to be okay.
With indentation:
function(A,F,B){
  x=F(A,B);
  while(x>9){
    m=nchar(x);
    x=F(x%%10^(1:m)%/%10^(1:m-1));
    T=T+1
  };
  c(x,T)
}

Main differences from @Vlo's answer are:

Instead of using Reduce, we rely on the input argument being a function, and just call it explicitly. (Yay for functions being first-class objects!)
Instead of initializing a new variable as our counter, we abuse R's builtins and use T, which evaluates to TRUE (aka 1), but since it's not a reserved variable we can modify it. Thus T+T is 2. So we use that as our counter.
Instead of cating the output, we just return it as a vector with c. As well as saving two bytes, the fact that the output is forced into a vector ensures that T is of class numeric. If we use cat, and T hasn't been incremented, then we get erroneous output like 1 TRUE.

you can restructure the while loop as follows, changing F to be something else to avoid name conflicts: function(A,O,B){x=O(A,B);while({F=F+1;x>9})x=O(x%/%10^(1:nchar(x)-1)%%10;c(x,F)}}. It's amazing how many R golfing tricks we've come up with in the last few years :)

@Giuseppe Nice restructuring! I can't find the meta consensus at the moment, but I'm reasonably confident that using the T and F counter trick within a function is actually invalid, as it means that the function can only be called once. So this answer (and several of my others!) are invalid, unless there's an explicit rm(T) at the end. I'm gonna keep looking for that meta post so I can be sure I didn't just dream it up.

I believe that the T and F trick is perfectly valid as long as you don't modify T or F in the global environment. for instance, f=function(){T=T+1;T} consistently returns 2. I think this is the meta post to which you refer.

@Giuseppe Ah yes, you're right on both counts. Thanks!

Perl, 38 bytes
Includes +2 for -ap
Run with the input on STDIN and spaces around the operator:
amath.pl <<< "12 + 123"
amath.pl <<< "12 * 123"

The output is digit and steps separated by +A
amath.pl:
#!/usr/bin/perl -ap
1while++$\,$_=eval."+A",s/\B/$F[1]/g

If outputting the steps in unary is ok this 35 byte version works better:
#!/usr/bin/perl -lap
1while$\.=1,$_=eval,s/\B/$F[1]/g

Java 7, 203 195 192 bytes
int c=1;String c(long a,long b,int o){return p(((o<1?a+b:a*b)+"",o)+","+c;}long p(String n,int o){long x=o,q;for(String s:n.split("")){q=new Long(s);x=o<1?x+q:x*q}c++;return x<10?x:p(x+"",o);}

It uses long (maximum value of 263-1). If it would use int instead (maximum value of 231-1) it would only be 1 byte less (191 bytes):
int c=1;String c(int a,int b,int o){return p(((o<1?a+b:a*b)+"",o)+","+c;}int p(String n,int o){int x=o,q;for(String s:n.split("")){q=new Integer(s);x=o<1?x+q:x*q}c++;return x<10?x:p(x+"",o);}

It can most likely be golfed a bit more. Having to print the steps as well as the answer for both operators takes some bytes, though..
Uses 0 (for (+)) and 1 (for (*)).
Ungolfed & test code:
Try it here.
class Main{
  static int c = 1;
  static String c(long a, long b, int o){
    return p((o < 1 ? a+b : a*b) + "", o) + "," + c;
  }

  static long p(String n, int o){
    long x = o,
         q;
    for(String s : n.split("")){
      q = new Long(s);
      x = o < 1
           ? x + q
           : x * q;
    }
    c++;
    return x < 10
            ? x
            : p(x+"", o);
  }

  public static void main(String[] a){
    System.out.println(c(81, 31, true));
    c = 1;
    System.out.println(c(351, 14568, true));
    c = 1;
    System.out.println(c(21, 111, false));
    c = 1;
    System.out.println(c(136, 2356, false));
  }
}

Output:
4,2
6,3
8,3
0,2

Mathematica, 105 94 bytes
Code.
{x,y}=(c=0;f//.a_:>(c++;t=o@@IntegerDigits@a);{t,c})&/.{{f->#1+#2,o->Plus},{f->#1#2,o->Times}}

Usage.
x[81, 31]
(* {4, 2} *)

x[351, 14568]
(* {6, 3} *)

y[21, 111]
(* {8, 3} *)

y[136, 2356]
(* {0, 2} *)

Explanation.
The two functions x (for (+)) and y (for (*)) are created at the same time by replacing the parameters f and o in
(c = 0;
 f //. a_ :> (c++; t = o@@ IntegerDigits@a);
 {t, c}
)&

with their appropriate values. For x, f becomes #1 + #2 and o becomes Plus; for y, they respectively become #1 #2 and Times. Rewriting the function x for the last part of the explanation:
x = (
  c = 0;
  #1 + #2 //. a_ :> (c++; t = Plus@@IntegerDigits@a);
  {t, c}
) &;

(* The symbol //. stands for ReplaceRepeated.
   The rule a_ :> (c++; t = Plus@@IntegerDigits@a) is applied until the result no longer
changed. Specifically, the rule increments the counter of 1 at each step (this is c++),
then takes the sum of the digits of the previous result (this is Plus@@IntegerDigits@a).
The rule stops to apply when the variable t is less than 10. We return the final result and
the number of steps with {t, c}. *)

Ruby, 55 bytes
Recursive call. Used to be very different from @edc65's JavaScript answer but as I optimized it eventually became a direct port developed almost independently from their answer, minus one final optimization involving checking the eval'ed result instead of the length of the list of operands being passed in, which allowed me to surpass their byte count.
Input is a string representing the operator, and an array containing the operands.
Try it online.
f=->o,x,i=1{y=eval x*o;y>9?f[o,y.to_s.chars,i+1]:[y,i]}

The result is correct, but the number of steps required to obtain a single digit value is incorrect. Could you rectify your code?

@Anastasiya-Romanova秀 ah, you're right. My old logic required it to start from i=0 and I sort of forgot when refactoring.


text:
Together Everyone Achieves More
(related: one, two, three)
An acrostic is a style of poem/writing where the beginning character of each line, when read vertically, also produces a word or message. For example,
Together
Everyone
Achieves
More

also spells out the word TEAM when the first column is read vertically.
Acrostics are a subset of mesostics, where the vertical word can be anywhere in the horizontal words. For example, the TEAM one above could also be written as a mesostic as follows
   togeTher
everyonE
       Achieves
       More

along with several other variations.
The challenge here will be to produce an acrostic or mesostic from a given list of input words.
Input

A list of words in any any suitable format.
The list will only contain words made from lowercase [a-z].
The list is guaranteed to form an acrostic or a mesostic (no need to handle bogus input).
One of the words in the input will form the vertical word, while the rest make the horizontal words - part of the challenge here is to find the appropriate vertical word, so it cannot be taken separately.

Output

The ASCII-art acrostic or mesostic formed from the input words, written to STDOUT or returned, in any reasonable format.
The corresponding vertical word must be capitalized (as in the examples).
Leading spaces to get the vertical word to line up appropriately are required. Trailing spaces, and leading/trailing newlines are optional. Extra leading spaces are fine as well, so long as the words align correctly.
If both an acrostic and mesostic are possible, output only the acrostic.
If more than one acrostic/mesostic is possible, your code can output any or all of them.

Rules

Either a full program or a function are acceptable.
Standard loopholes are forbidden.
This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.

Examples
['together', 'team', 'everyone', 'achieves', 'more']
Together
Everyone
Achieves
More

['aaa', 'aaa', 'aaa', 'aaa']
Aaa
Aaa
Aaa
# One output, or multiple (of the same) output is allowed

['aaa', 'aaa', 'aab', 'baa']
Aaa
Aaa
Baa
# This is the only allowed output, since others would be mesostic, which are lower priority

['live', 'every', 'love', 'very', 'ohio']
Live
Ohio
Very
Every
# Note that 'live' couldn't be the vertical word since then it would be a mesostic, which is lower priority output

['cow', 'of', 'fox']
cOw
 Fox
# A shorter mesostic test case

['late', 'ballroom', 'anvil', 'to', 'head']
anviL
   bAllroom
    To
   hEad

It seems that in the cases where an acrostic is produced, the list will be in that order?

Can you have a shorter mesostic testcase?

Are extra leading spaces allowed?

It doesn't say that the input is guaranteed to be sorted correctly, but judging from the test cases, they are. Are they?

@aross They aren't (e.g. the live ohio very every test case, or the last one).

Dear god. I'll pass then

@Pietu1998 Sure, that's fine -- the important thing is that the words are lined up. I'll edit in that clarification.

Pyth, 52 49 47 46 bytes
jm++*;-lsQhAd<HGr>HG4hhMDfhhShMTm.b,xNYNtdhd.p

Try it online.
This is probably very golfable. It prints a bunch of leading spaces.

Brachylog, 145 bytes
p~c[A:B:C],Bl1,A:CcP@pz:cahgB,P:1a~@nw|lL,?:laot:" "rjg:Ljb:sa:?z:cap~c[A:B:C],Bl1,A:Cc@pz:caZ:LmgB,Zl-yM,Z:M:Lz:2az:ca~@nw
bB,?h@u:Bc
b#=,?h@u|h

Try it online!
(Takes half a minute, so be patient.)

Looks like this took some effort to write :) Very nice!

@TimmyD Fixed, thanks.

JavaScript (ES6), 255 263 269 286
Edit 17 bytes saved as arbitrary number of leading spaces is allowed
Edit2 some shuffling, 6 byte saved
Edit3 return a list of string instead of a single string with newlines (OP comment to feersum's answer), 8 more bytes saved
For each word in the input list, I use a recursive DFS to find all possibile mesostics/acrostics. Each one is stored as an array with word and target letter position inside the word. Every result found is saved in global result array at position 1 (if it's an acrostic) or 0 if it's a mesostic.
After the complete scan for all words, I get the result at last position in array and build and return its ascii art rapresentation.
l=>(l.map((w,i)=>(r=(p,v,i,a)=>(l[i]='.',w[p]?l.map((v,i)=>~(j=v.search(w[p]))&&r(p+1,v,i,a|j,m[p]=[j,v])):l[p+1]?0:s[+!a]=[...m],l[i]=v))(0,w,i,m=[]),s=[]),m=s.pop(),m.map(([j,v])=>' '.repeat((l+0).length-j)+v.slice(0,j)+v[j].toUpperCase()+v.slice(j+1)))

Less golfed
f=l=>(
  l.map((w,i)=>
    // r: recursive DFS function
    // defined here as it uses local w variable
    (r = (p,v,i,a) => (
     l[i] = '.'
     , w[p]
     ? l.map(
       (v,i) => ~(j=v.search(w[p])) &&
                r(p+1, v, i, a|j, m[p] = [j,v])

     )
     : l[p+1] ? 0 // invalid if there are still unused words
              : s[+!a]=[...m] // a is 0 if acrostic
     , l[i] = v)
    )(0, w, i, m=[])
  , s=[]),
  m = s.pop(), // get last result
  // m.map(([j]) => o = o<j ? j : o, o=0), // find offset for alignment
  // no need to find the optimal offset as leading blanks are allowed
  m.map(([j,v]) => ' '.repeat((l+0).length-j)
                   + v.slice(0,j)
                   + v[j].toUpperCase()
                   + v.slice(j+1)
  )
)

Test

f=l=>(l.map((w,i)=>(r=(p,v,i,a)=>(l[i]='.',w[p]?l.map((v,i)=>~(j=v.search(w[p]))&&r(p+1,v,i,a|j,m[p]=[j,v])):l[p+1]?0:s[+!a]=[...m],l[i]=v))(0,w,i,m=[]),s=[]),m=s.pop(),m.map(([j,v])=>' '.repeat((l+0).length-j)+v.slice(0,j)+v[j].toUpperCase()+v.slice(j+1)))

console.log=x=>O.textContent+=x+'\n\n'

;[
 ['together', 'team', 'everyone', 'achieves', 'more']
,['aaa', 'aaa', 'aaa', 'aaa']
,['aaa', 'aaa', 'aab', 'baa']
,['live', 'every', 'love', 'very', 'ohio']
,['cow', 'of', 'fox']
,['late', 'ballroom', 'anvil', 'to', 'head']
].forEach(l=>console.log(f(l).join`\n`))

Mathematica 10.0, 139 bytes
An unnamed function returning a list of lines:
Sort[{q=Max[p=Min/@Position@@@({z={##2},#})],Array[" "&,q-#2]<>ToUpperCase~MapAt~##&@@@({z,p})}&@@@Permutations@Characters@#][[1,2]]&

Example usage:

In[144]:= f = Sort[{q=Max[p=Min/@Position@@@({z={##2},#})],Array[" "&,q-#2]ToUpperCase~MapAt~##&@@@({z,p})}&@@@Permutations@Characters@#][[1,2]]&;

In[145]:= f @ {"late","ballroom","anvil","to","head"} // Column

 ... several pages of warnings ...

Out[145]= baLlroom
            Anvil
            To
           hEad

I'm looking for suggestions on better ways to do the capitalization. I found a very nice function MapAt for capitalizing the letter in the string.

Sure, functions can return multiline strings as a list of strings.

Perl6, 287 277 269 bytes
my @w=$*IN.words;my ($q,$r)=gather for ^@w {my @v=@w.rotate($_);my \d=@v.shift;for @v.permutations {my @o=flat($_ Z d.comb).map:{$^a.index: $^b};take $_,@o if @o>>.defined.all}}.sort(*[1].sum)[0];for @$q Z @$r ->(\a,\b){say " "x($r.max -b)~a.substr(0,b)~a.substr(b).tc}

Haskell, 214 206 204 202 bytes
import Data.List
z=zipWith
h i j t|(u,v:w)<-splitAt j t=([1..sum i-j]>>" ")++u++toEnum(fromEnum v-32):w
f x=uncurry(z=<<h)$sort[(head<$>z elemIndices w l,l)|w:l<-permutations x,(True<$w)==z elem w l]!!0

Returns a list of space padded strings, e.g. f ["late","ballroom","anvil","to","head"] -> [" baLlroom","   Anvil","   To","  hEad"] or more display friendly:
*Main> mapM_ putStrLn $ f ["late", "ballroom", "anvil", "to", "head"]
 baLlroom
   Anvil
   To
  hEad

f selects the words that are written horizontally together with a list of offsets. h pads each word according to the corresponding offset and inserts the uppercase letter. In detail:
                permutations x       -- for each permutation of the input list x
         w:l<-                       -- bind w to the first word and l to the rest
             (True<$w)==z elem w l   -- keep it if the list of other words
                                     -- containing the next letter of w
                                     -- equals (length w) times True, i.e. we have
                                     -- as many matching letters as letters in w.
                                     -- This rules out combinations shortcut by zipWith

                                     -- for all the remaining w and l make a pair
         head<$>z elemIndices w l    -- the first element of the list of list of
                                     -- indices where the letter appears in the word
                                l    -- and l itself
   sort                              -- sort the pairs (all 0 indices, i.e. acrostics
                                     -- go first)
                               !!0   -- pick the first
                                     -- now we have a pair like
                                     -- ([2,0,0,1],["ballroom","anvil","to","head"])
 uncurry(z=<<h)                      -- loop over (index,word) and
                                     -- provide the third parameter for h

 h i j t                             -- h takes the list of indices and
                                     -- an index j and a word t
       (u,v:w)<-splitAt j t          -- split the word at the index and bind
                                     --   u: part before the split
                                     --   v: letter at the split
                                     --   w: part after the split
         [1..sum i-j]>>" "           -- the spaces to pad
           ++ u                      -- followed by u
           ++ toEnum(fromEnum v-32)  -- and uppercase v
           :                         -- and w

Python, 249 bytes
Probably still very golfable
from itertools import*;e=enumerate;lambda l:[[[' ']*(max(j for k,(j,c)in o[1:])-i)+l[k][:i]+[c.upper()]+l[k][i+1:]for k,(i,c)in o[1:]]for p in product(*[list(e(w))for w in l])for o in permutations(list(e(p)))if[c for k,(i,c)in o[1:]]==l[o[0][0]]][0]

Takes and returns a list of list of characters.
- e.g. "   bAllroom" is [' ',' ',' ','b','A','l','l','r','o','o','m']
Only ever returns the first result and checks in an order such that all the acrostics are checked first.
See all test cases printed in the display format on ideone

Here is a more readable functional form that does the same (except it returns the first result immediately rather than evaluating and then returning the first result):
from itertools import*
def f(l):
    for p in product(*[list(enumerate(w)) for w in l]):
        for o in permutations(list(enumerate(p))):
            if [c for k,(i,c) in o[1:]] == l[o[0][0]]:
                return [ [' '] * (max(j for k,(j,c) in o[1:]) - i)
                       + l[k][:i]
                       + [c.upper()]
                       + l[k][i+1:]
                       for k, (i, c) in o[1:]
                       ]

Perl 6, 177 bytes
->\a{for first({.[0] eq[~] .[1]»[1]},map |*,[Z] map {.[0]X [X] map {.comb[(^$_,$_,$_^..* for ^.chars)]},.[1..*]},a.permutations)[1] ->$/ {say [~] " "x a.comb-$0,|$0,$1.uc,|$2}}

Brute-force solution.
How it works
-> \a {
    for first({.[0] eq[~] .[1]»[1]},          # For the first valid candidate
            map |*, [Z]                       # among the transposed
            map {                             # lists of candidates
                .[0] X [X] map {
                    .comb[(^$_,$_,$_^..* for ^.chars)]
                }, .[1..*]
            },
            a.permutations                    # for all permutations of the input:
        )[1] ->$/ {
        say [~] " "x a.comb-$0,|$0,$1.uc,|$2  # Print the candidate as ASCII art.
    }
}

Each candidate looks like:
"of", (("c"),"o",("w")), ((),"f",("o","x"))

Transposing the list of lists of candidates is necessary to ensure that an acrostic, if it exists, is found before any mesostic.

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Steps of Permutation
Write a function which takes a set of integers and prints every permutation of the set, and the swap performed in between each step
Input
a set of integers, for example (0, 1, 2)
Output
the list of permutations and swaps in the format
(set)
(swap)
(set)
...
Test case
Input:
(3, 1, 5)

Output:
(3, 1, 5)
(3, 1)
(1, 3, 5)
(3, 5)
(1, 5, 3)
(1, 3)
(3, 5, 1)
(3, 5)
(5, 3, 1)
(3, 1)
(5, 1, 3)

Rules

You can format the set of numbers however you want.
You can do the swaps in any order
You can repeat permutations and swaps in order to get a new one
Your code doesn't have to actually perform the swaps, the output just needs to show what swap was made between your last output and your current one
Your code only needs to function for sets with 2 or more elements
The set you're given will have no repeating elements (e.g. (0, 1, 1, 2) is invalid)

This is code-golf, so shortest code wins!

Can we use randomness?

You mean just do a load of random swaps until you happen to achieve all permutations? Yes, but you have to be sure that all permutations have been printed

@Rod yes, I specified that this is allowed in the rules.

@Rod, oh sorry, no repeating elements. I'll edit to specify thanks

Welcome to PPCG! Nice first challenge. I would suggest editing the example so the elements don't get confused with the indices, like use set (3, 1, 4) or so -- reading it the first time I was very confused because the first swap 0,1 swapped the elements 0,1 but also the indices 0,1, but then the next swap didn't follow that pattern. I'll also point you to the Sandbox where you can post challenges and get feedback before posting them to the main site.

@TimmyD thanks for the suggestion, I have changed the example. I saw the link to the sandbox just after I posted this, I'll post there first from now on!

Hi, reading again the puzzle (after answering it :P) I am a bit confused about You can repeat permutations and swaps in order to get a **new one**. So, are there any invalid permutations?

The Steinhaus–Johnson–Trotter algorithm generates the minimum necessary sequence.

@Master_ex I didn't really mean anything by "a new one", sorry if it was confusing

Java, 449 426 bytes
import java.util.*;interface P{static Set s=new HashSet();static void main(String[]a){o(Arrays.toString(a));while(s.size()<n(a.length)){p(a);o(Arrays.toString(a));}}static<T>void o(T z){System.out.println(z);s.add(z);}static int n(int x){return x==1?1:x*n(x-1);}static void p(String[]a){Random r=new Random();int l=a.length,j=r.nextInt(l),i=r.nextInt(l);String t=a[j];a[j]=a[i];a[i]=t;System.out.println("("+a[j]+","+t+")");}}

Brute force approach. It keeps making random swaps until all the possible permutations have took place. It uses a Set of the string representation of the array in order to check how many different states have been generated. For n different integers there are n! = 1*2*3*..*n distinct permutations.
Update

Followed Kevin Cruijssen's suggestions to golf it a bit more.

Ungolfed:
import java.util.*;

interface P {

    static Set<String> s = new HashSet<>();

    static void main(String[] a) {
        // prints the original input
        o(Arrays.toString(a));
        while (s.size() < n(a.length)) {
            p(a);
            // prints the array after the swap
            o(Arrays.toString(a));
        }
    }

    static void o(String z) {
        System.out.println(z);
        // adds the string representation of the array to the HashSet
        s.add(z);
    }

    // method that calculates n!
    static int n(int x) {
        if (x == 1) {
            return 1;
        }
        return x * n(x - 1);
    }

    // makes a random swap and prints what the swap is
    static void p(String[] a) {
        Random r = new Random();
        int l = a.length, j = r.nextInt(l), i = r.nextInt(l);
        String t = a[j];
        a[j] = a[i];
        a[i] = t;
        System.out.println("(" + a[j] + "," + t + ")");
    }
}

Usage:
$ javac P.java
$ java P 1 2 3
[1, 2, 3]
(2,1)
[2, 1, 3]
(1,1)
[2, 1, 3]
(2,2)
[2, 1, 3]
(3,1)
[2, 3, 1]
(3,1)
[2, 1, 3]
(1,2)
[1, 2, 3]
(1,1)
[1, 2, 3]
(3,2)
[1, 3, 2]
(2,3)
[1, 2, 3]
(3,1)
[3, 2, 1]
(3,1)
[1, 2, 3]
(3,3)
[1, 2, 3]
(1,2)
[2, 1, 3]
(1,3)
[2, 3, 1]
(1,2)
[1, 3, 2]
(3,1)
[3, 1, 2]

As you can see there are many more swaps than the necessary minimum. But it seems to work :-D
As a bonus, it works with strings too, i.e.
$ java P 'one' 'two'
[one, two]
(two,one)
[two, one]

do you have an un-golfed version for us to take a look at your method using?

@Billyoyo: Added the un-golfed code. Nothing fancy there however :-)

You can golf it a bit. No need to fix warnings, so you can removed the Set declarations: Set s=new HashSet();. Your code in the method n can be a single return: static int n(int x){return x==1?1:x*n(x-1);}. And you can replace String z in your method o with a generic instead: static<T>void o(T z){System.out.println(z);s.add(z);}. All combined it would get down to 426 bytes.

Mathematica, 102 bytes
<<Combinatorica`
Riffle[#,BlockMap[Pick[#[[1]],#!=0&/@({1,-1}.#)]&,#,2,1]]&@*MinimumChangePermutations

Examples
//Column for a clearer result
%[{1,3,5}]//Column
(*
{1,3,5}
{1,3}
{3,1,5}
{3,5}
{5,1,3}
{5,1}
{1,5,3}
{1,3}
{3,5,1}
{3,5}
{5,3,1}
*)

JavaScript (ES6), 186 bytes

f=
a=>{console.log(a);d=a.slice().fill(-1);s=[...d.keys()];for(i=l=a.length;i;)s[k=(j=s.indexOf(--i))+d[i]]<i?(console.log(a[s[j]=s[k]],a[s[k]=i]),console.log(s.map(n=>a[n])),i=l):d[i]*=-1}
;
<input id=i><input type=button value=Go! onclick=f(i.value.split`,`)>

Note: I'm not sure how flexible the output format is, may be I could do this for 171 bytes:
a=>{console.log(a);d=a.slice().fill(-1);s=[...d.keys()];for(i=l=a.length;i;)s[k=(j=s.indexOf(--i))+d[i]]<i?console.log(a[s[j]=s[k]],a[s[k]=i],s.map(n=>a[n],i=l)):d[i]*=-1}

Works by performing the Steinhaus–Johnson–Trotter algorithm on the shuffle array of indices and translating back to the input array. Ungolfed:
function steps(array) {
    console.log(array); // initial row
    var d = a.slice().fill(-1); // direction values
    var s = [...a.keys()]; // initial (identity) shuffle
    var l = a.length;
    for (var i = l; i; ) { // start by trying to move the last element
        var j = s.indexOf(--i);
        var k = j + d[i]; // proposed exchange
        if (s[k] < i) { // only exchange with lower index (within bounds)
            console.log(a[s[k]],a[i]); // show values being exchanged
            s[j] = s[k];
            s[k] = i; // do the exchange on the shuffle
            console.log(s.map(n=>a[n])); // show the shuffled array
            i = l; // start from the last element again
        } else {
            d[i] *= -1; // next time, try moving it the other way
        } // --i above causes previous element to be tried
    } // until no movable elements can be found
}

Haskell - 135 bytes
p=permutations;f=filter
q(a:b:xs)=(\x->f(uncurry(/=)).zip x)a b:q(b:xs);q _=[]
l=head.f(all((==2).length).q).p.p
f=zip.l<*>map head.q.l

output:
> f [3,1,5]
[([3,1,5],(3,1)),([1,3,5],(3,5)),([1,5,3],(1,5)),([5,1,3],(1,3)),([5,3,1],(5,3))]

I am using the standard permutations function, which is not based on swaps, so I am taking the permutations of the permutations and finding one that happens to be a chain of swaps.

Ruby, 86 bytes
puts (2..(a=gets.scan(/\d+/).uniq).size).map{|i|a.permutation(i).map{|e|?(+e*", "+?)}}

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Compact a list of numbers
Inspired by Using LaTeX to compact a list of numbers, this challenge is to output a compact list of numbers, given a range, as follows:
Input: 1,2, 3,4,5,8,11, 12,13
Output: 1-5, 8, 11-13

Input: 20,21,45,56,75, 76,77,78
Output: 20-21, 45, 56, 75-78

Input: 4,5
Output: 4-5

Input is always comma separated numbers, sometimes with spacing, and output should be in the format above -- note space after the commas. There is no upper limit to the length of the input string.
Winner: Smallest in terms of bytes

This is a nice first challenge :). Sadly, apart from sorting the array, it's the exact same challenge as this.


text:
Non-palindromic numbers
A strictly non-palindromic number N is a number that isn't a palindrome in any base (in bases 2 to N-2).  These numbers are listed on OEIS
For example, the number 19 in base 2,3,4,5,6,...17 is: 10011,201,103,34,31,...12.  None of these representations is palindromic, so the number is strictly non-palindromic.
For this challenge, you need to return a truthy value if the number is non-palindromic, otherwise a falsy value.

You may assume the number passed to you is greater than or equal to 0.
Your program should work for values up to your languages' integer size.

Test cases:
Truthy:
0
1
2
3
4
6
11
19
47
53
79
103
389
997
1459

Falsy:
5
7
8
9
10
13
16
43
48
61
62
101
113
211
1361

This is a code-golf, so make your answers as short as possible!

Yes, I missed that. However, answers to this challenge could basically be reused by adding a result < n-2 check to them, I think.

C, 82 bytes
p(n,a,b,c,r){c=0;for(b=1;++b<n-2;c+=r==n)for(a=n,r=0;a>0;a/=b)r=r*b+a%b;return!c;}

Ideone it!
Explanation
This code reverses n in base b and stores in r:
for(a=n,r=0;a>0;a/=b)r=r*b+a%b;

The outer loop counts the number of bases from 2 to n-1 in which n is a palindrome.
If n is non-palindromic, the count would be 1 (n must be a palindrome in base n-1).

Have an upvote because I couldnt upvote the SILOS answer twice

@RohanJhunjhunwala Best reason to upvote ever.

@LeakyNun But a bit of serial voting...

Python 2, 71 bytes
n=input();b=1
while b<n-2:
 m=n;r=0;b+=1
 while m/(r!=n):r=r*b+m%b;m/=b

Output is via exit code, where 0 is truthy and 1 is falsy. Test it on Ideone.

S.I.L.O.S, 206 bytes
GOTO e
lbld
c - 1
GOTO c
lble
readIO
n = i
i - 3
b = i
b + 1
GOTO f
lbla
a = n
r = 0
lblb
m = a
m % b
r * b
r + m
a / b
if a b
r - n
r |
if r d
lblc
c + 1
i - 1
b - 1
lblf
if i a
c / c
c - 1
c |
printInt c

Try it online!
Port of my answer in C.

Have two upvotes one for each answer, because I can't upvote this twice

pheraps if you can write the code using one separation statement as "|" you can make advantage in write 1 char instead of 2 char of \13 \10 as \n as separation statement

@RosLuP Am I using \r\n as \n now?

i don't know in your sys, but i copy above program in a notepad, than save it: the lenght of that file is 241 not 206. so here it seems to me that \n is 2 chars not 1

@RosLuP Your notepad automatically converted EOLs to \r\n.

if not for gain one char for "\n", it is because i say it is good to use | as instruction separator (in the add of "\n") for readability reason... here in this place i can not indent that code nor use "\n" so i have no other thing to show or say.

@RosLuP The | is absolute.

abs is one function one use few time as the C or "|", but one separator is Always used every where so it is better choice one good instrution separator first than all other functions, operators, key words label etc. but this is just how i see the subject "instruction separators"

@RosLuP I am not understanding you. What is your native language?

Haskell, 75 68 bytes
(a!c)b|a<1=c|x<-c*b+mod a b=div a b!x$b
f n=all((/=n).(n!0))[2..n-2]

Jelly, 9 bytes
bRµ⁼"US<3

Try it online! or verify all test cases.
How it works
bRµ⁼"US<3  Main link. Argument: n

 R         Range; yield [1, ..., n].
b          Convert n to all bases between 1 and n, yielding a 2D array A>
  µ        Begin a new, monadic chain. Argument: A
     U     Upend; reverse the 1D arrays in A.
   ⁼"      Zipwith equal; yield 1 for each array that matches its inverse.
      S    Sum; add the resulting Booleans.
           If n > 1, the sum will be 2 if n is strictly non-palindromic (it is only
           a palindrome in bases 1 and n - 1), and greater than 2 otherwise.
           For 0 and 1, the sum will be 0 (sum of the empty array) and 1 (only a
           palindrome in base 1); both are less than 2.
       <3  Compare the sum with 3, yielding the desired Boolean.

Pyth, 12 10 bytes
Saved two bytes with Dennis' trick.
>3sm_IjQdS

Try it online!
Explanation:
         S (Q)   Get all the bases we need by building a list from 1 to Q
   m               For all bases d in the bases list:
      jQd           cast Q to base d as a list
    _I              and check to see if the list is palindromic (invariant on reversal)
                  Compile all the results back into a list
  s                Sum the results (a shorter form of any), gives 3 or more for palindromics
                    (2 is the usual because of bases 1 and Q-1)
>3                 And verify that the sum is greater than three to get non-palindromics

Mathematica, 58 43 bytes
!Or@@Table[#==#~IntegerReverse~i,{i,2,#-2}]&

TIL that #~IntegerReverse~i reverses the digits of the input when written in base i.

Perl6, 110 72 65
my &f={?all(map {{.reverse ne$_}(@(.polymod: $^a xx*))},2..$_-2)}

Couldn't use base since that's broken for any base above 36.
Previous attempts
my &a={$^a??flat($a%$^b,a($a div$b,$b))!!()};my &f=-> $n {?all(map {.reverse ne$_ given @(a($n,$_))},2..$n-2)}
my &f=->\n {?all(map {.reverse ne$_ given @(n.polymod: $_ xx*)},2..n-2)}

I managed to get it down to 59 bytes with my first try. Hint use .polymod with an infinite list of divisors. 1362.polymod: 226 xx *

Make that 53, and another hint {...} and -> $_ {...} are almost exactly the same. Also you don't have to store the lambda anywhere so you can remove the my &f =.

JavaScript (ES6), 83 bytes

f=(n,i=n-2,g=n=>n<i?[n]:[...g(n/i|0),n%i])=>i<2||`${a=g(n)}`!=a.reverse()&&f(n,i-1)
<input type=number oninput=o.textContent=f(this.value);><pre id=o>

Brachylog, 14 bytes
¬{⟦₆bk∋;?ḃ₍.↔}

Try it online!
Outputs through predicate success or failure, which prints true. or false. if run as a program.
¬{           }    It cannot be shown that
        ?         the input
       ; ḃ₍       in a base
      ∋           which is an element of
  ⟦₆              the range from 1 to the input - 1
    b             without its first element
     k            or its last element
           .      can be unified with both the output variable
            ↔     and its reverse.

Vyxal GRr, 58 bitsv2, 7.25 bytes
⇩Ḣƛ?τḂ⁼;a

Try it Online!
Bitstring:
1101010001101111001011011000000100110010001101101010011011

C, 77 bytes
h(n,b,k,z){for(z=0,k=n;z+=k%b,k/=b;z*=b);return b+3>n?1:z==n?0:h(n,++b,0,0);}

recursive exercise...i change (b+2>=n) with (b+3>n) whithout debugging...
main()
{int  v[]={0,1,2,3, 4, 6,11,19,47,53,79,103,389,997,1459},
  n[]={5,7,8,9,10,13,16,43,48,61,62,101,113,211,1361}, m;
    // 0 1 2 3  4  5  6  7  8  9 10  11  12  13   14
 for(m=0; m<15; ++m)
    printf("%u=%u\n", v[m], h(v[m],2,0,0));
 for(m=0; m<15; ++m)
    printf("%u=%u\n", n[m], h(n[m],2,0,0));
}

/*
 77
 0=1
 1=1
 2=1
 3=1
 4=1
 6=1
 11=1
 19=1
 47=1
 53=1
 79=1
 103=1
 389=1
 997=1
 1459=1
 5=0
 7=0
 8=0
 9=0
 10=0
 13=0
 16=0
 43=0
 48=0
 61=0
 62=0
 101=0
 113=0
 211=0
 1361=0
*/

Do not vandalize your posts.

C, 129 bytes
f(n,b,k,j){int a[99];for(b=2;b+2<n;++b){for(j=0,k=n;a[j]=k%b,k/=b;++j);for(;k<j&&a[k]==a[j];++k,--j);if(k>=j)return 0;}return 1;}

PHP, 68 bytes
for($b=$argn;--$b;)strrev($c=base_convert($argn,10,$b))!=$c?:die(1);

takes input from STDIN, exits with 1 for falsy, 0 for truthy. Run with -R.

If I see this right you can only solve n<39

APL(NARS), chars 47, bytes 94
{⍵≤4:1⋄∼∨/{⍵≡⌽⍵}¨{⍵{(⍺⍴⍨⌊1+⍺⍟⍵)⊤⍵}w}¨2..¯2+w←⍵}

where {(⍺⍴⍨⌊1+⍺⍟⍵)⊤⍵} would be the function conversion one positive omega
in digits number base alpha, and {⍵≡⌽⍵} would be the function check palindrome...
test:
  f←{⍵≤4:1⋄∼∨/{⍵≡⌽⍵}¨{⍵{(⍺⍴⍨⌊1+⍺⍟⍵)⊤⍵}w}¨2..¯2+w←⍵}
  f¨0 1 2 3 4 6 11 19 47 53 79 103 389 997 1459
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  f¨5 7 8 9 10 13 16 43 48 61 62 101 113 211 1361
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/