clasificación lexicográfico

Question

Estoy haciendo un problema que dice "concatenar las palabras para generar la cadena lexicográfico más bajo posible." de una competencia.

Tomemos, por ejemplo, esta cadena: jibw ji jp bw jibw

La salida real resulta ser: bw jibw jibw ji jp

Cuando me clasificación en esto, me sale:. bw ji jibw jibw jp

¿Esto significa que este no es clasificando? Si se está clasificando, hace "lexicográfico" clasificación toma en consideración empujando las cadenas más cortas en la parte posterior o algo?

He estado leyendo sobre lexigographical fin y yo no veo ninguna punto o escenarios en los que se utiliza este, ¿tiene alguna?

Answer 1

Parece que lo que estás buscando es un mejor entendimiento de la cuestión, por lo que permítanme dejar claro. La clasificación habitual en las cadenas es clasificación lexicográfico. Si ordena las cadenas [jibw, ji, jp, BW, jibw] en orden lexicográfico, la secuencia ordenada es [BW, ji, jibw, jibw, jp], que es lo que tienes. Así que el problema no es con la comprensión de la palabra "lexicográfico"; ya entender correctamente.

Su problema es que usted está leyendo mal la pregunta. La pregunta no le pida a tipo las cadenas en orden lexicográfico. (Si así fuera, la respuesta que recibió por la clasificación sería correcta.) En su lugar, se le pide a los productos un string, tiene por concatenación las cadenas de entrada en un cierto orden ( es decir, haciendo una cadena sin espacios), de modo que la cadena sencilla resultante es lexicográficamente mínima.

Para ilustrar la diferencia, considere la cadena se obtiene concatenando la secuencia ordenada, y la cadena de respuesta:

bwjijibwjibwjp //Your answer
bwjibwjibwjijp //The correct answer

Ahora, cuando se comparan estas dos cadenas - Tenga en cuenta que usted está comparando dos cadenas de 14 caracteres, no dos secuencias de cadenas - se puede ver que la respuesta correcta es, en efecto lexicográfico más pequeño que su respuesta: la respuesta comienza con " bwjij", mientras que la respuesta correcta comienza con 'bwjib', y 'bwjib' viene antes de 'bwjij' en orden lexicográfico.

esperamos que entienda la pregunta ahora. No es una cuestión de clasificación en absoluto. . (Es decir, no es un problema de la clasificación de las cadenas de entrada You podría do la clasificación de todas las cadenas posibles tiene permutando y la concatenación de las cadenas de entrada; esta es una manera de resolver el problema si el número de cadenas de entrada es pequeño.)

Answer 2

Se puede convertir esto en un problema trivial clasificación comparando palabra1 + palabra2 contra palabra2 + palabra1. 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

El uso de esta función de comparación con los resuelve ordenar el problema estándar.

Answer 3

He estado usando C # en esta copa hacker de Facebook. Aprendido bastante en esta competición. Dado que la documentación sobre F # en la web es todavía escasa, creo que también podría compartir un poco aquí.

Este problema se solicita para ordenar una lista de cadenas a base de un método de comparación personalizada. Aquí está mi fragmento de código en C #.

    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

// Usar este bloque de código para imprimir caracteres lexicográfico ordenados de una matriz o se puede utilizar de muchas maneras.

  #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

El ejemplo que ha escrito muestra que la mera clasificación no generaría la cadena lexicográfico más bajo. Para el problema dado, lo que tendría que aplicar un poco de truco adicional para determinar qué cadena debe venir antes de la cual (a partir de ahora, no puedo pensar en el método exacto)

La salida real no viola la condición por palabra lexicográfico más bajo.

Answer 6

El comando sort en Linux también hace ordenación lexicográfica y genera la salida en el orden de peso corporal ji jibw jibw JP

Answer 7

Check what happened here:

If you just apply a lexicographic sort you'll get bw ji jibw jibw jp but if you analyze token by token you'll find that "bwjibw" (bw, jibw) is lexicographicaly lower than "bwjijibw" (bw, ji, jibw) that's why the answer is bw jibw jibw ji jp because first you should append bwjibwjibw and after that you could concatenate ji and jp to get the lowest string.

Answer 8

A simple trick involving only sorting, which would work for this problem as the max string length is specified, would be to pad all strings up to max length with the first letter in the string. Then you sort the padded strings, but output the original unpadded ones. For ex. for string length 2 and inputs b and ba you would sort bb and ba which would give you ba and bb, and hence you should output bab.

Answer 9

Prasun's trick works if you instead pad with a special "placeholder" character that could be weighted to be greater than "z" in a string sort function. The result would give you the order of lowest lexicographic combination.

Answer 10

The contest is over so I am posting a possible solution, not the most efficient but one way of doing it

 #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;
  }

I am using algorithms from the STL library in c++, the prev_permutation function simply generates a permutation sorted lexicographically