Si tengo un doblemente estocástica de la matriz, ¿cómo puedo encontrar el conjunto de todas las soluciones factibles?
Respuesta
¿Demasiados anuncios?
No Knuth del Volumen 4, Fascículo 2, de El Arte de la Programación de la Computadora tiene una larga sección en generar todas las permutaciones, incluyendo algoritmos para hacerlo. He encontrado un proyecto de aquí en línea. (Actualización: El enlace funciona, pero ahora es un archivo comprimido. Sin embargo, Knuth ha publicado desde entonces el Volumen 4A: Combinatoria Algoritmos, Parte 1, que incluye este material en la generación de permutaciones como la Sección 7.2.1.2. )
Entonces, pasando de una permutación de una matriz de permutación es bastante sencillo. Por ejemplo, suponga que tiene la permutación 1342 de los números 1, 2, 3, y 4. Que se puede representar en dos líneas, la forma como
$$\begin{matrix}1&2&3&4\\1&4&2&3\end{matrix}$$
debido a que la permutación envía 1 a la posición 2 a la cuarta posición, etc.
A continuación, la permutación de la matriz es la matriz con 1 en entradas (1,1), (2,4), (3,2), (4,3), y 0 en otro lugar; es decir,
$$\begin{pmatrix}1&0&0&0\\0&0&0&1\\0&1&0&0\\0&0&1&0\end{pmatrix}$$
