词典排序

Question

我正在做一个问题，说“连接单词以生成字典顺序最低的可能字符串”。来自一场比赛。

以这个字符串为例： jibw ji jp bw jibw

实际输出结果是： bw jibw jibw ji jp

当我对此进行排序时，我得到： bw ji jibw jibw jp。

这是否意味着这不是排序？如果是排序，“字典顺序”排序是否考虑将较短的字符串推到后面或其他什么？

我一直在阅读词典顺序，但我没有看到任何要点或场景这个是用在什么上面的，你有吗？

Answer 1

您发布的示例表明，仅排序不会生成字典顺序最低的字符串。
对于给定的问题，您需要应用一些额外的技巧来确定哪个字符串应该出现在哪个字符串之前（到目前为止，我想不出确切的方法）

实际输出不会违反字典顺序最低单词的条件。

Answer 2

Linux 上的 sort 命令也进行字典排序并按 bw ji jibw jibw jp 的顺序生成输出

Answer 3

检查这里发生了什么：

如果你只是应用字典排序，你会得到 bw ji jibw jibw jp
但是如果你逐个分析令牌，你会发现“bwjibw”（bw，jibw）在字典顺序上低于“bwjijibw”（bw，ji，jibw），这就是为什么答案是bw jibw jibw ji jp，因为首先你应该附加bwjibwjibw之后，您可以连接 ji 和 jp 以获得最低的字符串。

Answer 4

一个仅涉及排序的简单技巧（在指定最大字符串长度时适用于解决此问题）是将所有字符串填充到字符串中的第一个字母，使其达到最大长度。然后对填充的字符串进行排序，但输出原始的未填充的字符串。对于前。对于字符串长度为 2 且输入 b 和 ba，您将对 bb 和 ba 进行排序，这将得到 ba 和 bb，因此您应该输出 bab。

Answer 5

如果您使用特殊的“占位符”字符进行填充，该字符可以在字符串排序函数中加权为大于“z”，那么 Prasun 的技巧就会起作用。结果将为您提供最低词典组合的顺序。

Answer 6

比赛结束了，所以我发布了一个可能的解决方案，不是最有效的，而是一种方法，

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

我使用 C++ 中的 STL 库中的算法， prev_permutation 函数只是生成按字典顺序排序的排列

Answer 7

看来你想要的是更好地理解这个问题，所以让我说清楚。字符串的通常排序是字典排序。如果将字符串 [jibw, ji, jp, bw, jibw] 按字典顺序排序，则排序后的序列是 [bw, ji, jibw, jibw, jp]，这就是您得到的。所以你的问题不在于理解“词典”这个词；而是在于理解“词典”这个词。你已经正确理解了它。

你的问题是你误读了这个问题。该问题不会要求您按字典顺序对字符串进行排序。 （如果是这样，您通过排序得到的答案将是正确的。）相反，它会要求您生成一个字符串，该字符串是通过按某种顺序连接输入字符串而获得的（即，生成一个没有空格的字符串），以便生成的单个字符串在字典顺序上是最小的。

为了说明差异，请考虑通过连接排序序列和答案字符串获得的字符串：

bwjijibwjibwjp //Your answer
bwjibwjibwjijp //The correct answer

现在，当您比较这两个字符串时 - 请注意，您只是比较两个 14 字符的字符串，而不是两个字符串序列 -您可以看到，正确答案确实按字典顺序小于您的答案：您的答案以“bwjij”开头，而正确答案以“bwjib”开头，并且按字典顺序“bwjib”位于“bwjij”之前。

希望你现在明白这个问题了。这根本不是一个排序问题。 （也就是说，这不是对输入字符串进行排序的问题。您可以对通过排列和连接输入字符串获得的所有可能的字符串进行排序；这是解决问题的一种方法，如果数字输入字符串的数量很小。）

Answer 8

您可以通过将 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 9

我在 Facebook 黑客杯中一直使用 F#。通过这次比赛，收获颇丰。由于网上关于 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 10

//使用此代码块来打印数组中按字典顺序排序的字符，或者它可以以多种方式使用。

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