タイトルには、10 進数を整数に変換する方法を探していると書かれていますが、解決しようとしている実際の問題に対する答えを示します。N 要素の配列の K 番目の順列を取得する方法です。
簡単に言えば、与えられた配列の K 番目の順列を予測するには、1 桁ずつ進む必要があります。物事の理論的な側面は非常に単純です。配列 A に要素があり、各要素が 2 番目の配列 S で使用されているかどうかに関する情報を格納しているとします。各桁に適切な値を選択すると、S が更新されます。結果は配列 R に格納されます。
Nあります！与えられた配列 A の要素の順列。N 桁の配列の場合、A の最小要素が結果の左端の桁 R[0] になるように選択された場合に、いくつの順列があるかを考えてみましょう。(N-1)ですよね？#1 から #(N-1) までの順列です! 結果の左端の要素が A の最小要素である場合に属します。順列 #((N-1)! + 1) から #(2 *(N-1)!) は、A の 2 番目に小さい値を R とします。 [0]。そのため、#((i-1) * (N-1)! + 1) から #(i * (N-1)!) への順列は、A の i 番目の未使用で辞書編集的に最小の数字を R[0] として使用します。
より一般化された意味では、値は K 番目の辞書編集的に最小の順列 A[i] の R[d] で使用されているため、A[i] はこれまで使用されていない i 番目の辞書編集的に最小の要素であり、(i * (N-1-d)! + 1) <= kおよびk <= ((i+1) * (N-1-d)!)。
S 全体をトラバースすると、適切な i 値を見つけるのにO(N)時間がかかります。それを正確に実装する方法についてはわかりませんが、S でバイナリ検索を実行して、適切な値を見つけることもできる場合があります。 i は O(logN) 時間です。
大きな K 値がある場合、比較を行うために大きな整数乗算を実装する必要があると思いますが、これを回避する賢い方法を考えたら、回答のこの部分を更新します。
適切な i を選択したら、A[i] を R[d] に割り当てて、次の数字を見つけることができます。
以下は、このソリューションを実装するコードの一部です。長くなりますが、そのほとんどは単なる大整数の実装です。アルゴリズムの要点は、実際には 30 行未満です。必要に応じて自分でテストできるように、動作するコードを提供したかっただけです。
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#define NLIMIT 100
#define ASIZELIMIT 101
#define BIGINTBUCKETSLIMIT 100
#define BUCKETCAPACITY 1000000000
#define DIGITSPERBUCKET 9
using namespace std;
/* sufficient big integer implementation */
class BigInt
{
/*
* Note that BIGINTBUCKETSLIMIT should be high enough so that
* the values given as input does not cause overflow
* or access violation from the last bucket in operations
* multiply and subtract.
*/
public:
long long buckets[BIGINTBUCKETSLIMIT];
BigInt() {
for(int i=0; i < BIGINTBUCKETSLIMIT; ++i) {
buckets[i] = 0LL;
}
}
BigInt(int initialValue) {
for(int i=0; i < BIGINTBUCKETSLIMIT; ++i)
{
buckets[i] = initialValue % BUCKETCAPACITY;
initialValue /= BUCKETCAPACITY;
}
}
void multiply(int val) {
for(int i= BIGINTBUCKETSLIMIT - 1; i >= 0; --i)
buckets[i] = buckets[i] * val;
for(int i=0; i < BIGINTBUCKETSLIMIT - 1; ++i) {
buckets[i+1] += buckets[i] / BUCKETCAPACITY;
buckets[i] = buckets[i] % BUCKETCAPACITY;
}
}
void subtract(BigInt B) {
for(int i= 0; i < BIGINTBUCKETSLIMIT; ++i) {
buckets[i] = buckets[i] - B.buckets[i];
if(buckets[i] < 0LL) {
buckets[i] += BUCKETCAPACITY;
buckets[i+1]--;
}
}
}
const BigInt & operator=(const BigInt &B) {
for(int i=0; i < BIGINTBUCKETSLIMIT; ++i)
buckets[i] = B.buckets[i];
return *this;
}
bool operator<(const BigInt &B) {
for(int i=BIGINTBUCKETSLIMIT-1; i >= 0; --i)
if(buckets[i] != B.buckets[i])
return buckets[i] < B.buckets[i];
return false;
}
void importFromStr(string &src)
{
long long buffer = 0, j = 0;
for(int i=src.size() - 1; i >= 0; i -= DIGITSPERBUCKET) {
buffer = 0;
for(int k=max(0, i - DIGITSPERBUCKET + 1); k <= i; ++k) {
buffer = buffer * 10 + (src[k] - '0');
}
buckets[j++] = buffer;
}
}
};
BigInt factorials[ASIZELIMIT];
void preprocessFactorials(int n)
{
factorials[0] = BigInt(1);
for(int i=1; i <= n; ++i) {
factorials[i] = factorials[i-1];
factorials[i].multiply(i);
}
}
void findKthPermutation(int N, int A[], BigInt K, int result[]) {
BigInt tmpBigInt;
bool S[ASIZELIMIT];
for(int i=0; i < N; ++i)
S[i] = true;
K.subtract(BigInt(1));
preprocessFactorials(N);
for(int d=0; d < N; ++d) {
for(int i=0, j=0; i < N; ++i) {
if(S[i]) {
tmpBigInt = factorials[N-1-d];
tmpBigInt.multiply(j+1);
if(K < tmpBigInt) {
result[d] = A[i];
S[i] = 0;
tmpBigInt = factorials[N-1-d];
tmpBigInt.multiply(j);
K.subtract(tmpBigInt);
break;
}
++j;
}
}
}
}
int main() {
string k;
BigInt K;
int N;
int A[ASIZELIMIT], R[ASIZELIMIT];
cin >> N >> k;
for(int i=0; i < N; ++i)
cin >> A[i];
K.importFromStr(k);
sort(A, A+N);
findKthPermutation(N, A, K, R);
cout << R[0];
for(int i=1; i < N; ++i)
cout << " " << R[i];
cout << endl;
return 0;
}
関数 findKthPermutation と私の BigInt クラスの 2 つのループを簡単に観察できるように、実装は K に関係なく O(N 3 ) で機能します。正確なパフォーマンスのニーズはわかりませんが、N <= 100 であるため、十分に効率的です。あなたが望むほど効率的でない場合、私の最初の提案は、O(logN) 時間で各桁 d に対して求められる適切な i 値を生成する可能性のある他のデータ構造を使用して、S に情報を格納することを最適化することです。
最後に、この解決策では、可能性のある順列の辞書式列挙に干渉するため、 A に重複する要素が含まれていないことを前提としていることに注意してください。