Algoritmo para recuperar todas las permutaciones (aleatorias) para una secuencia de vectores 1...N con sólo valores únicos

Question

El problema es el siguiente: tengo un vector de $N$ elementos de longitud (que sólo contengan único valores de $1...N$ ).

1. Estoy buscando un algoritmo para obtener todas las combinaciones (aleatorias) posibles, donde cada valor sólo puede aparecer una vez.

Es decir, por ejemplo, los siguientes vectores en el caso $N=3$ .

$(1, 2, 3)$

$(1, 3, 2)$

$(2, 1, 3)$

$(2, 3, 1)$

$(3, 1, 2)$

$(3, 2, 1)$

¿Algo más?

Preguntas de seguimiento:

1. ¿Hay alguna forma de filtrar las reglas que parecen sistemáticas, por ejemplo el vector $(1,2,3,4)$ ya que sólo busco combinaciones aleatorias.
2. ¿Cuántas combinaciones son posibles? ¿Es 100x100?
3. ¿Existe un Matlab ¿hay alguna función disponible para ello?

Answer 1

No son combinaciones pero permutaciones . Existen $n!$ permutaciones de $(1,2,\cdots,n)$ con $n!=1\cdot2\cdots n$ .

Existe un algoritmo muy sencillo para obtenerlos, de uno en uno, en orden lexicográfico (es decir, el orden que utiliza en su ejemplo).

Comenzar con una permutación $(a_1,a_2,\cdots,a_n)$ queremos el siguiente en orden lexicográfico.

1. Encontrar el índice más pequeño $i$ tal que la secuencia $(a_i,a_{i+1},\cdots,a_n)$ disminuye.
2. Si $i=1$ , has terminado, porque toda la permutación es decreciente, y es la última.
3. Invierta esta secuencia $(a_i,a_{i+1},\cdots,a_n)$ por lo que ahora está aumentando.
4. Intercambio $a_{i-1}$ con $a_j$ donde $j$ es el índice más pequeño, tal que $j\geq i$ y $a_j>a_{i-1}$ . Usted tiene entonces la siguiente permutación.

Véase RosettaCode para varias implementaciones. Para Matlab, tiene el permanentes función.

Encontrará este algoritmo y otros en Knuth's TAOCP volumen 4 fasc. 2 . Todo el volumen 4 trata de algoritmos combinatorios.