tri lexicographique

Question

Je fais un problème qui dit « concaténer les mots pour générer la corde la plus grave possible lexicographique. » d'un concours.

Prenons par exemple cette chaîne: jibw ji jp bw jibw

La sortie réelle se révèle être: bw jibw jibw ji jp

Quand je fais le tri sur ce point, je reçois. bw ji jibw jibw jp

Est-ce que cela signifie que ce ne soit pas le tri? Si elle est le tri, ne « lexicographique » tri prendre en considération pousser les chaînes plus courtes à l'arrière ou quelque chose?

Je fais un peu de lecture sur lexigographical ordre et je ne vois pas de points ou scénarios sur lesquels il est utilisé, avez-vous une?

Answer 1

Il semble que ce que vous cherchez est une meilleure compréhension de la question, alors laissez-moi juste qu'il soit clair. Le tri d'habitude sur les chaînes tri lexicographique. Si vous triez les chaînes [jibw, ji, jp, pc, jibw] dans l'ordre lexicographique, la séquence triée [pc, ji, jibw, jibw, jp], qui est ce que tu as. Donc, votre problème n'est pas à comprendre le mot « lexicographique »; vous comprenez déjà correctement.

Votre problème est que vous êtes une mauvaise interprétation de la question. La question ne vous demande pas de trier les chaînes dans l'ordre lexicographique. (Si elle l'a fait, la réponse que vous avez obtenu par le tri serait correct.) Au lieu de cela, il vous demande de produire un string, obtenu par concaténer les chaînes d'entrée dans un ordre ( à savoir, ce qui rend une chaîne sans espaces), de sorte que la seule chaîne résultante est lexicographique minimale.

Pour illustrer la différence, pensez à la chaîne que vous obtenez en enchaînant la séquence triée, et la chaîne de réponse:

bwjijibwjibwjp //Your answer
bwjibwjibwjijp //The correct answer

Maintenant, quand vous comparez ces deux chaînes - note que vous êtes juste comparaison de deux chaînes de 14 caractères, pas deux séquences de chaînes - vous pouvez voir que la réponse correcte est en effet lexicographique plus petit que votre réponse: le début de votre réponse avec " bwjij », alors que le début de la réponse correcte avec « bwjib » et « bwjib » vient avant « bwjij » dans l'ordre lexicographique.

espère que vous comprenez maintenant la question. Il n'est pas une question de tri du tout. . (C'est, ce n'est pas un problème de tri des chaînes d'entrée Vous peut ne tri sur toutes les chaînes possibles obtenu en permutant et concaténer les chaînes d'entrée, ce qui est une façon de résoudre le problème si le nombre des chaînes d'entrée est faible.)

Answer 2

Vous pouvez convertir en un problème de tri trivial en comparant mot1 + mot2 contre + mot2 mot1. En Python:

def cmp_concetanate(word1, word2):
    c1 = word1 + word2
    c2 = word2 + word1
    if c1 < c2:
        return -1
    elif c1 > c2:
        return 1
    else:
        return 0

En utilisant cette fonction de comparaison avec les tri standard permet de résoudre le problème.

Answer 3

Je me sers de F # dans cette tasse de pirate Facebook. J'ai appris un peu dans cette compétition. Étant donné que la documentation sur F # sur le web est encore rare, je pense que je pourrais aussi bien partager un peu ici.

Ce problème vous demande de trier une liste de chaînes basées sur une méthode de comparaison personnalisée. Voici mon extrait de code F #.

    let comparer (string1:string) (string2:string) =
         String.Compare(string1 + string2, string2 + string1)

    // Assume words is an array of strings that you read from the input
    // Do inplace sorting there
    Array.sortInPlaceWith comparer words
    // result contains the string for output
    let result = Array.fold (+) "" words

Answer 4

// Utilisez ce bloc de code pour imprimer des caractères lexicographique classés d'un tableau ou il peut être utilisé de plusieurs façons.

  #include<stdio.h>
  #include<conio.h>

  void combo(int,int,char[],char[],int*,int*,int*);

  void main()
  {
      char a[4]={'a','b','c'};
      char a1[10];
      int i=0,no=0;
      int l=0,j=0;
      combo(0,3,a,a1,&j,&l,&no);
      printf("%d",no);
      getch();
  }
  void combo(int ctr,int n,char a[],char a1[],int*j,int*l,int*no)
  {
      int i=0;
      if(ctr==n)
      {
        for(i=0;i<n;i++)
            printf("%c",a1[i]);
        printf("\n");
        (*no)++;
        (*j)++;
        if((*j)==n)
        { 
            *l=0;
             *j=0;
        }
        else
        *l=1;       
        getch();
      }
      else
        for(i=0;i<n;i++)
        {
        if(*l!=1)
            *j=i;
        a1[ctr]=a[*j];
        combo(ctr+1,n,a,a1,j,l,no);
        }
    }

Answer 5

L'exemple que vous avez affichée montre que le simple tri ne générerait pas la corde la plus grave lexicographique. Pour le problème donné, vous auriez besoin d'appliquer une astuce supplémentaire pour déterminer quelle chaîne doit venir devant laquelle (à partir de maintenant, je ne peux pas penser à la méthode exacte)

La sortie réelle ne viole pas la condition pour mot lexicographique plus bas.

Answer 6

La commande sort sur Linux fait aussi le tri lexicographique et génère la sortie dans l'ordre de poids corporel ji jibw jibw jp

Answer 7

Vérifier ce qui est arrivé ici:

Si vous appliquez simplement une sorte lexicographique que vous obtiendrez bw ji jibw jibw jp mais si vous analysez jeton par jeton, vous trouverez que « bwjibw » (pc, jibw) est inférieure lexicographicaly que « bwjijibw » (pc, ji, jibw) qui est la raison pour laquelle la réponse est bw jibw jibw ji jp parce que d'abord, vous devez ajouter bwjibwjibw et après que vous pourriez concatenate ji et jp pour obtenir la corde la plus grave.

Answer 8

Un truc simple impliquant seulement le tri, qui travaillerait pour ce problème comme la longueur de chaîne maximale est spécifiée, serait pad toutes les chaînes jusqu'à longueur max avec la première lettre dans la chaîne. Ensuite, vous triez les cordes rembourrées, mais sortie les unpadded d'origine. Ex. pour une longueur de chaîne 2 et entrées b et ba vous trierait bb et ba qui vous donnera ba et bb, et donc vous devriez bab de sortie.

Answer 9

truc de Prasun fonctionne si vous pad à la place d'un caractère spécial « espace réservé » qui pourraient être pondérées pour être supérieur à « z » dans une fonction de tri de chaîne. Le résultat vous donnera l'ordre de la plus faible combinaison lexicographique.

Answer 10

Le concours est terminé donc je posterai une solution, pas la plus efficace, mais une façon de le faire

 #include <iostream>
 #include <fstream>
 #include <string>
    #include <algorithm>
    using namespace std;
   int main()
  {
ofstream myfile;
myfile.open("output.txt");
int numTestCases;
int numStrings;
string* ptr=NULL;
char*ptr2=NULL;
string tosort;
scanf("%d",&numTestCases);
for(int i=0;i<numTestCases;i++)
{
    scanf("%d",&numStrings);
    ptr=new string[numStrings];
    for(int i=0;i<numStrings;i++)
    {
        cin>>ptr[i];
    }
    sort(ptr,ptr+numStrings);
    for(int i=0;i<numStrings;i++)
    {
        next_permutation(ptr,ptr+numStrings);
    }
    tosort.clear();
    for(int i=0;i<numStrings;i++)
    {
        tosort.append(ptr[i]);
    }
    ptr2=&tosort[i];

    cout<<tosort<<endl;
    myfile<<tosort<<endl;   
    delete[]ptr;
}
return 0;
  }

J'utilise des algorithmes de la bibliothèque STL en C ++, la fonction génère prev_permutation simplement une permutation lexicographique triée