Autor Tema: Pseudocódigo

0 Usuarios y 1 Visitante están viendo este tema.

19 Diciembre, 2011, 11:32 am
Leído 2372 veces

set

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 15
  • Karma: +0/-0
  • Sexo: Femenino
Hola, ¿a alguien se le ocurre como generar un pseudocóodigo que genere una permutacióon de los n primeros números naturales?

19 Diciembre, 2011, 05:35 pm
Respuesta #1

Phicar

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 513
  • Karma: +1/-0
  • Sexo: Masculino
    • redinfocol.org
Hola, usa recursividad.

la idea es fijar un numero y rotar los siguientes

digamos n=3

1,2,3   entonces empiezas a rotar
2,3,1 y 3,1,2...y en cada uno de ellos, rotas solo los siguientes numeros

osea en 1,2,3 recursivamente llamas una funcion con 2,3 luego te quedara 2,3 y 3,2 y cuando lo concatenas te da
1,2,3 y 1,3,2

lo mismo haces en cada rotacion y te dan todas las permutaciones.

el codigo quedaria algo como
func(Conjunto s,Conjunto p){
if(size(s)==0){
imprimir(p);
retornar;
}
for(int n = 0;n<size(s);n++){
int r = s[0];
p.add(r);
s.delete(0);
func(s,p);
s = s.subconjunto(1,size(s)).add(r);
}
}
Esto no es ningun lenguaje, pero pense que asi lo entenderias, es notacion sobre conjuntos pero escrita :P.
Si notas, en S tendras los numeros naturales del 1 al n, y en p iras guardando la recursion.

pd: te servira tambien ver esto http://en.wikipedia.org/wiki/Factorial_number_system
redinfocol.org

20 Diciembre, 2011, 02:04 pm
Respuesta #2

feriva

  • $$\Large \color{#a53f54}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 12,032
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
También se podría generar aleatoriamente una permutación cualquiera para un "n" dado; después se guardaría en un "array". Posteriormente, con un bucle, se volvería a generar otra permutación; seguidamente, mediante un comando condicional "if" se compararía con los elementos guardados en la "array" para, después, según ya exista ese elemento o no en la matriz, optar por guardarlo en ella o volver a repetir el bucle. Y así sucesivamente hasta alcanzar una contante, guardada en una variable, que marque el número de permutaciones para "n" según la fórmula. Aunque para un "n" grande supongo que sería lento.

 Saludos.

20 Diciembre, 2011, 04:04 pm
Respuesta #3

Phicar

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 513
  • Karma: +1/-0
  • Sexo: Masculino
    • redinfocol.org
Uff, he visto metodos para hacer esa permutacion aleatoria y es realmente lento. Tu a cual te refieres Feriva? :)
Y fijate que para generar una permutacion debes usar cierta memoria, ahora imaginate guardar todas las n! permutaciones en un arreglo.
redinfocol.org

20 Diciembre, 2011, 04:25 pm
Respuesta #4

feriva

  • $$\Large \color{#a53f54}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 12,032
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Uff, he visto metodos para hacer esa permutacion aleatoria y es realmente lento. Tu a cual te refieres Feriva? :)
Y fijate que para generar una permutacion debes usar cierta memoria, ahora imaginate guardar todas las n! permutaciones en un arreglo.
Hola, Phicar. Sí, ya imagino que sería inviable a lo hora de la verdad; era más por decir algo en plan "teórico", no para ponerlo en práctica.

Saludos.

21 Diciembre, 2011, 09:43 am
Respuesta #5

set

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 15
  • Karma: +0/-0
  • Sexo: Femenino
Hola chicos creo que me voy a basar en generar un algoritmo que utilice otro subalgoritmo que consiste en generar una variable aleatoria uniforme ([0,1])
cuando lo tenga pensado mejor lo publico a ver que os parece pero creo que la idea es buena. un saludo.

21 Diciembre, 2011, 06:42 pm
Respuesta #6

Phicar

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 513
  • Karma: +1/-0
  • Sexo: Masculino
    • redinfocol.org
Usarias la idea como la de feriva, te recomiendo veas el algoritmo de Satolo. :)
redinfocol.org

21 Diciembre, 2011, 09:10 pm
Respuesta #7

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Un algoritmo puede ser el siguiente:

Paso base. Si \( n=1 \) devuelvo:
\( \color{red}1 \)

Paso inductivo. Ahora a partir de una permutación aleatoria de los dígitos \( \{1,\dots, n-1\} \), construyamos otra con los números \( \{1,\dots, n\} \). Sea \( \color{red} a_1a_2\dots a_{n-1} \) la permutación aleatoria de los dígitos \( 1,2,\dots n-1 \), o sea, \( a_i\in \{1,\dots, n-1\}\ \forall i \) y \( a_i \neq{} a_j,\ \forall i\neq{}j \). Se puede representar de la siguiente manera:

\( \underbrace{\fbox{$\phantom{n}$}}_{0}{\color{red} a_1}\underbrace{\fbox{$\phantom{n}$}}_{1}{\color{red} a_2}\underbrace{\fbox{$\phantom{n}$}}_{2}{\color{red} a_3}\underbrace{\fbox{$\phantom{n}$}}_{3}\dots\dots {\color{red} a_{n-2}}\underbrace{\fbox{$n$}}_{n-2}{\color{red} a_{n-1}}\underbrace{\fbox{$\phantom{n}$}}_{n-1} \)

Lo único que hay que hacer es elegir un recuadro para colocar \( n \) (en el dibujo puse \( n \) en la posición \( n-2 \) sólo para fijar ideas). Hay \( n \) recuadros así que habría que construirse una función que genere un natural aleatorio en el rango [0..n-1]. Y finalmente colocar \( n \) en esa posición.

Saludos

PD. Ese subprograma del que hablo se puede hacer fácilmente a partir de otro que simule una variable uniforme [0,1].
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print