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

Question

Я хочу преобразовать десятичное число в систему счисления Factorial.

Я хочу сделать это для нахождения n-й лексикографической перестановки массива до 100 элементов, например. А [87]={1,2,3..,87}

Мне дан индекс 'n', лексикографическая перестановка которого в той позиции мне нужно найти. например, 2-я перестановка {1,2,3} равна {1,3,2}

Для этого я пытаюсь использовать Факториальную систему счисления.

Ниже ссылка дает информацию о способе конвертации.

https://en.wikipedia.org/wiki/Factorial_number_system

Как объяснено (463) в десятичном виде дает 341010! в факториале.

463 ÷ 1 = 463, остаток 0

463 ÷ 2 = 231, остаток 1

231 ÷ 3 = 77, остаток 0

77 ÷ 4 = 19, остаток 1

19 ÷ 5 = 3, остаток 4

3 ÷ 6 = 0, остаток 3

Этот метод может применяться только в том случае, если десятичное число попадает в допустимый диапазон, например, unsigned long long int.

Что делать, если число не может вписаться в целочисленный диапазон?

Мои тесты включают в себя число, настолько большое, что их нужно хранить в строковом формате (например, Find 123456789012345678901234555623344 перестановка массива [100]={1,2,3,4,....100})

Я пытаюсь решить эту проблему в C++.

(Использование метода next_permutation() в C++ для получения заданного индекса является дорогостоящим методом и занимает много времени.)

Answer 1

Вот код Вы можете увидеть и спросить меня о любой путанице.

Кроме того, у меня есть только один тестовый пример, который вы предоставили, и я не провел исчерпывающий тест кода. Если вы обнаружите какую-либо ошибку, я буду рад устранить ее.

#include<bits/stdc++.h>
using namespace std;

#define MAX 1000000
#define MOD 1000000007
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define V vector
#define I int
#define D double
#define B bool
#define pii pair<int,int>
#define LL long long

#define in(x) scanf("%d",&x)
#define in2(x,y) scanf("%d%d",&x,&y)
#define lin(x) scanf("%lld",&x)
#define lin2(x,y) scanf("%lld%lld",&x,&y)
#define FOR(i,a,b) for(i=a;i<b;i++)
#define all(v) v.begin(),v.end()

string q;    //this is the input
V<I> sol;    //this is final solution vector. (will be printed in reverse)

void divide(I n){    //function to divide a string by `n`
    string r = "";
    I i,k=0;
    FOR(i,0,q.length()){
        k *= 10;
        k += (q[i] - '0');
        I g = k / n;
        k = k % n;
        if((r.length()==0 && g!=0) || (r.length()>0)){
            r += (char)(g + '0');
        }
    }
    q = r;
    sol.PB(k);
}

I main(){
    cin>>q;
    I i;
    FOR(i,1,101){   //assuming 100 is the limit
        if(q.length()==0)
            break;
        divide(i);
    }
    //print the result
    for(i=sol.size()-1;i>=0;i--)
        //printf("%d ",sol[i]);
        cout<<sol[i]<<" ";
    printf("\n");
    return 0;
}

Answer 2

Хотя в заголовке говорится, что вы ищете способ преобразования десятичных чисел в целые, я дам ответ на реальную проблему, которую вы пытаетесь решить: как получить 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) <= k и k <= ((i+1) * (N-1-d)!).

Потребуется O(N) время, чтобы найти подходящее значение i, если вы пройдете весь S. Я не уверен, как именно вы можете его реализовать, но вы также можете выполнить бинарный поиск по S и добиться нахождения подходящего я в 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³) независимо от K. Хотя я не знаю ваших точных потребностей в производительности, так как N <= 100, это может быть достаточно эффективен. Если это не так эффективно, как вы хотите, моим первым предложением будет оптимизация хранения информации в S с использованием некоторой другой структуры данных, которая может дать за время O(logN) соответствующее значение i, запрошенное для каждой цифры d.

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