11

「単語を連結して、辞書式順序で可能な限り低い文字列を生成する」という問題を実行しています。競争から。

たとえば、次の文字列を取り上げます。jibw ji jp bw jibw

実際の出力は次のようになります。bw jibw jibw ji jp

これで並べ替えを行うと、次のようになりますbw ji jibw jibw jp。

これは、これがソートされていないことを意味しますか？ソートの場合、「辞書式」ソートでは、短い文字列を後ろに押すなどの考慮がありますか？

私は語彙の順序についていくつか読んでいますが、これが使用されているポイントやシナリオは見当たりませんが、何かありますか？

4

10 に答える 10

25

あなたが探しているのは質問のより良い理解であるように思われるので、それをはっきりさせておきましょう。文字列の通常のソートは辞書式ソートです。文字列[jibw、ji、jp、bw、jibw]を辞書式順序で並べ替えると、並べ替えられたシーケンスは[bw、ji、jibw、jibw、jp]になります。したがって、問題は「辞書編集」という単語を理解することではありません。あなたはすでにそれを正しく理解しています。

あなたの問題はあなたが質問を読み間違えているということです。この質問では、文字列を辞書式順序で並べ替えることは求められません。（もしそうなら、ソートによって得られた答えは正しいでしょう。）代わりに、入力文字列をある順序で連結することによって得られた1つの文字列を生成するように求められます（つまり、スペースなしで1つの文字列を作成します）。文字列は辞書式に最小限です。

違いを説明するために、ソートされたシーケンスを連結して得られる文字列と、回答文字列について考えてみます。

bwjijibwjibwjp //Your answer
bwjibwjibwjijp //The correct answer

これらの2つの文字列を比較すると（文字列の2つのシーケンスではなく、2つの14文字の文字列を比較していることに注意してください）、正解は実際に辞書式順序で回答よりも小さいことがわかります。回答は「bwjij」で始まります。正解は「bwjib」で始まり、「bwjib」は辞書式順序で「bwjij」の前にあります。

あなたが今質問を理解することを望みます。ソートの問題ではありません。（つまり、入力文字列の並べ替えの問題ではありません。入力文字列を並べ替えて連結することで取得できるすべての文字列を並べ替えることができます。これは、入力文字列の数が少ない場合の問題を解決する1つの方法です。）

于 2011-01-08T08:33:05.883 に答える
1

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

この比較関数を標準のソートで使用すると、問題が解決します。

于 2011-01-18T04:35:35.120 に答える
1

私はこのFacebookハッカーカップでF＃を使用しています。この大会でかなり学んだ。Web上の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
于 2011-01-27T14:08:42.560 に答える
1

//このコードブロックを使用して、配列の辞書式順序で並べ替えられた文字を印刷します。または、さまざまな方法で使用できます。

  #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);
        }
    }
于 2013-03-26T18:09:15.793 に答える
0

あなたが投稿した例は、単なる並べ替えでは辞書式順序で最も低い文字列が生成されないことを示しています。与えられた問題については、どの文字列がどの文字列の前に来るかを決定するためにいくつかの追加のトリックを適用する必要があります（現時点では、正確な方法を考えることはできません）

実際の出力は、辞書式順序で最も低い単語の条件に違反しません。

于 2011-01-08T06:39:36.630 に答える
0

代わりに、文字列ソート関数で「z」より大きくなるように重み付けできる特別な「プレースホルダー」文字をパディングすると、Prasunのトリックが機能します。結果は、辞書式順序が最も低い順序になります。

于 2011-01-09T18:00:20.933 に答える
0

Linuxのsortコマンドは、辞書式ソートも実行し、bw ji jibwjibwjpの順序で出力を生成します。

于 2011-01-08T07:07:17.667 に答える
0

ここで何が起こったかを確認してください：

辞書式順序を適用するだけでbwjijibw jibw jpが得られますが、トークンごとに分析すると、「bwjibw」（bw、jibw）が「bwjijibw」（bw、ji、jibw）よりも辞書式に低いことがわかります。そのため、答えはbw jibw jibw ji jpです。これは、最初にbwjibwjibwを追加し、その後、jiとjpを連結して最小の文字列を取得できるためです。

于 2011-01-08T07:51:10.350 に答える
0

最大文字列長が指定されているため、この問題に対して機能するソートのみを含む簡単なトリックは、最大長までのすべての文字列に文字列の最初の文字を埋め込むことです。次に、パディングされた文字列を並べ替えますが、元のパディングされていない文字列を出力します。例：文字列の長さが2で、入力がbとbaの場合、bbとbaを並べ替えると、baとbbが得られるため、babを出力する必要があります。

于 2011-01-09T15:23:11.617 に答える
0

コンテストが終わったので、私は可能な解決策を投稿しています。最も効率的ではありませんが、それを行う1つの方法です。

 #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関数は、辞書式順序で並べ替えられた順列を生成するだけです。

于 2011-01-10T21:56:48.870 に答える