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

Question

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

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

Фактический выходной сигнал оказывается: bw jibw jibw ji jp

Когда я делаю сортировку на этом, я получаю: 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

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

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

  #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

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

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

Answer 6

Команда сортировки в Linux также делает лексикографическую сортировку и генерирует вывод в порядке BW Ji Jibw Jibw JP

Answer 7

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

Если вы просто примените лексикографический вид, вы получите BW Ji Jibw Jibw JP, но если вы анализируете токен по токену, вы обнаружите, что «BWJIBW» (BW, JIBW) лексикографичен ниже, чем «BWJijibw» (BW, JI, JIBW) Вот почему ответ BW Jibw Jibw Ji JP, потому что сначала вы должны добавить BWJIBWJIBW и после этого вы могли бы объединить Ji и JP, чтобы получить самую низкую строку.

Answer 8

Простой трюк, включающий только сортировку, который будет работать для этой проблемы, так как указывается максимальная длина строки, будет прокладываться на все строки до максимальной длины с первой буквой в строке. Затем вы сортируете мягкие струны, но выведите оригинальные негруппированные. Для бывшего. Для длины строки 2 и входов B и BA вы бы сортируете BB и BA, который бы дал вам BA и BB, и, следовательно, вы должны выводить BOB.

Answer 9

Хитрость Prasun работает, если вы вместо этого накладываете специальный символ «заполнителя», который можно взвесить, чтобы быть больше, чем «Z» в функции сортировки строки. Результат даст вам порядок самых низких лексикографических комбинаций.

Answer 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 в C ++, функция Prev_Permution просто генерирует перестановку отсортированной лексикографически