lexikographische Sortierung

Question

Ich mache ein Problem, das sagt, dass „die Worte verketten die lexikographisch niedrigste mögliche Zeichenfolge zu generieren.“ von einem Wettbewerb.

Nehmen Sie zum Beispiel diese Zeichenfolge: jibw ji jp bw jibw

Die tatsächliche Ausgabe erweist sich als: bw jibw jibw ji jp

Wenn ich dies tun, Sortierung, erhalte ich:. bw ji jibw jibw jp

Bedeutet dies, dass dies das Sortieren nicht? Wenn es sortiert wird, bedeutet „lexicographic“ berücksichtigen Sortieren der kürzeren Saiten auf den Rücken oder etwas drängen?

Ich habe einige Lesung getan auf lexigographical bestellen und ich sehe keine Punkt oder Szenarien, auf denen diese verwendet werden, tun Sie welche haben?

Answer 1

Es scheint, dass für das, was Sie suchen ein besseres Verständnis für die Frage ist, so lassen Sie es mich nur klar machen. Die übliche Sortierung auf Zeichenketten is lexicographic Sortierung. Wenn Sie sortieren die Saiten [jibw, ji, jp, bw, jibw] in lexikographische Ordnung, die sortierte Sequenz is [bw, ji, jibw, jibw, jp], das ist, was du hast. Also Ihr Problem ist nicht das Wort mit Verständnis „lexicographic“; du es schon richtig verstanden.

Ihr Problem ist, dass Sie die Frage sind Verlesen. Die Frage ist nicht, dass Sie auf Art die Saiten in lexikographische Ordnung. (Wenn ja, die Antwort, die Sie durch die Sortierung bekam wäre richtig.) Stattdessen es Sie produzieren fragt ein string, bekam von Verkettungs die Eingabezeichenfolgen in einer bestimmten Reihenfolge ( das heißt, so dass eine Zeichenkette ohne Leerzeichen), so dass die resultierenden einzelne Zeichenfolge lexikographisch minimal ist.

Um den Unterschied zu verdeutlichen, sollten Sie die Zeichenfolge, die Sie erhalten, indem die sortierte Sequenz verketten, und die Antwort string:

bwjijibwjibwjp //Your answer
bwjibwjibwjijp //The correct answer

Wenn Sie nun diese beiden Strings vergleichen - beachten Sie, dass Sie vergleichen nur zwei 14-Zeichenketten, nicht zwei Sequenzen von Strings - Sie können sehen, dass die richtige Antwort in der Tat ist lexikographisch kleiner als Ihre Antwort: Ihre Antwort beginnt mit " bwjij“, während die richtige Antwort beginnt mit "bwjib" und "bwjib" kommt vor "bwjij" in lexikographische Ordnung.

Hope Sie die Frage verstehen jetzt. Es ist nicht eine Sortier Frage überhaupt. . (Das heißt, es ist kein Problem, die Eingabezeichenfolgen Sortier Sie könnte auf allen möglichen Strings muß Sortier bekommen durch Permutieren und Verkettung der Eingabezeichenfolgen, das ist eine Möglichkeit, das Problem zu lösen, wenn die Anzahl von Eingabeketten klein ist.)

Answer 2

Sie können diese in eine triviale Sortierproblem umwandeln, indem word1 Vergleich + word2 gegen word2 + word1. 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

Mit dieser Vergleichsfunktion mit der Standard-Art löst das Problem.

Answer 3

Ich habe mit F # in diesem Facebook Hacker Cup. ziemlich viel in diesem Wettbewerb gelernt. Da die Dokumentation auf F # auf dem Netz noch selten ist, ich glaube, ich könnte genauso gut hier ein wenig teilen.

Dieses Problem fordert Sie eine Liste von Strings auf einem angepassten Vergleichsverfahren zu sortieren. Hier ist mein Code-Schnipsel in 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

// Verwenden Sie diesen Codeblock lexikographisch sortiert Zeichen eines Arrays zu drucken oder es kann auf viele Arten verwendet werden.

  #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

Das Beispiel zeigt, dass Sie auf dem Laufenden nur die Sortierung der lexikographisch tiefsten Saite nicht erzeugen würde. Für das gegebene Problem, müßten Sie einigen zusätzlichen Trick anwenden, um zu bestimmen, welche Zeichenfolge vor dem kommen sollen (wie jetzt, kann ich nicht die genauen Methode denken)

Die tatsächliche Ausgabe verstößt nicht gegen die Bedingung für lexikografisch niedrigste Wort.

Answer 6

Der Sortier Befehl auf Linux funktioniert auch Lexikographische Sortier- und erzeugt die Ausgabe in der Reihenfolge bw ji jibw jibw jp

Answer 7

Überprüfen Sie, was hier passiert ist:

Wenn Sie nur eine lexicographic Art anwenden Sie erhalten bw ji jibw jibw jp aber wenn Sie mit dem Token analysieren Token Sie, dass „bwjibw“ finden (bw, jibw) ist lexicographicaly niedriger als „bwjijibw“ (bw, ji, jibw) Aus diesem Grund ist die Antwort bw jibw jibw ji jp weil zuerst sollten Sie bwjibwjibw anhängen und danach konnte man verketten ji und jp die tiefste Saite zu erhalten.

Answer 8

Ein einfacher Trick bei denen nur das Sortieren, die für dieses Problem zu umgehen wäre als die maximale Stringlänge angegeben ist, auf Pad würde alle Saiten bis max Länge mit dem ersten Buchstaben in der Zeichenkette. Dann sortieren Sie die gepolsterten Saiten, aber Ausgang die ursprünglichen unpadded diejenigen. Für ex. für String-Länge 2 und Eingänge b und ba Sie sortieren bb und ba würde, die Sie ba und bb geben würde, und daher sollten Sie Ausgabe bab.

Answer 9

Prasun Trick funktioniert, wenn Sie stattdessen Pad mit einem speziellen „Platzhalter“ Zeichen, das gewichtet werden könnte größer sein als „z“ in einer String-Sortierfunktion. Das Ergebnis würden Sie die Reihenfolge der niedrigsten lexicographic Kombination.

Answer 10

Der Wettbewerb ist vorbei, damit ich eine mögliche Lösung bin Entsendung, nicht die effizienteste, aber eine Möglichkeit, es zu tun,

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

Ich bin mit Algorithmen aus der STL-Bibliothek in C ++, die prev_permutation Funktion erzeugt einfach eine Permutation sortiert lexikografisch