Foros del Web » Programando para Internet » Javascript »

permutaciones

Estas en el tema de permutaciones en el foro de Javascript en Foros del Web. Veamos, llevo tiempo queriendo hacer una cosa y jamás me ha salido. Se trata de que, teniendo un array abecedario: Código PHP: var  abc = ...
  #1 (permalink)  
Antiguo 16/02/2004, 16:16
Avatar de derkenuke
Colaborador
 
Fecha de Ingreso: octubre-2003
Ubicación: self.location.href
Mensajes: 2.665
Antigüedad: 20 años, 6 meses
Puntos: 45
permutaciones

Veamos, llevo tiempo queriendo hacer una cosa y jamás me ha salido. Se trata de que, teniendo un array abecedario:

Código PHP:
var abc="abcdefghijklmnopqrstuvwxyz"
abc=abc.split(""); 
El script debe sacar todas las combinaciones de la longitud que yo quiera, es decir, si le doy longitud 3, deberia hacer todas las combinaciones posibles de "abc", pudiendo repetir o no caracteres. Mas o menos quedaría:

aaa
aab
aac
aba
abb
abc
aca
acb
acc

Todo esto solo empezando por la a, para la b y la c seria igual solo que empezando por estas letras. Mas o menos la idea espero que me la capten.

Puedo hacerlo manualmente, es decir, sabiendo con antelacion la longitud, anidar bucles hasta que salga, aqui serian 3 bucles anidados; pero quisiera hacer una funcion generica para que la longitud se pase por argumento.


Espero una ayuda.
Muchas gracias!
__________________
- Haz preguntas inteligentes, y obtendrás más y mejores respuestas.
- Antes de postearlo Inténtalo y Búscalo.
- Escribe correctamente tus mensajes.
  #2 (permalink)  
Antiguo 18/02/2004, 13:31
Avatar de derkenuke
Colaborador
 
Fecha de Ingreso: octubre-2003
Ubicación: self.location.href
Mensajes: 2.665
Antigüedad: 20 años, 6 meses
Puntos: 45
Mmmm, parece ser muy complicado... Para mi lo es!
__________________
- Haz preguntas inteligentes, y obtendrás más y mejores respuestas.
- Antes de postearlo Inténtalo y Búscalo.
- Escribe correctamente tus mensajes.
  #3 (permalink)  
Antiguo 19/02/2004, 13:47
Avatar de JavierB
Colaborador
 
Fecha de Ingreso: febrero-2002
Ubicación: Madrid
Mensajes: 25.052
Antigüedad: 22 años, 2 meses
Puntos: 772
Hola, derkenuke.

A ver si este código es lo que buscas:
Código PHP:
var letras="abcdefghijklmnopqrstuvwxyz"
letras=letras.split("");
numLetras=letras.length;
permuta=new Array;
combina 3//nº de letras a combinar;
serie=1;
for(
i=0i<combinai++)
    
serie *= numLetras;
for(
i=0;i<serie;i++)
    
permuta[i]='';
subSerie serie/numLetras;
for(
i=0;i<combina;i++) {
    
per=let=0;
    for(
j=0;j<serie;j++) {
        
permuta[j]+=letras[let];
        
per+=1;
        if(
per>subSerie) {
            
per=1let+=1;
            if(
let>numLetras-1let=0;
        }
    } 
subSerie /= numLetras;
}
for(
i=0;i<serie;i++)
document.write(permuta[i]+'<br/>'); 
Saludos,
  #4 (permalink)  
Antiguo 19/02/2004, 15:23
Avatar de derkenuke
Colaborador
 
Fecha de Ingreso: octubre-2003
Ubicación: self.location.href
Mensajes: 2.665
Antigüedad: 20 años, 6 meses
Puntos: 45


Mi héroe! jeje. increible. sencillamente. Siempre encontrais respuestas.

__________________
- Haz preguntas inteligentes, y obtendrás más y mejores respuestas.
- Antes de postearlo Inténtalo y Búscalo.
- Escribe correctamente tus mensajes.
  #5 (permalink)  
Antiguo 20/02/2004, 03:30
Avatar de JavierB
Colaborador
 
Fecha de Ingreso: febrero-2002
Ubicación: Madrid
Mensajes: 25.052
Antigüedad: 22 años, 2 meses
Puntos: 772
Me alegro de que te haya servido y gracias por los aplausos.
  #6 (permalink)  
Antiguo 01/08/2005, 15:19
Avatar de derkenuke
Colaborador
 
Fecha de Ingreso: octubre-2003
Ubicación: self.location.href
Mensajes: 2.665
Antigüedad: 20 años, 6 meses
Puntos: 45
Retomo el tema despues de mas de un año porque me ha vuelto a picar el gusanillo. Esta vez tenia que hacer una cosa parecida, pero con una funcion que devolviera la siguiente combinacion. Es decir, si a la funcion le paso "aaa" que me devuelva "aab", y si le paso esto ultimo "aac".

Tenia que estar preparada para funcionar por si sola hasta el infinito, de manera que "zzz" generase "aaaa" para empezar de nuevo a dar "aaab", "aaac"... "zzzz".

Es en PHP, pero vamos, que viene a ser lo mismo. La funcion es recursiva, y he comentado todo lo mejor que he podido para que se entienda. Al parecer mis conocimientos siguen aumentando (aunque me ha costado su tiempo...).

Código PHP:
//esta denominada como 'abecedario' en los comentarios
$abc=array("A""B""C""D""E""F""G""H""I""J""K""L""M""N""O""P""Q""R""S""T""U""V""W""X""Y""Z");

// devuelve la siguiente cadena generada por el orden logico del alfabeto
function siguiente($str=""$attach="") {
    global 
$abc;
    
//si nos lo dan vacio, vacio lo devolveremos
    
if($str=="") return "";
    
//calculamos su longitud, lo necesitaremos y es mejor almacenarlo en una variable
    
$longitud=strlen($str);
    
//cogemos la ultima letra para analizar qué parte debemos evolucionar
    
$ultima_letra=substr($str,-1);
    
//si la ultima letra de la palabra es la ultima letra de abecedario
    //  haremos un siguiente de toda la cadena menos el ultimo caracter, y el ultimo caracter
    //  se convertira en $abc[0]
    //cogemos toda la cadena menos la ultima letra
    
$loViejo=substr($str,0,$longitud-1);
    if(
$ultima_letra==$abc[count($abc)-1]) {
        
//si resulta que loViejo esta vacio (es que la longitud era 1), necesitaremos una nueva cadena desde cero
        
if($loViejo=="") {
            
//generacion de nueva cadena de orden $longitud+1 repleta de $abc[0]
            
$devolver="";
            for(
$a=0$a<$longitud+1+strlen($attach); $a++)
                
$devolver.=$abc[0];
            return 
$devolver;
        }
        
//si loViejo tenia contenido simplemente devolveremos ese siguiente(viejo), y mantendremos lo que se 
        //  estaba manteniendo y un $abc[0] para empezar una nueva secuencia.
        
else
            return 
siguiente$loViejo $attach.$abc[0] );
    }
    
//la ultima letra no es la ultima detra de abecedario. Basta modificar esa letra unicamente.
    
else {
        
//para ello extraemos la posicion de la ultima letra en abecedario
        
$pos_ultima_letra=array_search($ultima_letra$abc);
        
//y obtenemos la letra siguiente
        
$nueva_ultima_letra=$abc[$pos_ultima_letra+1];
        
//devolveremos todo exactamente como estaba, solo que la ultima letra ya estara cambiada
        
return $loViejo.$nueva_ultima_letra .$attach;
    }

Espero que a alguien le sirva!. Podemos hacer:
Código PHP:
$actual="A";
for(
$a=0$a<100000$a++) {
    echo 
$actual."<br>";
    
$actual=siguiente($actual);

si desearamos las primeras 100000 generaciones.





Me queda el mono de una ultima funcion, que se le pase un numero tipo 123 y te devuelva la combinacion numero 123 sin tener que hacer las 122 anteriores. Vere si algun dia la saco, y espero no tardar tanto como esta .


Posteado queda, pues!
__________________
- Haz preguntas inteligentes, y obtendrás más y mejores respuestas.
- Antes de postearlo Inténtalo y Búscalo.
- Escribe correctamente tus mensajes.
  #7 (permalink)  
Antiguo 01/09/2005, 17:53
(Desactivado)
 
Fecha de Ingreso: noviembre-2002
Ubicación: Ciudad Autónoma de Buenos Aires
Mensajes: 2.367
Antigüedad: 21 años, 5 meses
Puntos: 317
Hola derkenuke , JavierB :

Qué proyecto interesante.

Lo estuve leyendo, aunque no entiendo PHP, y me pareció recordar un método para hacer algo así. Pero resultó que no era "tan así".

Intenté hacer una combinación de caracteres alfabéticos en todas sus posibilidades; pero pudiendo elegir la cantidad. Quiero decir : todas las combinaciones posibles de 2 caracteres de los 3 primeros("a" "b" "c") ; todas las combinaciones posibles de 3 caracteres de los 5 primeros("a" "b" "c" "d" "e")...

La lógica me dice que ése es justamente el método que usan los números en dígitos : todas las combinaciones posibles de 3 "caracteres" (dígitos) de los 10 "primeros" (y únicos "0" al "9") serían del "000" al "999".

El método para las letras sería como ir sumando 1 desde 0 y convertirlo a caracter alfabético de una secuencia, hasta terminar cuando aparezca el cuarto dígito (porque queríamos 3).

Eso es jusamente lo que hace toString(n); donde n es el valor máximo de la "secuencia alfabética" hasta donde vamos a combinar, y con un for le decimos que llegue hasta el (p.e.) "999".

El problema es que la secuencia va desde el "0" hasta la "z"; no desde "a" hasta "z". Le podemos decir hasta que caracter usar, pero no desde cual.

Un ejemplo típico es el hexadecimal. Si usamos

Código:
<input onblur="this.value=(this.value*1).toString(16)" value="255">
la secuencia para convertir será de "0" a "f", no de "a" a "p".

¿Alguien sabe si se le puede decir a toString() desde dónde empezar?

gracias

furoya

Última edición por furoya; 05/09/2005 a las 11:04
  #8 (permalink)  
Antiguo 01/09/2005, 18:06
Avatar de derkenuke
Colaborador
 
Fecha de Ingreso: octubre-2003
Ubicación: self.location.href
Mensajes: 2.665
Antigüedad: 20 años, 6 meses
Puntos: 45
Si, creo que he dado con la solucion....

Código PHP:
<input onblur="cambia(this)" value="255">

<
script>

var 
letras="abcdefghijklmnopqrstuvwxyz"
letras=letras.split("");

function 
cambia(caja) {
    
// el +10 hace omitir los numeros del 0 al 10 en la conversion, empezando desde a,b,c...
    
caja.value=(parseInt(caja.value)+10).toString(letras.length);
}

</script> 
Me estas abriendo los ojos furoya... no se me habria ocurrido ni por asomo eso de toString pasandole la base...

A ve si me sale algo con ello.

Sobresaliente.
__________________
- Haz preguntas inteligentes, y obtendrás más y mejores respuestas.
- Antes de postearlo Inténtalo y Búscalo.
- Escribe correctamente tus mensajes.
  #9 (permalink)  
Antiguo 01/09/2005, 18:42
(Desactivado)
 
Fecha de Ingreso: noviembre-2002
Ubicación: Ciudad Autónoma de Buenos Aires
Mensajes: 2.367
Antigüedad: 21 años, 5 meses
Puntos: 317
La verdad es que no sé en qué navegadores funciona, pero lo usé varias veces para convertir a binario, en códigos que eran para IE.

Probé tu código con el 255, y me aparecen números. En la "segunda vuelta" empieza otra vez de "0". Me parece que se puede calcular los restos con %.

Este ejemplo creo lo saqué del foro.

Código:
 
<script>
function convierte(){
var valoresHexa = "0123456789ABCDEF";
decValor=entrada.value;
conDec=valoresHexa.charAt(parseInt(decValor /16/16/16%16)) + valoresHexa.charAt(parseInt(decValor /16/16%16)) +  valoresHexa.charAt(parseInt(decValor /16%16)) + valoresHexa.charAt(decValor %16)
salida.value=conDec;
}
</script>
<input id=entrada onblur="convierte()" /><input id=salida />
aunque hay que saber de antemano la cantidad de "dígitos".

En algún lado debe haber un tutorial de toString(), pero los que yo vi no decían nada del límite inferior.
  #10 (permalink)  
Antiguo 01/09/2005, 19:17
Avatar de derkenuke
Colaborador
 
Fecha de Ingreso: octubre-2003
Ubicación: self.location.href
Mensajes: 2.665
Antigüedad: 20 años, 6 meses
Puntos: 45
En realidad lo que se le pasa a la funcion toString es la nueva base, asi que si le pasamos base 16 (hexadecimal) coge por caracteres validos 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F; como ya sabemos.

Lo que estoy intentando ahora pasarle de base la longitud del abecedario (26), de la variable 'letras' de javierB. Lo que pasa es que no se como decirle que elimine el 0,1,2,3,4,5,6,7,8,9 de toda la secuencia 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,G,H....

Es la misma duda que la que tienes tu.

Para la primera pasada (del 0 al 25) es facil porque con sumarle 10 antes de convertirlo como he hecho aqui:
Código PHP:
(parseInt(caja.value)+10).toString(letras.length); 
pues ya vale. La segunda pasada se me complica mas, pero con tiempo yo creo que lo sacaremos.

A ver si le dedico al script mas neuronas.
__________________
- Haz preguntas inteligentes, y obtendrás más y mejores respuestas.
- Antes de postearlo Inténtalo y Búscalo.
- Escribe correctamente tus mensajes.
  #11 (permalink)  
Antiguo 01/09/2005, 20:02
Avatar de derkenuke
Colaborador
 
Fecha de Ingreso: octubre-2003
Ubicación: self.location.href
Mensajes: 2.665
Antigüedad: 20 años, 6 meses
Puntos: 45
Lo unico que he podido sacar hasta ahora ha sido:

Código PHP:
var letras="abcdefghijklmnopqrstuvwxyz"
letras=letras.split("");

function 
num2letra(num) {
    var 
resultado=(num+10).toString(36);
    
//tratamos cada caracter
    
var cadena=resultado.split("");        
    
//aqui iremos poniendo el resultado
    
var formateado="";
    for(var 
a=0a<resultado.lengtha++) {
        
//si es un numero, debemos tratarlo; si no lo añadimos a pelo a la cadena formateado
        
if( cadena[a].search(/^[0-9]{1}$/)==) {        // se devuelve 0 si es un numero
            //document.write("numero("+cadena[a]+")! ");
            
formateado+=num2letraparseInt(cadena[a]) );
        }
        else {
            
//alert("letra! "+cadena[a]);
            
formateado+=cadena[a];
        }
    }
    return [
formateado];
}

for(
a=0;a<100;a++) {
    
document.write(''+a+' --> '+num2letra(a)+'<br/>');

Y su salida es:
Código:
0 --> a
1 --> b
2 --> c
3 --> d
4 --> e
5 --> f
6 --> g
7 --> h
8 --> i
9 --> j
10 --> k
11 --> l
12 --> m
13 --> n
14 --> o
15 --> p
16 --> q
17 --> r
18 --> s
19 --> t
20 --> u
21 --> v
22 --> w
23 --> x
24 --> y
25 --> z
26 --> ba
27 --> bb
28 --> bc
29 --> bd
30 --> be
31 --> bf
32 --> bg
33 --> bh
34 --> bi
35 --> bj
36 --> ba
37 --> bb
38 --> bc
39 --> bd
40 --> be
41 --> bf
42 --> bg
43 --> bh
44 --> bi
45 --> bj
46 --> bk
47 --> bl
48 --> bm
49 --> bn
50 --> bo
51 --> bp
52 --> bq
53 --> br
54 --> bs
55 --> bt
56 --> bu
57 --> bv
58 --> bw
59 --> bx
60 --> by
61 --> bz
62 --> ca
63 --> cb
64 --> cc
65 --> cd
66 --> ce
67 --> cf
68 --> cg
69 --> ch
70 --> ci
71 --> cj
72 --> ca
73 --> cb
74 --> cc
75 --> cd
76 --> ce
77 --> cf
78 --> cg
79 --> ch
80 --> ci
81 --> cj
82 --> ck
83 --> cl
84 --> cm
85 --> cn
86 --> co
87 --> cp
88 --> cq
89 --> cr
90 --> cs
91 --> ct
92 --> cu
93 --> cv
94 --> cw
95 --> cx
96 --> cy
97 --> cz
98 --> da
99 --> db
Como ves cuando empieza la segunda pasada en
26 --> ba
empieza desde 'b' y no por 'a', por aquello del +10.

A ver si se nos ocurre algo.
__________________
- Haz preguntas inteligentes, y obtendrás más y mejores respuestas.
- Antes de postearlo Inténtalo y Búscalo.
- Escribe correctamente tus mensajes.
  #12 (permalink)  
Antiguo 02/09/2005, 06:51
Avatar de derkenuke
Colaborador
 
Fecha de Ingreso: octubre-2003
Ubicación: self.location.href
Mensajes: 2.665
Antigüedad: 20 años, 6 meses
Puntos: 45
Progresos por fin, despues de haberlo intentado horas.

El problema es que la escala en la que nosotros representamos el abecedario es
Código PHP:
var YOdevuelvo="abcdefghijklmnopqrstuvwxyz" 
pero la escala en la que javascript devuelve esa misma cadena al hacer el toString() es
Código PHP:
var ELdevuelve="0123456789abcdefghijklmnop"
, luego ahi tenemos un grave problema.

Lo que hago es codificar el numero en la base de la longitud de ELdevuelve
Código PHP:
var resultado=(num).toString(ELdevuelve.length); 
. 'resultado' seguro contiene letras unicamente de la cadena ELdevuelve, ya que es su escala de caracteres cuando la base es ELdevuelve.length.

Espero que me podais seguir hasta aqui.

Ahora lo que hago es transformar esos caracteres (suyos) a los mios. Es decir, al '0' le corresponde la 'a', al '1' la 'b', al '2' la 'c'... y asi hasta la 'p', que le corresponde la 'z'.

Construyo el script, y me encuentro mi primer problema: El "numero" que va despues de 'p' (='z') no es '00' (='aa'), si no '10' (='ba'). Asi que pienso que si se encuentra un numero que esta en las decimas, se le debe restar 1. Lo hago asi y funciona a la perfeccion, hasta que llegamos a '100' (='aaa'). Claro, qué pasa. Que a la cifra de las centenas (1) le quito 1, y todo bien. A la cifra de las decenas (0) le quito 1, y da -1. ERROR.

Se me ha ocurrido solucionar el problema diciendo que la resta de 1 solo la ejecute una vez por transformacion. Es decir, que si le quita a las centenas, a las decenas ya no. Si se lo quita a los miles, a las centenas ya no.

Y funciona!. de 'zz' pasa a 'aaa', y de 'zzz' pasa de 'aaaa'. Comprobado.

Código PHP:
var YOdevuelvo="abcdefghijklmnopqrstuvwxyz".split("");
var 
ELdevuelve="0123456789abcdefghijklmnop";

function 
num2letra(num) {
    var 
resultado=(num).toString(ELdevuelve.length);
    
resultado=resultado.split("");
    var final=
"";
    var 
quitado=false;
    for(var 
a=0;a<resultado.length;a++) {
        
n=resultado[a];
        
//si no se le ha quitado, si a>decenas, y si es un numero del 1 al 9 (el cero no vale)
        
if( resultado.length-1>&& resultado[a].search(/^[1-9]$/)==&& quitado==false ) {
            
//document.write("Le quito '"+(1)+"' al '"+resultado[a]+"'....");            //debug
            
n-=1;        //le restamos 1
            
quitado=true;
        }
        
posELdevuelve.indexOf(n);
        final+= 
YOdevuelvo[pos];
    }
    return [
"Convertido="+resultado.join(""),"Final="+final];

Se puede imprimir un bucle, por ejemplo:
Código PHP:
for(a=0;a<1000;a++) {
    
document.write('Numero'+a+' --> '+num2letra(a).join("; ")+'<br/>');

Ahora bien, no todo es camino de rosas, porque ya le he encontrado un fallo. Resulta que a las decenas le quitamos 1 si es por ejemplo un 9. El "numero" '9p' antes de sustituirlo lo convertimos a '8p'. Lo sustituimos y da 'iz'. El numero siguiente es 'a0', que lo convertimos a 'a0' (no se toca) y da 'ka', en vez de 'ja'.

¿Y porque se salta la J? Pues porque el '9' es convertido a '8', que segun
Código PHP:
var YOdevuelvo="abcdefghijklmnopqrstuvwxyz"
var ELdevuelve="0123456789abcdefghijklmnop"
se corresponde a 'i'. Pero despues de ese '8' nuestro, se pasa a 'a', en vez de a '9'; y 'a' no se toca. Es decir: en el ciclo nuestro de una vez convertido (antes de sustituir), nos pasamos el '9'.


De momento no se como solucionarlo, supongo que a parte de los numeros de las decenas, centenas y miles, tambien hay que quitarle 1 a las letras de esas posiciones....



Aunque de momento va bien, no?
__________________
- Haz preguntas inteligentes, y obtendrás más y mejores respuestas.
- Antes de postearlo Inténtalo y Búscalo.
- Escribe correctamente tus mensajes.
  #13 (permalink)  
Antiguo 02/09/2005, 06:58
Avatar de derkenuke
Colaborador
 
Fecha de Ingreso: octubre-2003
Ubicación: self.location.href
Mensajes: 2.665
Antigüedad: 20 años, 6 meses
Puntos: 45
Cita:
supongo que a parte de los numeros de las decenas, centenas y miles, tambien hay que quitarle 1 a las letras de esas posiciones....
Lo que no habia pensado es que al quitarle 1 consigo la 'j', pero me olvido de la 'z'...
__________________
- Haz preguntas inteligentes, y obtendrás más y mejores respuestas.
- Antes de postearlo Inténtalo y Búscalo.
- Escribe correctamente tus mensajes.
  #14 (permalink)  
Antiguo 05/09/2005, 11:03
(Desactivado)
 
Fecha de Ingreso: noviembre-2002
Ubicación: Ciudad Autónoma de Buenos Aires
Mensajes: 2.367
Antigüedad: 21 años, 5 meses
Puntos: 317
¡Epa!. ¡Que tampoco sea una obsesión!

Lo de solamente aceptar una base para toString me parece que no tendrá arreglo. Lo de usar 2 cadenas va a funcionar seguro. Quizás habría que insistir ( se me ocurre ) con replace(). Y tal vez un prototype. Bah, son ideas.

Te felicito. Hasta ahora, el empeño es la única forma que conozco de conseguir algo que nos deje orgullosos.
furoya
  #15 (permalink)  
Antiguo 27/03/2007, 18:33
Avatar de derkenuke
Colaborador
 
Fecha de Ingreso: octubre-2003
Ubicación: self.location.href
Mensajes: 2.665
Antigüedad: 20 años, 6 meses
Puntos: 45
Re: permutaciones

Bueno, mi primer mensaje en este hilo tiene más de tres años, pero hace una semana me picó el gusanillo y estuve probando para ver si se podía hacer un toString() con las características pedidas (una semana me ha costado sacarlo ). Éstas eran:

Si toString() permite traducir de una base numérica a otra tenemos el problema de que no nos da combinación de los caracteres, es decir:
si cambiamos de base 10 a base 10 pasa esto:
0=0
1=1
.
.
8=8
9=9
10=10
11=11
evidentemente no se toca nada. Bueno, yo quería que al llegar al 10 se repitiera el 00, ya que la siguiente combinación con [0,1,2,3,4,5,6,7,8,9] después de 9 es 00, y luego 01...
0=0
1=1
.
.
8=8
9=9
10=10 <--- debería ser 00
11=11 <--- debería ser 01
12=12 <--- debería ser 02

Bueno pues después de hacer muuuuchos dolores de cabeza sólo hacia falta un toString() mejorado, un toString2():
Código PHP:
Number.prototype.toString2=function(b) {
    if( 
0<=this && this<) {
        
//caso directo, no hay que hacer nada, devuelve bien
        
res=(this).toString(b);
    }
    else {
        
//caso general
        //el ultimo se mantiene como se transformaria
        
var ultimo=(this).toString(b);
        
ultimo=ultimo[ultimo.length-1];
        
//los primeros (sean cuantos sean) se resuelven recursivamente, hasta llegar a un caso directo
        
var aConvertir=parseInt(this/b)-1;
        var 
primeros=(aConvertir).toString2(b);
        
res=primeros+ultimo;    //siendo primeros y ultimo strings
    
}
    return 
res;
}

for(var 
b=3a=0;a<500a++) {
    var 
c=(a).toString2(b);
    
document.writea+" --> "+c+"<br/>" );

Fijáos si era sencilla la solución (recursiva).
Bueno pues esas líneas para conseguir la recursión me han costado dos semanas.


Después de ésto, hallar la combinación número 124967 se hace con un método directo, sin tener que calcular las 124966 anteriores. Y todo esto lo aplicaremos a aquello de:
Código PHP:
var YOdevuelvo="abcdefghijklmnopqrstuvwxyz".split("");
var 
ELdevuelve="0123456789abcdefghijklmnop"
Para hallar la combinación número 124967 que forman las letras [abcdefghijklmnopqrstuvwxyz], así de sencillo.



Bueno, voy a dormir un rato, que el cuerpo me lo está pidiendo a voces....
__________________
- Haz preguntas inteligentes, y obtendrás más y mejores respuestas.
- Antes de postearlo Inténtalo y Búscalo.
- Escribe correctamente tus mensajes.

Última edición por derkenuke; 27/03/2007 a las 18:44 Razón: simplificación de código
  #16 (permalink)  
Antiguo 07/04/2007, 19:08
Avatar de derkenuke
Colaborador
 
Fecha de Ingreso: octubre-2003
Ubicación: self.location.href
Mensajes: 2.665
Antigüedad: 20 años, 6 meses
Puntos: 45
Re: permutaciones

La solución en PHP, por si alguien la necesita. Ví en la función chr() que lo intentaban.. yo sin embargo uso la función base_convert(), como lo hice con toString() en JS:

Código PHP:
function base_convert2($n,$b) {        //asumo que desde la base que queremos transformar es desde decimal
    
if( 0<=$n && $n<$b ) {        //caso directo, no hay que hacer nada, devuelve bien
        
$res=base_convert($n,10,$b);
    }
    else {                          
//caso general
        //el ultimo se mantiene como se transformaria
        
$ultimo=base_convert($n,10,$b);
        
$ultimo=substr($ultimo, -11);        //ultimo caracter
        //los primeros (sean cuantos sean) se resuelven recursivamente, hasta llegar a un caso directo
        
$aConvertir=(int)($n/$b)-1;
        
$primeros=base_convert2($aConvertir,$b);
        
$res=$primeros.$ultimo;    //siendo primeros y ultimo strings
    
}
    return 
$res;
}

$YOdevuelvo=split(" " "a b c d e f g h i j k l m n o p q r s t u v w x y z");
$ELdevuelve="0123456789abcdefghijklmnop";

function 
num2alpha($n$b=26 ) {
    global 
$YOdevuelvo$ELdevuelve;
    
$bc=base_convert2($nstrlen($ELdevuelve) );
    for(
$a=0$dev="";$a<strlen($bc);$a++) {
        
// la posicion de cada caracter en ELdevuelve es la letra en $YOdevuelvo
        
$pos=strpos($ELdevuelve$bc[$a]);
        
$dev.=$YOdevuelvo[$pos];
    }
    return 
$dev;
}

function 
alpha2num($alpha$b=26 ) {
    global 
$YOdevuelvo;
    
$YOdevuelvoSTR=implode("",$YOdevuelvo);
    for(
$a=0,$dev=0$a<strlen($alpha);$a++) {    
        
// orden: unidades=0; decenas=1; centenas=2 ...
        
$orden=strlen($alpha)-$a-1;
        
$pos=strpos($YOdevuelvoSTR$alpha[$a] );    //posicion de la letra con respecto a $YOdevuelvo
        
if($orden==0)
            
$dev+=$pos;        //haría pow($base,$orden), pero daría 1 en vez de 0
        
else 
            
$dev+=pow($b,$orden)*($pos+1);    
    }
    return 
$dev;

Código PHP:
echo alpha2num("hola")."<br/>";    //151060
echo num2alpha(151060)."<br/>";  //hola 
Tiene un par de problemas cuando tiene que trabajar con cifras grandes, no se puede traducir a numero "permutaciones" porque daría una combinación demasiado alta para un entero supongo (3.4319006077858E+017) y perdemos la precisión.

Pero creo que hasta que la cadena a devolver fuera de 8 caracteres num2alpha() funciona, más no. Con alpha2num() no he encontrado restricciones.


Saludos foreros.
__________________
- Haz preguntas inteligentes, y obtendrás más y mejores respuestas.
- Antes de postearlo Inténtalo y Búscalo.
- Escribe correctamente tus mensajes.
  #17 (permalink)  
Antiguo 07/04/2007, 19:39
Avatar de Panino5001
Me alejo de Omelas
 
Fecha de Ingreso: mayo-2004
Ubicación: -34.637167,-58.462984
Mensajes: 5.148
Antigüedad: 20 años
Puntos: 834
Re: permutaciones

Sólo porque alguna vez hice algo parecido, lo pongo para ampliar un poco el tema y ver si a alguien le sirve. Como les dije, es sólo algo parecido, un algoritmo en php que usa backtracking para obtener coincidencias en base a un diccionario de letras (en el ejemplo es muy limitado, pero se puede ampliar). Lo hice hace bastante, y es una tontería, así que no lo juzguen muy severamente:
Código PHP:
<?php
set_time_limit
(0);
function 
cargar($palabra){
global 
$longitud;
global 
$posibles;
global 
$asignar;
$longitud=strlen($palabra);
$asignar=array();
$posibles =range(a,z);
for(
$i=0;$i<$longitud;$i++){
    
$asignar[$i]=$posibles;
}
}

function 
solucionado($palabra,$test){
if(
$test==$palabra)return 1;
return 
0;
}

function 
paltmp(){
global 
$longitud;
global 
$posibles;
global 
$asignar;
for(
$i=0;$i<$longitud;$i++){
    if(
count($asignar[$i])==count($posibles))return 0;
}
return 
1;
}

function 
ensayar($palabra){
global 
$longitud;
global 
$posibles;
global 
$asignar;
global 
$solucionado;
if(
$solucionado==1) return;
for(
$i=0;$i<$longitud;$i++){
if(
count($asignar[$i])!=count($posibles))continue;
for(
$j=0;$j<count($posibles);$j++){
$asignar[$i]=$posibles[$j];
if(
paltmp()>0){
$paltmp=implode('',$asignar);
if(
solucionado($palabra,$paltmp)>0){
echo 
'<br />La solución es: '.$paltmp;$solucionado=1;return;
}
else echo 
'<br />'.$paltmp;
}
ensayar($palabra);
}
$asignar[$i]=$posibles;return;
}

}
$algo='papa';
cargar($algo);
ensayar($algo);
Acá ensayaríamos todas las posibilidades dentro de nuestro diccionario hasta encontrar la palabra 'papa'.
  #18 (permalink)  
Antiguo 07/04/2007, 20:01
Avatar de derkenuke
Colaborador
 
Fecha de Ingreso: octubre-2003
Ubicación: self.location.href
Mensajes: 2.665
Antigüedad: 20 años, 6 meses
Puntos: 45
Re: permutaciones

Gracias Panino5001 por aportar algo al post!
Está interesante el script. Lo que más me gusta es que no tiene límite. Puedes buscar "derkenuke" y tarde o temprano lo encontrará (aunque es demasiado largo ese nombre..)

Saludos !
__________________
- Haz preguntas inteligentes, y obtendrás más y mejores respuestas.
- Antes de postearlo Inténtalo y Búscalo.
- Escribe correctamente tus mensajes.
  #19 (permalink)  
Antiguo 09/11/2012, 11:35
 
Fecha de Ingreso: julio-2011
Mensajes: 5
Antigüedad: 12 años, 9 meses
Puntos: 0
Respuesta: permutaciones

Hola comunidad. hace unos dias realize un pequeno programa que me permite realizar la combinaciones posibles una cantidad de numero agrupados en 3 digitos. pero no he podido ajustar algunas cosas que quisiera que me ayudaran si pueden. la idea es la siguiente:

si introduzco un triple: 111 este solo tiene una combinacion posible que es el mismo numero

si triple: 112 sus combinaciones son 3 : 112-121-211

si triple: 123 sus combinaciones son 6: 123-132-213-231-312-321

hasta aqui estamos bien, pero existe algo que son super permutas que necesito hacer para un sistema de loterias.

ya mi sistema logra sacar los triples principales para combinar. ejemplo

numero 1234: sus triples son: 123-124-134-234: todos difererentes son 6 combinaciones posibles cada uno para un total de 24 combinaciones.

hasta aqui mi algorismo lo hace pero el problema es cuando el cliente pide:

ejemplo1: numero :1123 sus triples principales: 112-113-123 de las cuales los triples 112 y 113 son tres combinaciones cada uno para un total de 6 y el 123 son 6 combinaciones cada uno para un total de 6. y asi la suma de la combinaciones posibles de 1123 es 12 triples.

ejemplo2: numero: 11323: sus principales: 113-112-132-133-323, los numeros que tienen dos iguales 113-112-133-323 son tres combinaciones para un total de 12 y el numero 132 de 6 combinaciones posibles para un total de 18 triples

asi con todas las cantidades posibles permitidas por la base de datos o la memoria.

mi algoritmo aunque un poco alcaico es el siguiente. de ante mano gracias por la ayuda si la realizan.


<?php
$numero = isset($_REQUEST['txtpermuta'])?$_REQUEST['txtpermuta']:null;

$btn = isset($_REQUEST['btn'])?$_REQUEST['btn']:null;

echo "Digitos = ".$cant = strlen($numero);
echo "<br>";

$pos=0;
$a=0;
$b=1;
$c=2;
$triple = Array();
$trip=0;


if($btn=="Permutar"){
for($x=0;$x<$numero;$x++){
$n[$x] = substr($numero,$x,1);
}


for($y=0;$y<=$cant;$y++){

for($z=0;$z<$cant;$z++){
if($c<$cant){

if($n[$a]!=$n[$b] && $n[$a]!=$n[$c] && $n[$b]!=$n[$c]){
//echo "<script>alert('Si Todos son Diferentes');</script>";
$triple[$pos++] = $n[$a]."".$n[$b]."".$n[$c];
$triple[$pos++] = $n[$a]."".$n[$c]."".$n[$b];
$triple[$pos++] = $n[$b]."".$n[$a]."".$n[$c];
$triple[$pos++] = $n[$b]."".$n[$c]."".$n[$a];
$triple[$pos++] = $n[$c]."".$n[$a]."".$n[$b];
$triple[$pos++] = $n[$c]."".$n[$b]."".$n[$a];*/

}


if(($n[$a]==$n[$b] && $n[$a]!=$n[$c]) ||
($n[$a]==$n[$c] && $n[$a]!=$n[$b]) ||
($n[$b]==$n[$c] && $n[$a]!=$n[$b])){
//echo "<script>alert(' Sin dos son iguales');</script>";
$triple[$pos++] = $n[$a]."".$n[$b]."".$n[$c];
$triple[$pos++] = $n[$c]."".$n[$a]."".$n[$b];
$triple[$pos++] = $n[$b]."".$n[$c]."".$n[$a];
}
if($n[$a]==$n[$b] && $n[$a]==$n[$c] && $n[$b]==$n[$c]){
//echo "<script>alert(' Todos iguales');</script>";
$triple[$pos++] = $n[$a]."".$n[$b]."".$n[$c];
}
$c++;
}
}
if($b!=$cant-2){
$b++;
$c = $b + 1;
}else{
$a++;
$b = $a + 1;
$c = $b + 1;
}
}

}

?>
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">

<html>

<head>
<title>Sans Titre</title>
<meta http-equiv="content-type" content="text/html; charset=iso-8859-1" />
<meta name="generator" content="HAPedit 3.1">
</head>
<body bgcolor="#FFFFFF">
<br><br>

<form action="permuta.php" name="frmPermuta" method="post">
Permuta:
<input type="text" name="txtpermuta" size="20" value="<?php echo $txtpermuta; ?>" tabindex="1"/><br><br>
Monto:
<input type="text" name="txtmonto" size="10" value="<?php echo $txtmonto; ?>" tabindex="2"/><br><br>
<input type="submit" name="btn" value="Permutar" tabindex="3"/>
</form>

<textarea name="txtriples" rows="10" cols="20" readonly>
<?php
for($i=0;$i<=count($triple);$i++){echo $triple[$i]."\n";}
?>
</textarea>
<br>
Triples: <input type="text" name="txtCantTrip" value="<?php echo count($triple); ?>" size="20" /><br>
</body>

</html>
  #20 (permalink)  
Antiguo 09/11/2012, 11:41
Avatar de JavierB
Colaborador
 
Fecha de Ingreso: febrero-2002
Ubicación: Madrid
Mensajes: 25.052
Antigüedad: 22 años, 2 meses
Puntos: 772
Respuesta: permutaciones

Hola

Te recuerdo el aviso que había al final de este tema y que parece que no has leído o no le has hecho ni caso.



Tema cerrado.
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Tema Cerrado

SíEste tema le ha gustado a 1 personas




La zona horaria es GMT -6. Ahora son las 03:41.