algorithm - 作为流操作的数基转换

Question

有没有办法在恒定的工作空间中进行任意大小和任意碱基转换。也就是说，将 [1,m] 范围内的 n 数字序列转换为 ceiling(n*log(m)/log( p)) 范围 [1,p] 中的数字使用一对一映射(最好但不一定)保留词法顺序并给出顺序结果？

我对作为管道功能可行的解决方案特别感兴趣，例如能够处理比存储在 RAM 中更大的数据集。

我发现了许多需要与输入大小成比例的“工作空间”的解决方案，但还没有一个解决方案可以摆脱恒定的“工作空间”。

---

放弃顺序约束有什么不同吗？即:允许按字典顺序输入导致非字典顺序输出:

F(1,2,6,4,3,7,8) -> (5,6,3,2,1,3,5,2,4,3)
F(1,2,6,4,3,7,9) -> (5,6,3,2,1,3,5,2,4,5)

---

一些想法:

这行得通吗？

streamBase_n -> convert(n, lcm(n,p)) -> convert(lcm(n,p), p) -> streamBase_p

(其中 lcm 是最小公倍数)

Answer 1

我认为在一般情况下这是不可能的。如果 m 是 p 的幂(反之亦然)，或者如果它们都是公共(public)基数的幂，你可以这样做，因为每组日志_m(p) 是独立的。但是，在一般情况下，假设您要转换数字 a1 a2 a3 ... an。 base p 中的等价数是

sum(ai * m i-1 for i in 1..n)

如果我们已经处理了前 i 个数字，那么我们就有了第 i 个部分和。要计算第 i+1 个部分和，我们需要添加 ai+1 * mi.在一般情况下，这个数字在大多数地方都会有非零数字，所以我们需要修改到目前为止我们处理过的所有数字。换句话说，在我们知道最终输出数字是什么之前，我们必须处理所有输入数字。

在 m 都是公共(public)基数的幂的特殊情况下，或者等效地，如果 log_m(p) 是一个有理数，那么 mi 将只有几个非零数字以 p 靠近前面，所以我们可以安全地输出我们目前计算的大部分数字。