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

Question

Я делаю задачу, которая гласит «объединить слова, чтобы сгенерировать лексикографически минимально возможную строку».из соревнования.

Возьмем, к примеру, эту строку: jibw ji jp bw jibw

Фактический результат получается следующим образом: bw jibw jibw ji jp

Когда я делаю сортировку по этому, яget: bw ji jibw jibw jp.

Значит ли это, что это не сортировка?Если это сортировка, учитывает ли «лексикографическая» сортировка толкание более коротких строк назад или что-то в этом роде?

Я читал лексикографический порядок , а я нетувидеть какие-либо точки или сценарии, в которых это используется, у вас есть какие-либо?

Answer 1

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

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

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

bwjijibwjibwjp //Your answer
bwjibwjibwjijp //The correct answer

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

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

Answer 2

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

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

Answer 4

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

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

Answer 5

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

 #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 в c ++, функция prev_permutation просто генерирует перестановку, отсортированную лексикографически

Answer 6

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

Answer 7

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

Answer 8

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

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

Answer 9

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

Answer 10

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

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