Random permutations by probability matrix
Your problem is not well-defined. As David Eisenstat notes in his comment, your matrix actually has to be bistochastic rather than just stochastic, since every convex combination of permutation matrices is bistochastic. Also, there could be many ways of representing a given bistochastic matrix as a convex combination of permutation matrices. As a simple example, the matrix $$\begin{bmatrix} 1/3 &amp; 1/3 &amp; 1/3 \\ 1/3 &amp; 1/3 &amp; 1/3 \\ 1/3 &amp; 1/3 &amp; 1/3 \end{bmatrix}$$ can be obtained by taking all permutations or just $123,231,312$.

The Birkhoff–von Neumann theorem states that every bistochastic matrix is a convex combination of permutation matrices. Its algorithmic proof gives a polynomial time algorithm that gives such a combination with at most $n^2$ matrices, which is probably optimal or close to optimal. In the literature you might be able to find faster algorithms; if you do, please let us know.