Obwohl der Titel besagt, dass Sie nach einer Möglichkeit suchen Dezimalzahlen auf ganze Zahlen zu konvertieren, werde ich eine Antwort auf das eigentliche Problem gegeben Sie zu lösen sind versucht: wie die K-te Permutation eines Arrays erhalten von N Elementen.
Einfach gesagt, müssen Sie Ziffern für die Vorhersage der K-ten Permutation des gegebenen Arrays gehen. Die theoretische Seite der Dinge ist ziemlich einfach. Angenommen, Sie haben die Elemente im Array A und Sie speichern die Informationen darüber, ob jedes Element in einem zweiten Array S verwendet wird. S wird aktualisiert, wenn Sie für jede Ziffer den entsprechenden Wert auswählen. Das Ergebnis wird in einem Array R gespeichert.
Es gibt N! Permutationen der Elemente in der gegebenen Anordnung A.Betrachten wir für ein Array mit N Ziffern, wie viele Permutationen es gibt, wenn das kleinste Element in A als die am weitesten links stehende Ziffer im Ergebnis R [0] ausgewählt wird. Es ist (N-1)! Also Permutationen von # 1 bis # (N-1)! gehören zu dem Fall, in dem das äußerste linke Element des Ergebnisses das kleinste Element in A ist. Die Permutationen # ((N-1)! + 1) bis # (2 * (N-1)!) haben den zweitkleinsten Wert von A als R [0]. Also verwenden die Permutationen # ((i-1) * (N-1)! + 1) bis # (i * (N-1)!) Die nicht verwendete und lexikographisch kleinste Ziffer in A als R [0]. In einem allgemeineren Sinne wird der Wert in R [d] in der k-ten lexikographisch kleinsten Permutation A [i] verwendet, so dass A [i] das ith lexikographisch kleinste Element ist, das bisher nicht verwendet wird und so (i * (N-1-d)! + 1) < = k und k < = ((i + 1) * (N-1-d)!).
Es dauert O (N) Zeit, den geeigneten i-Wert zu finden, wenn Sie die gesamte S durchlaufen. Ich bin mir nicht sicher, wie Sie es genau implementieren können, aber Sie können auch binäre Suche tun auf S und erreiche die Suche nach geeigneten i in O (logN) Zeit.
Wenn Sie große K-Werte haben, denke ich, dass Sie eine große Ganzzahl-Multiplikation implementieren müssen, um den Vergleich zu machen, aber ich werde diesen Teil der Antwort aktualisieren, wenn ich über eine clevere Möglichkeit denke, um dies zu umgehen .
Sobald Sie das richtige i ausgewählt haben, können Sie einfach A [i] als R [d] zuweisen und weiter nach der nächsten Ziffer suchen.
Unten ist der Codeabschnitt, der diese Lösung implementiert. Es ist langwierig, aber das meiste ist nur die große Integer-Implementierung. Der Kern des Algorithmus ist tatsächlich weniger als 30 Zeilen. Ich wollte nur einen funktionierenden Code zur Verfügung stellen, damit Sie ihn selbst testen können, wenn Sie möchten.
#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;
}
Wie Sie leicht die zwei Schleifen in Funktion findKthPermutation und meine BigInt Klasse beobachten können, arbeitet die Umsetzung in O (N), und zwar unabhängig von K. Obwohl ich weiß nicht, Ihre genauen Leistungsanforderungen, als N < = 100 kann es effizient genug sein. Wenn es nicht so effizient ist, wie Sie es wünschen, wäre mein erster Vorschlag, das Speichern der Informationen in S unter Verwendung einer anderen Datenstruktur zu optimieren, die in O (logN) -Zeit den geeigneten i-Wert für jede Ziffer d liefern kann.
Schließlich, diese Lösung geht davon aus, dass A enthält keine doppelten Elemente, als das mit der lexikographischen Aufzählung der möglichen Permutationen eingemischt.
Verwenden Sie __int128 oder verwenden Sie GMP https://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithmetic_Library –
Können Sie nicht eine Funktion erstellen, die ein Array durch eine Zahl teilt und Ihnen den Quotienten als Array zurückgibt (und den Rest als a Nummer)? – vish4071
Wenn Sie wollen, kann ich Ihnen eine Funktion zur Verfügung stellen, die es kann. – vish4071