Лексикографическая сортировка

Ответ 1

Кажется, что то, что вы ищете, - это лучшее понимание вопроса, поэтому позвольте мне просто дать понять. Обычная сортировка по строкам - лексикографическая сортировка. Если сортировать строки [jibw, ji, jp, bw, jibw] в лексикографическом порядке, отсортированная последовательность - [bw, ji, jibw, jibw, jp], что и есть то, что вы получили. Поэтому ваша проблема заключается не в понимании слова "лексикография"; вы уже правильно это поняли.

Ваша проблема в том, что вы неправильно читаете вопрос. Вопрос не требует сортировки строк в лексикографическом порядке. (Если бы это было так, ответ, который вы получили путем сортировки, был бы правильным.) Вместо этого он просит вас создать одну строку, полученную путем конкатенации входных строк в некотором порядке (т.е. Создание одной строки без пробелов), чтобы получившийся сингл строка лексикографически минимальна.

Чтобы проиллюстрировать разницу, рассмотрите строку, которую вы получаете, объединив отсортированную последовательность и строку ответа:

bwjijibwjibwjp //Your answer
bwjibwjibwjijp //The correct answer

Теперь, когда вы сравниваете эти две строки - обратите внимание, что вы просто сравниваете две строки из 14 символов, а не две последовательности строк - вы можете видеть, что правильный ответ действительно лексикографически меньше вашего ответа: ваш ответ начинается с "bwjij", тогда как правильный ответ начинается с "bwjib", а "bwjib" предшествует "bwjij" в лексикографическом порядке.

Надеюсь, ты сейчас поймешь вопрос. Это не вопрос сортировки. (То есть, это не проблема сортировки входных строк. Вы можете сортировать по всем возможным строкам, полученным путем перестановки и конкатенации входных строк, это один из способов решения проблемы, если количество входных строк невелико.)

Ответ 2

Вы можете преобразовать это в тривиальную проблему сортировки, сравнив word1 + word2 с word2 + word1. В 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

Использование этой функции сравнения со стандартной сортировкой решает проблему.

Ответ 3

Я использую F # в этой хакерской чашке Facebook. Выучил немного в этом соревновании. Поскольку документация по F # в Интернете все еще редка, я думаю, что я мог бы также немного поработать здесь.

Эта проблема требует, чтобы вы отсортировали список строк на основе настроенного метода сравнения. Вот мой фрагмент кода в 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

Ответ 4

//Используйте этот блок кода для печати лексикографически отсортированных символов массива или его можно использовать разными способами.

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

Ответ 5

В приведенном примере показано, что простая сортировка не создавала бы лексикографически минимальную строку. Для данной проблемы вам нужно применить некоторый дополнительный трюк, чтобы определить, какая строка должна быть до этого (на данный момент я не могу придумать точный метод)

Фактический вывод не нарушает условия для лексикографически младшего слова.

Ответ 6

Команда sort на linux также выполняет сортировку по лексикографическим данным и генерирует вывод в порядке bw ji jibw jibw jp

Ответ 7

Проверьте, что произошло здесь:

Если вы просто примените лексикографическую сортировку, вы получите bw ji jibw jibw jp но если вы проанализируете токен с помощью токена, вы обнаружите, что "bwjibw" (bw, jibw) лексикографически ниже, чем "bwjijibw" (bw, ji, jibw), поэтому для ответа является bw jibw jibw ji jp, потому что сначала вы должны добавить bwjibwjibw и после этого вы можете объединить ji и jp, чтобы получить самую низкую строку.

Ответ 8

Простой трюк, включающий только сортировку, которая будет работать для этой проблемы с максимальной длиной строки, будет состоять в том, чтобы заполнить все строки до максимальной длины первой буквой в строке. Затем вы сортируете заполненные строки, но выводите оригинальные незакрепленные. Напр. для длины строки 2 и входов b и ba вы бы сортировали bb и ba, которые давали бы вам ba и bb, и, следовательно, вы должны выводить баб.

Ответ 9

Трюк Prasun работает, если вы вместо этого используете специальный символ "placeholder", который может быть взвешен, чтобы быть больше, чем "z" в функции сортировки строк. Результат даст вам порядок наименьшей лексикографической комбинации.

Ответ 10

Конкурс завершен, поэтому я публикую возможное решение, а не самый эффективный, но один из способов сделать это.

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

Я использую алгоритмы из библиотеки STL в С++, функция prev_permutation просто генерирует перестановку, отсортированную лексикографически