Как конвертировать очень большое десятичное число в систему факторных чисел?

Хотя в заголовке говорится, что вы ищете способ преобразования десятичных чисел в целые, я дам ответ на реальную проблему, которую вы пытаетесь решить: как получить K-ю перестановку массива из N элементов.

Проще говоря, вам нужно идти цифра за цифрой в предсказании K-й перестановки данного массива. Теоретическая сторона вещей довольно проста. Предположим, что у вас есть элементы в массиве A, и вы храните информацию о том, используется ли каждый элемент во втором массиве S. S будет обновляться по мере выбора подходящего значения для каждой цифры. Результат будет сохранен в массиве R.

Нет! перестановки элементов в данном массиве A. Для массива с N цифрами, давайте рассмотрим, сколько существует перестановок, если наименьший элемент в A выбран в качестве самой левой цифры в результате, R [0]. Это (N-1) !, верно? Так что перестановки от № 1 до № (N-1)! принадлежат случаю, когда самый левый элемент результата является наименьшим элементом в A. Перестановки # ((N-1)! + 1) в # (2 * (N-1)!) имеют второе наименьшее значение A как R [0]. Таким образом, перестановки # ((i-1) * (N-1)! + 1) в # (i * (N-1)!) Используют i-ю неиспользованную и лексикографически наименьшую цифру в A как R [0].

В более обобщенном смысле значение используется в R [d] в K-й лексикографически наименьшей перестановке A [i], так что A [i] является i-м лексикографически наименьшим элементом это не используется до сих пор и такой, что (i * (N-1-d)! + 1) <= к а также К <= ((i + 1) * (N-1-d)!).

Это займет НА) время, чтобы найти подходящее значение i, если вы пройдете весь S. Я не уверен, как именно вы можете его реализовать, но вы также можете выполнить бинарный поиск по 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;
}

Поскольку вы можете легко наблюдать 2 цикла в функции findKthPermutation и в моем классе BigInt, реализация работает в O (N³), независимо от К. Хотя я не знаю ваших точных потребностей в производительности, как N <= 100, это может быть достаточно эффективно. Если это не так эффективно, как вы хотите, моим первым предложением будет оптимизация хранения информации в S с использованием некоторой другой структуры данных, которая может дать за время O (logN) соответствующее значение i, запрошенное для каждой цифры d.

Наконец, обратите внимание, что это решение предполагает, что A не содержит повторяющихся элементов, как это мешает с лексикографическим перечислением возможных перестановок.