2

順列を使用して（各文字を使用して）文字列を「helloworld！」に生成していますが、「helloworld！」に到達するのに...176791かかりました。「helloworld！」にすばやく変換するために、176791と入力する方法はありますか？

        ...
176790. helloworl!d
176791. helloworld!

私のコード：

#include <windows.h>
#include <string>
#include <iostream>
#include <algorithm>

int main( void )
{
    ::UINT64 Count = 0;
    std::string SomeString = "eohldo!lwrl";
    do
    {
        Count ++;
        std::cout << Count << ". " << SomeString << std::endl;
        if( SomeString == "helloworld!" )
            break;
    } while( std::next_permutation( SomeString.begin( ), SomeString.end( ) ) );

    ::getchar( );
    return( 0 );
};
4

1 に答える 1

3

質問が何なのかわかりません。基本的に、整数による順列を「エンコード」する方法を探しているように見えます。ただし、このエンコーディングが、への順次呼び出しによって生成された順列シーケンスと同期する必要があるかどうかは明らかではありませんstd::next_permutation。それは...ですか？つまり、その数がアプリケーション176791によって生成された順列をエンコードする必要がありますか？176791std::next_permutation

順列は、いくつかの異なる方法で整数でエンコードできます。適切に構築されたエンコーディングは、すべて同じビット数を占有します。ただし、エンコードが異なると、同じ順列をエンコードするために異なる整数が使用される場合があります。

とにかく、特定のエンコード方法を気にしない場合は、N要素の順列を次の方法でエンコードできます。

  • 順列の正規表現を想像してみてください。Nシーケンスの要素の新しい位置を記述するインデックスの配列index[old position] = new positionです。

  • 次に、その配列を基数のN桁の数値として解釈しNます。つまり、順列は整数値で表されます

    index[0]*N^0 +  index[1]*N^1 + index[2]*N^2 + ... + index[N-1]*N^(N-1)

基本的に、元の順列の正規配列表現は、十分に大きな整数値にパックされます。（Nが2の累乗の場合、この表現は元の配列値をビット配列にパックするだけです）。梱包と開梱はどちらも簡単なプロセスです。

残念ながら、上記で説明した表現は適切に構成されていません。index一意でない値で配列を「ロスレス」でエンコードしようとするため、必要以上のビットが必要になります。順列の有効な表現では、インデックス配列に繰り返し値はありません。これはすぐに、上記の表現が過剰であることを意味します。よりコンパクトな表現が可能になるはずです。とにかく、これはかなりよく研究された主題であるはずであり、単純なグーグル検索はエンコーディング順列に関する多くの情報を見つけるはずです。

これは、このトピックのより深い分析を提供するSOリンクです。

高速順列->数値->順列マッピングアルゴリズム

于 2012-11-29T03:49:12.157 に答える