ordinamento lessicografico

Question

che sto facendo un problema che dice "concatenare le parole per generare la stringa di lessicografico più basso possibile." da un concorso.

Prendiamo ad esempio questa stringa: jibw ji jp bw jibw

L'uscita effettiva risulta essere: bw jibw jibw ji jp

Quando faccio l'ordinamento su questo, ottengo:. bw ji jibw jibw jp

Questo significa che questo non è l'ordinamento? Se è l'ordinamento, significa "lessicografico" ordinamento prendere in considerazione spingendo le corde più corte sul retro o qualcosa del genere?

Ho fatto qualche lettura su lexigographical ordine e non vedo alcun punto o scenari in cui la presente viene usato, hai qualche?

Answer 1

Sembra che quello che stai cercando è una migliore comprensione della questione, quindi vorrei solo mettere in chiaro. L'ordinamento di consueto sulle stringhe è ordinamento lessicografico. Se si ordina le stringhe [jibw, ji, jp, bw, jibw] in ordine lessicografico, la sequenza ordinata è [BW, ji, jibw, jibw, jp], che è quello che avete ottenuto. Quindi il problema non è con la comprensione del termine "lessicografico"; hai già capito correttamente.

Il tuo problema è che si sta fraintendendo la domanda. La questione non si chiede di sort le stringhe in ordine lessicografico. (Se così fosse, la risposta avete ottenuto di classificare gli sarebbe corretto.) Invece, si chiede di produrre una string, ottenuto da concatenamento le stringhe di input in un certo ordine ( Per esempio, facendo una stringa senza spazi), in modo che la singola stringa risultante è lexicographically minimo.

Per illustrare la differenza, si consideri la stringa che si ottiene concatenando sequenza ordinata, e la stringa di risposta:

bwjijibwjibwjp //Your answer
bwjibwjibwjijp //The correct answer

Ora, quando si confrontano questi due stringhe - nota che sei solo il confronto di due stringhe di 14 caratteri, non due sequenze di stringhe - si può vedere che la risposta corretta è infatti lexicographically più piccolo della tua risposta: i tuoi risposta inizia con " bwjij", mentre le risposte corrette inizia con "bwjib", e "bwjib" viene prima "bwjij" in ordine lessicografico.

Spero che tu capisca la questione ora. Non è una questione di smistamento a tutti. . (Cioè, non è un problema di ordinare le stringhe di input È potrebbero do l'ordinamento su tutte le possibili stringhe ottenuto permutando e concatenando le stringhe di input; questo è un modo di risolvere il problema se il numero di stringhe di input è piccolo.)

Answer 2

È possibile convertire questo in un problema di ordinamento banale confrontando parola1 + parola2 contro parola2 + parola1. In 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

Usando questa funzione di confronto con i normali risolve il problema di ordinamento.

Answer 3

ho usato F # in questa tazza di hacker Facebook. Imparato un po 'in questa competizione. Dal momento che la documentazione su F # sul web è ancora raro, penso che potrei anche condividere un po 'qui.

Questo problema si chiede di ordinare un elenco di stringhe sulla base di un metodo di confronto personalizzato. Ecco il mio frammento di codice in 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

// Utilizzare questo blocco di codice per stampare caratteri lessicografico ordinati di un array o può essere utilizzato in molti modi.

  #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'esempio si ha postato mostra che mero smistamento non generare la stringa lessicografico più basso. Per il problema dato, si avrebbe bisogno di applicare particolari accorgimenti per determinare quale stringa deve venire prima che (a partire da ora, non mi viene in mente il metodo esatto)

L'uscita effettiva non viola la condizione per parola lessicografico più basso.

Answer 6

Il comando sort su Linux fa anche smistamento Lexicographic e genera l'uscita nell'ordine bw ji jibw jibw jp

Answer 7

Controlla ciò che è accaduto qui:

Se hai appena applica un ordinamento lessicografico si otterrà peso corporeo ji jibw jibw jp ma se si analizza simbolici con gettone ci si accorge che "bwjibw" (BW, jibw) è lexicographicaly inferiore a "bwjijibw" (peso corporeo, ji, jibw) che è il motivo per cui la risposta è di peso corporeo jibw jibw ji jp perché prima si deve accodare bwjibwjibw e dopo che si potrebbe concatenare ji e JP per ottenere la corda più bassa.

Answer 8

Un trucco semplice che coinvolge solo l'ordinamento, che avrebbe funzionato per questo problema, come è specificato la lunghezza massima della stringa, sarebbe quello di pad tutte le stringhe fino a lunghezza massima con la prima lettera della stringa. Poi si ordinano le corde imbottiti, ma la produzione non imbottiti quelli originali. Per es. per la lunghezza della stringa 2 e ingressi b and ba si ordina bb e ba che darebbe ba e bb, e quindi si deve emettere bab.

Answer 9

il trucco di Prasun funziona se invece pad con un carattere speciale di "segnaposto" che potrebbe essere ponderati per essere maggiore di "z" in una funzione di stringa sorta. Il risultato darebbe l'ordine di basso combinazione lessicografico.

Answer 10

Il concorso è finita così sto inviando una possibile soluzione, non il più efficiente, ma un modo di farlo

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

Sto usando algoritmi dalla libreria STL in C ++, la funzione prev_permutation genera semplicemente una permutazione ordinata lessicografico