Petit problème de tri

[Good07]

Bonjour à tous.

Voilà, j'ai un petit problème de tri, et je ne sait pas comment le résoudre.
Bon un petit exemple valant mieux qu'un long discours, voici le programme que j'utilise:

Code : Tout sélectionner

Clef$="UNPEIGNEUNPEIGNE"
long=Len(Clef$)
Global Dim tableclef$(Len(Clef$))
Global Dim TableCrypto$(9,long+1)
Crypto$="SOTPECHEURALEMBOUCHUREDURHONESONPOISSONSURLEGRILDEUXFOISRETOURNA"
For n=1 To long
  tableclef$(n)=Mid(Clef$,n,1)+Str(n)
  Debug tableclef$(n)
Next n
Debug "------------------------------"
SortArray(tableclef$(),0)
For n=1 To long
  Debug tableclef$(n)
Next n

Bon maintenant, une petite explication. Il s'agit de trier un tableau de lettres rempli avec un mot clef qui peut être plus ou moins long. Dans cet exemple il s'agit de "UNPEIGNEUNPEIGNE". Pour faire simple, et pour éviter de trier en plus un tableau d'index, j'associe directement l'index à la lettre et ensuite je tri.
Le problème se situe au niveau des lettres identiques. Par exemple l'index après le tri est celui-ci:
12/16/4/8/14/6/13/5/10/15/2/7/11/3/1/9 alors qu'il devrait-être:
4/8/12/16/6/14/5/13/2/7/10/15/3/11/1/9

Les lettres devant-être relevées de la gauche vers la droite en respectant l'ordre alphabétique. Bien sur il faudrai alors effectuer un deuxième tri sur les lettres de même valeur... Mais cela risque de compliquer pas mal la chose...
Avez-vous une autre solution ?
Autre question. Est-il possible en Pure de commencer un tableau à l'indice 1 au lieu de zéro ? Si mes souvenirs sont exacts en Basic GFA on utilisait Option Base 0 ou Option Base 1. Impossible de trouver en Pure... Mais j'ai peut-être manqué une option. Si oui, il serai souhaitable de la rajouter dans la doc avec l'option DIM.
Merci d'avance pour vos réponses.

[Backup]

pour l'option base, moi c'est souvent que j'ai un element vide en debut de tableau, car je part de 1 , l'element 0 si t'en tien pas compte, c'est pas bien grave , tu perd un peut de Ram, mais c'est vrais que c'est plus simple certaines fois


pour ton blem de trie, c'est chaud !!, j'ai essayé, mais sans resultats
il faudrai re-annalyser le premier resultat , en mettant ensemble
les "E" , les "S" ect.. pour faire des trie dans le trie , c'est chaud a faire, a mon avis

[Good07]

Bonjour Dobro.

Merci pour ta réponse.Je vois que les anciens du GFA se serrent toujours les coudes.

Bah. Moi je croyais que Pure avait aussi cette fonction. Enfin comme tu le dis ce n'est pas bien grave, mais j'ai toujours du mal avec la case zéro. Quelquefois le programme à un comportement bizarre quand on ne l'utilise pas.
Pour le tri, je vois que tu en arrive à la même conclusion que moi. Il faudrai faire un deuxième tri en tenant compte des valeurs identiques de lettres et en triant cette fois-ci les indexs par ordre de grandeur.
Pas facile...
Je vais essayé une autre approche avec un tri par sélection.(On prend la première case du tableau et on la compare avec la suivante. Si elle est plus grande on permute, et ce jusqu'à la fin du tableau) ça devrait peut-être donner un meilleur résultat.

A suivre.

[Good07]

Toute mes excuses pour la fausse manip, je voulais corriger la clef qui comportait une erreur sur mon premier post et j'ai tout renvoyé.
Bon c'est pas grave, l'ordre de la clef est bon sur ce post et je l'ai corrigé aussi sur le premier.
Pour ce qui est du tri par sélection, il donne un meilleur résultat au début mais je ne comprend pas pourquoi il y a encore des inversions
voici le programme:

Code : Tout sélectionner

Global long
Clef$="UNPEIGNEUNPEIGNE"
long=Len(Clef$)
Global Dim tableclef$(long)
Global Dim index(long)

For n=1 To long
  tableclef$(n)=Mid(Clef$,n,1)
  index(n)=n
  Debug tableclef$(n)+" "+Str(index(n))
Next n
Procedure trie()
For I=1 To long-1
  For j=I+1 To long
  If tableclef$(j)<tableclef$(I)
    AA$=tableclef$(j)
    Swap tableclef$(j),tableclef$(I)
    Swap index(j),index(I)
    tableclef$(I)=AA$
  EndIf
  Next j
Next I
EndProcedure

  
Debug "------------------------------"
trie()
For n=1 To long
  Debug index(n)
Next n

Cette fois-ci j'ai utilisé un tableau d'index car je me suis aperçu que ma première méthode semblait interférer sur l'ordre du tri. E12 semble différent de E4 par exemple et en plus ça semble logique.
Il doit bien exister une solution

[Good07]

Ca Marche !!!

Bon je suis arrivé à résoudre le problème en utilisant deux procedures de tri légèrement différentes. La première tri le tableau de lettres et le tableau d'index et la seconde compare le tableau de lettre et le tableau d'index et permute l'index si il n'est pas dans le bon ordre. Voici le programme:

Code : Tout sélectionner

Global long
Clef$="UNPEIGNEUNPEIGNE"
long=Len(Clef$)
Global Dim tableclef$(long)
Global Dim index(long)

For n=1 To long
  tableclef$(n)=Mid(Clef$,n,1)
  index(n)=n
  Debug tableclef$(n)+" "+Str(index(n))
Next n

Procedure tri()
For I=1 To long-1
  For j=I+1 To long
  If tableclef$(j)<tableclef$(I)
    AA$=tableclef$(j)
    Swap tableclef$(j),tableclef$(I)
    Swap index(j),index(I)
    tableclef$(I)=AA$
  EndIf
  Next j
Next I
EndProcedure

Procedure tri2()
For I=1 To long-1
  For j=I+1 To long
  If tableclef$(j)=tableclef$(I) And index(j)<index(I)
    Swap index(j),index(I)
  EndIf
  Next j
Next I
EndProcedure  
Debug "------------------------------"
tri()
For n=1 To long
  Debug index(n)
Next n
Debug "------------------------------"
tri2()
For n=1 To long
  Debug index(n)
Next n

Je ne sais pas si on peu faire autrement, la mienne fonctionne même si elle ne me plait pas trop. Si vous avez une autre idée, elle est la bienvenue.

[Backup]

Bravo !
désolé de ne pas avoir pu consacrer plus de temps a ce probleme,
j'aurai bien aimé avoir le temps , mais en ce moment c'est short
en tout cas encore Bravo,pour la solution, je voyais ça mal barré

[Good07]

Merci Dobro

La solution n'est pas très élégante (2 procédures...) mais elle a le mérite de fonctionner.
J'étudie toujours le problème mais comme je n'ai pas trop de temps non plus sa risque de durer.

[brossden]

J'ai peut être une solution à ton problème mais je ne vois pas ce que vient faire les deux lignes
- Global Dim TableCrypto$(9,long+1)
- Crypto$="SOTPECHEURALEMBOUCHUREDURHONESONPOISSONSURLEGRILDEUXFOISRETOURNA"

Code : Tout sélectionner

Clef$="UNPEIGNEUNPEIGNE"
long=Len(Clef$)
Global Dim tableclef$(Len(Clef$))
Global Dim TableCrypto$(9,long+1)
Crypto$="SOTPECHEURALEMBOUCHUREDURHONESONPOISSONSURLEGRILDEUXFOISRETOURNA"
For n=1 To long
  tableclef$(n)=Mid(Clef$,n,1)+RSet(Str(n),3," ") ; <<<<<<< Seule modif avec Rset !!
  Debug tableclef$(n)
Next n
Debug "------------------------------"
SortArray(tableclef$(),0)
For n=1 To long
  Debug tableclef$(n)
Next n 

Désolé de n'avoir répondu plus tôt je n'avais pas vu ce post !

[Good07]

Bonjour Brossden.

Merci de te pencher sur le problème.

En fait ces deux lignes font parti d'un programme beaucoup plus long et je n'ai extrait que celles qui me posaient un problème de conception.
Donc n'en tient pas compte, elles ne servent à rien dans l'exemple.
J'aurai du les supprimer. Désolé.

[brossden]

As tu vu que je t'ai quand même mis ma solution !

[Good07]

Décidément, Je me fais vieux.

Désolé Brossden, je n'avais même pas vu que tu avais mis la solution. J'ai testé en plus ça marche nickel.
Un grand merci pour ton intervention. Y a pas à dire ça fait quand même plus pro que les deux procédures que j'avais faite.

[brossden]

Mais je pense que le petit code ci dessous est plus proche de ce que tu appelles "PRO"

Code : Tout sélectionner

Clef.s="UNPEIGNEUNPEIGNE"
NewList Car.s()
For n = 1 To Len(Clef)
  AddElement(Car())
  Car() = Mid(Clef,n,1)+RSet(Str(n),3," ")
Next
SortList(Car(),0)
ForEach Car()
  txt.s + Car()+Chr(13)
Next
MessageRequester("Liste des éléments",txt)

[Good07]

Super !

Je te remercie pour ce nouveau code. En fait je programme souvent des plats de spaghettis et je suis émerveillé par ce que vous arrivez à faire en quelques lignes alors que moi il m'en faut souvent le double ou le triple pour faire la même chose.

Mais à la fin je suis fier que ça fonctionne comme je veux.

Y'a pas à dire, les listes c'est quand même une belle invention. Il va falloir que je m'y mette sérieusement.

En fait pour moi, "PRO" cela voulais dire plus concis.

Mais avec ton code, je doute que l'on puisse faire mieux.

[brossden]

Il n'y a rien de super c'est l'habitude et l'expérience qui permet d'arriver à rendre plus concis les algos, tu y arriveras quand tu auras bien pris en main purebasic et glané des astuces ici et là !

Mais si tu veux pousser un peu plus :

Code : Tout sélectionner

Global FontID1,Txt.s, Position.s, Lettre.s, nbr, rc.s=Chr(13), S.s

OpenWindow(0, 10, 40, 700, 420, "Résultats",  #PB_Window_SystemMenu | #PB_Window_SizeGadget | #PB_Window_TitleBar )
CreateGadgetList(WindowID(0))
EditorGadget(1, 10, 10, 680, 400)
SetGadgetFont(1, LoadFont(1, "Courier New", 9,#PB_Font_Bold  ))

NewList Car.s()
Clef$="SOTPECHEURALEMBOUCHUREDURHONESONPOISSONSURLEGRILDEUXFOISRETOURNAUNPEIGNEUNPEIGNE"
x = PeekC(@Clef$+n)
While x
  AddElement(Car())
  Car() = Chr(x)+RSet(Str(n+1),6," ")
  n+1
  x = PeekC(@Clef$+n)
Wend
SortList(Car(),0)
ret =FirstElement(Car())
Lettre.s=Left(Car(),1)
Position.s = ""
nbr=0

ForEach Car()
  If Lettre.s = Left(Car(),1)
    Position +Trim(Right(Car(),6))+"," 
    nbr+1
  Else
    If nbr>1
      S="s : "
    Else
      S="  : "
    EndIf
    Txt + "Lettre : "+Lettre +" "+ " Nombre : "+RSet(Str(nbr),2," ") +"  Position" +S+Left(Position,Len(Position)-1)+ rc
    Lettre.s = Left(Car(),1)
    Position = Trim(Right(Car(),6))+","
    nbr=1
  EndIf
Next
Txt = rc + "Texte d'origine :" +rc+rc+">> "+ Clef$+ " <<" + rc + rc + Txt
SetGadgetText(1,Txt)
Repeat ; Start of the event loop
  Event = WaitWindowEvent() 
Until Event = #PB_Event_CloseWindow ; End of the event loop

[Good07]

Bonjour Brossden.

Désolé de te répondre si tard, mais je part au boulot à 04h et et je rentre vers 14 h. De plus nous n'avons pas internet au travail, seulement un réseau propre à l'entreprise.
Beau travail, même si il sort du cadre de ce que je voulais faire. Je vais garder ça sous le coude car je pense que cela va quand même me servir. En fait j'étudie les méthodes de chiffrement et déchiffrement utilisée à la fin du 19e siècle et le programme que je fait, sert à lire une phrase clef qui va servir à mélanger un texte avant son chiffrement par ex:
12345678
UNPEIGNE
SOTPECHE
URALEMBO
UCHUREDU
RHONESON
POISSONS
URLEGRIL
DEUXFOIS
RETOURNA

Désolé, les colonnes sont mal alignées, mais en fait on rempli un tableau dont le nombre de colonnes est égal à la longueur de la clef.
Ensuite on relève le texte par colonne en tenant compte de l'ordre alphabétique des lettres de la clef. Ce qui donne la clef suivante:

4,8,6,5,2,7,3,1 et le texte suivant:

EERESGFUEEOUNSLSACMESOROREERESGFUORCHOREEHBDONIINTAHOILUTUSUURPURDR

Il ne reste plus qu'a chiffrer ce texte avec un procédé quelconque (Vigenère, Beaufort etc...)
Bien sur, au déchiffrement, il faut employer la méthode inverse...
Mais comme le déchiffreur à besoin d'un maximum de renseignement sur le cryptogramme pour l'orienter sur la méthode de chiffrement je pense que ton petit programme va me servir.
En fait je butais simplement sur le tri de la clef pour conserver l'ordre alphabétique de lecture des colonnes du tableau.
Mais maintenant plus de problèmes ! Merci encore pour tout ces exemples.