How to Convert very large Decimal number to Factorial number system?

Question

I want to convert decimal number to Factorial number system.

I want to do this for finding nth Lexicographic permutation of array up to 100 elements eg. A[87]={1,2,3..,87}

I am given index 'n' whose lexicographic permutation at that position I need to find. e.g 2nd permutation of {1,2,3} is {1,3,2}

For this I am trying to use Factorial number system.

The below link gives information about conversion method.

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

As explained (463) in decimal gives 341010! in factorial.

463 ÷ 1 = 463, remainder 0

463 ÷ 2 = 231, remainder 1

231 ÷ 3 = 77, remainder 0

77 ÷ 4 = 19, remainder 1

19 ÷ 5 = 3, remainder 4

3 ÷ 6 = 0, remainder 3

This method can be applied only if decimal number falls in permissible range like unsigned long long int.

What do to if number can't fit in integer range?

My test cases involves number so large that they need to be stored in string format.(e.g. Find 123456789012345678901234555623344 permutation of array[100]={1,2,3,4,....100})

I am trying to solve this problem in c++.

(Use of next_permutation() in c++ to get up to given index is costly method and takes a lot of time.)

Answer 1

Here is the code. You can see and ask me for any confusion.

Also, I have only one test case which you have provided and I have not done an exhaustive test of the code. If you find any error, I'll be happy to resolve.

#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;
}