[pyar] Problema interesante: el anti-string

[Anthony Lenton]

Confieso que no leí todo el thread, pero capaz ayudo...


2010/8/4 Roberto Alsina <ralsina en netmanagers.com.ar>:
> On Wednesday 04 August 2010 15:51:47 Roberto Alsina wrote:
>> Buenas, tengo un problema interesante.
>>
>> Dado una lista de strings S1,S2...SN , producir una lista X1,X2,...XN que
>> al ordenarla alfabéticamente ordene **al revés** que la original.
>>
>> O sea, si tengo
>>
>> S1, X1
>> S2, X2
>>
>>
>> SN, XN
>>
>> Quiero que si ordeno por la primera columna, S1, S2... SN queden en orden
>> alfabético creciente, y si ordeno en orden alfabético creciente por la
>> segunda, queden exactamente al revés.
>>
>> Se entiende?
>> _______________________________________________
>> pyar mailing list pyar en python.org.ar
>> http://listas.python.org.ar/listinfo/pyar
>>
>> PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>
> Forma más fácil del problema:
>
> Dado un string S, crear una funcion f tal que  S1>S2 => f(S1) < f(S2)
>
> Ahí creo que es más claro :-)

Hacer esto es fácil con enteros porque son una secuencia infinita
hacia ambos lados, así que eligiendo cualquier punto al azar podés
encontrar simétricos para todos los demás respecto de este "cero".

Los strings en cambio son cerrados abajo: no hay ningún string más
chico que "".  Entonces no vas a poder encontrar un negativo para
cualquiera, ya que si invertís el conjunto en sí mismo te quedaría un
conjunto "cerrado arriba".

Para ponerlo de otra manera:  Si tomás f("") que, según el enunciado
inicial te tiene que devolver algún string, te queda una cantidad
finita de strings para la imagen de tu función, ya que f(x) debería
dar un string menor que éste para cualquier valor de x.  Y
lamentablemente hay infintos strings mayores que "" por un lado, y
apenas un puñado de strings menores que f("") por otro.

Si podés asumir que hay un string "máximo" (chr(255)*sys.maxint?) sí
se hace posible, ya que transformaste los strings en un conjunto
cerrado en ambas puntas.



-- 
Anthony Lenton