如何将非常大的十进制数转换为阶乘数系统？
How to Convert very large Decimal number to Factorial number system?
我想将十进制数转换为阶乘数制。
我想这样做是为了找到最多 100 个元素的数组的第 n 个词典排列，例如。 A[87]={1,2,3..,87}
我得到了索引 'n'，我需要找到它在那个位置的字典排列。例如 {1,2,3} 的第二个排列是 {1,3,2}
为此，我正在尝试使用阶乘数系统。
下面link给出了转换方法的信息。
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。
如果数字不在整数范围内怎么办？
我的测试用例涉及的数字太大，需要以字符串格式存储。（例如，查找 123456789012345678901234555623344 数组 [100]={1,2,3,4,....100} 的排列）
我正在尝试用 C++ 解决这个问题。
（在 C++ 中使用 next_permutation() 来达到给定的索引是一种昂贵的方法，需要花费大量时间。）
这是代码。有什么不明白的可以私信我
另外，我只有一个你提供的测试用例，我没有对代码进行详尽的测试。如果您发现任何错误，我很乐意解决。
#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;
}
虽然标题说你正在寻找一种将十进制数转换为整数的方法，但我会给出你要解决的实际问题的答案：如何获得 N 数组的第 K 个排列元素。
简单地说，你需要逐位预测给定数组的第K个排列。事情的理论方面非常简单。假设您有数组 A 中的元素，并且存储有关每个元素是否在第二个数组 S 中使用的信息。当您为每个数字选择适当的值时，S 将被更新。结果将存储在数组 R.
中
有N个！给定数组 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)!) 使用 ith 未使用和 lexicographically-smallest 数字在 A 作为 R[0].
在更广义的意义上，R[d] 中第 K 个字典序最小排列中使用的值是 A[i]，使得 A[i] 是第 i 个字典序最小元素 到目前为止没有使用 并且 (i * (N-1-d)! + 1) <= k and k <= ((i+1) * (N-1-d)!).
如果遍历整个S，需要O(N)时间才能找到合适的i值。我不确定你是如何实现的，但是您也可以对 S 进行二分查找，并在 O(logN) 时间内找到合适的 i。
如果您的 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 class 中的 2 个循环，实现在 O(N3) 中运行，与 K 无关。虽然我不知道您的确切性能需求，因为 N <= 100，它可能足够高效。如果它不如您期望的那样高效，我的第一个建议是使用其他一些数据结构优化将信息存储在 S 中，这些数据结构可能会在 O(logN) 时间内产生为每个数字 d.[=11= 寻找的适当 i 值]
最后，请注意，此解决方案假定 A 不包含重复元素，因为这会干扰可能排列的字典顺序枚举。
我想将十进制数转换为阶乘数制。
我想这样做是为了找到最多 100 个元素的数组的第 n 个词典排列，例如。 A[87]={1,2,3..,87}
我得到了索引 'n'，我需要找到它在那个位置的字典排列。例如 {1,2,3} 的第二个排列是 {1,3,2}
为此，我正在尝试使用阶乘数系统。
下面link给出了转换方法的信息。
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。
如果数字不在整数范围内怎么办？
我的测试用例涉及的数字太大，需要以字符串格式存储。（例如，查找 123456789012345678901234555623344 数组 [100]={1,2,3,4,....100} 的排列）
我正在尝试用 C++ 解决这个问题。
（在 C++ 中使用 next_permutation() 来达到给定的索引是一种昂贵的方法，需要花费大量时间。）
这是代码。有什么不明白的可以私信我
另外，我只有一个你提供的测试用例，我没有对代码进行详尽的测试。如果您发现任何错误，我很乐意解决。
#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;
}
虽然标题说你正在寻找一种将十进制数转换为整数的方法，但我会给出你要解决的实际问题的答案：如何获得 N 数组的第 K 个排列元素。
简单地说，你需要逐位预测给定数组的第K个排列。事情的理论方面非常简单。假设您有数组 A 中的元素，并且存储有关每个元素是否在第二个数组 S 中使用的信息。当您为每个数字选择适当的值时，S 将被更新。结果将存储在数组 R.
中有N个！给定数组 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)!) 使用 ith 未使用和 lexicographically-smallest 数字在 A 作为 R[0].
在更广义的意义上，R[d] 中第 K 个字典序最小排列中使用的值是 A[i]，使得 A[i] 是第 i 个字典序最小元素 到目前为止没有使用 并且 (i * (N-1-d)! + 1) <= k and k <= ((i+1) * (N-1-d)!).
如果遍历整个S，需要O(N)时间才能找到合适的i值。我不确定你是如何实现的，但是您也可以对 S 进行二分查找，并在 O(logN) 时间内找到合适的 i。
如果您的 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 class 中的 2 个循环，实现在 O(N3) 中运行，与 K 无关。虽然我不知道您的确切性能需求，因为 N <= 100，它可能足够高效。如果它不如您期望的那样高效，我的第一个建议是使用其他一些数据结构优化将信息存储在 S 中，这些数据结构可能会在 O(logN) 时间内产生为每个数字 d.[=11= 寻找的适当 i 值]
最后，请注意，此解决方案假定 A 不包含重复元素，因为这会干扰可能排列的字典顺序枚举。