Bonjour à tous ! Voilà le défi que je vous propose :
Elaborer une fonction prenant en paramètre une chaine de caractère :
cette fonction devra renvoyer une chaine utilisant les mêmes lettres que celle passée en paramètre et la chaine créée devra être immédiatement inférieure lexicographiquement.
Exemple : f("cba") = "cab" f("cbad") = "cadb"
On admettra que le paramètre n'est pas minimale, exemple : "ab", "abc", "abcd"
Merci Glapion, pour t'expliquer immédiatement inférieure lexicographiquement :
Si on remplace par des chiffres on a f(3214) = 3142
on prend 3142 car c'est l'entier le plus proche de 3214 et lui étant inférieur, en prenant exactement les mêmes chiffres que 3214 bien sûr
Si je comprends, tu veux dire que valeur("cbad") = 3214
et tu cherches une fonction telle que f(x)= valeur(x)-1 ? pour toute chaîne x="...."
parce que j'ai un peu de mal avec "3142 car c'est l'entier le plus proche de 3214 " ça c'est un scoop
et valeur("z") par exemple c'est 26 ? et valeur("zz") c'est quoi ? 2626 ? on colle les nombres même s'ils sont pas entre 0 et 9 ?
Si je remplace par des chiffres, c'est pour signifier l'ordre alphabétique. En gros imagine l'ensemble E des mots formés par exactement les memes lettres que x, tous ces mots (y compris x) ont une place dans le dictionnaire. Comment déteminer parmi E lequel est juste avant x.
Au passage je suis sûr de moi quand je dis "c'est l'entier le plus proche de 3214 et lui étant inférieur, en prenant exactement les mêmes chiffres" ce n'est pas un scoop
Bon, je comprends pas bien. Je passe mon tour. Peut-être quelqu'un d'autre comprendra mieux que moi et sera plus patient.
une piste quand même d'après ce que je comprends : tu génères toutes les chaînes qui ont les même lettres, pour chaque chaîne tu calcules sa valeur et tu renvoies celle qui a le plus faible écart négatif avec la chaîne initiale.
Tu as bien compris, sauf que je cherche une fonction qui renvoie la chaine avec le plus faible écart négatif sans générer l'ensemble des chaînes qui seraient bien trop coûteux.
c'est pas l'ensemble des chaînes, c'est juste toutes les chaînes que l'on obtient par permutation de la première, il y en a n! , c'est pas très long pour une machine, même si la première chaîne est grande et vaut "anticonstitutionnellement".
Bonjour,
moi je comprends juste que on veut faire un bête tri sur les lettres de la chaine en les triant à partir de la fin de la chaine par ordre décroissant depuis la fin.
mais qu'on s'arrête au premier échange de lettres qu'on a fait lors de ce tri et qu'on ne va pas plus loin.
par exemples :
f("cbad") = "cadb"
par ordre lexicographique on a
abcd
...
cabd
cadb <---- f(x) le plus proche de cbad et juste avant par ordre lexicographique
cbad <---- x
cbda
...
dcba
cherchons à trier les lettres : en partant de la fin, le premier "dérangement" (deux lettres successives en ordre inverse) est
ad : OK, par ordre alphabétique
ba : dérangement donc je trie bad en adb
autre exemple plus démonstratif :
fcabde le premier dérangement est ca, je remplace le c par le plus petit de cabde qui est a,
c'est forcément la lettre qui suit le "pivot" c dans la chaine cabde puisque c'est le premier dérangement trouvé.
et je range le reste en ordre inverse : edcb en ordre de lettres décroissantes
facile puisque c'est juste inverser leur ordre actuel
faedcb
le suivant par ordre lexicographique de faedcb est bien fcabde
sauf erreurs de croisement d'yeux
y a plus qu'à ...
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :