基于数字基础系统的算法？

Question

我最近注意到,基于创意基础中数字的巧妙使用,部分或全部有很多算法.例如:

• 二项式堆基于二进制数,并且更复杂的偏斜二项式堆基于偏斜二进制数.
• 用于生成按字典顺序排列的排列的一些算法基于事实数字系统.
• 可以将尝试视为一次查看字符串的一位数的树,以获得适当的基础.
• 霍夫曼编码树被设计成使树中的每个边在一些二进制表示中编码为零或一.
• Fibonacci编码用于Fibonacci搜索并反转某些类型的对数.

我的问题是:还有哪些其他算法使用聪明的数字系统作为他们直觉或证据的关键步骤？.我正在考虑就这个问题进行一次讨论,所以我必须从中得到更多的例子.

Answer 1

Chris Okasaki在他的书" Purely Functional Data Structures "中有一个非常好的章节,它讨论了"数字表示":基本上,对数字进行一些表示并将其转换为数据结构.为了给出一种味道,以下是该章的部分内容:

1. 位置编号系统
2. 二进制数(二进制随机访问列表,无表示,惰性表示,分段表示)
3. 偏斜二进制数(偏斜二进制随机访问列表,偏斜二项式堆)
4. 三元数和四元数

一些最好的技巧,蒸馏:

• 区分数字的密集和稀疏表示(通常你会在矩阵或图表中看到它,但它也适用于数字!)
• 冗余数字系统(具有多个数字表示的系统)很有用.
• 如果将第一个数字排列为非零或使用无零表示,则检索数据结构的头部可能很有效.
• 通过分割数据结构,避免级联借(从列表的尾部开始)并携带(从列表中获取)

这是该章的参考列表:

• Guibas,McCreight,Plass和Roberts:线性列表的新表示.
• 迈尔斯:一个应用随机访问堆栈
• Carlsson,Munro,Poblete:具有恒定插入时间的隐式二项式队列.
• Kaplan,Tarjan:纯粹的功能列表,通过递归减速来进行连接.

Answer 2

"三元数可以用来传达自我相似的结构,比如Sierpinski Triangle或Cantor set." 资源

"第四纪数字用于表示二维希尔伯特曲线." 资源

"四分之一虚数系统最初是由Donald Knuth于1955年提出的,是对高中科学人才搜索的提交.它是一个非标准的位置数字系统,它使用虚数2i作为基础.它能够仅使用数字0,1,2和3表示每个复数." 资源

"罗马数字是一个两性系统." 资源

"在素数的研究中,可以认为Senary是有用的,因为所有素数,当用基数6表示时,除了2和3之外,有1或5作为最后数字." 资源

"Sexagesimal(60号基地)是一个以六十年代为基础的数字系统.它起源于公元前三千年的古代苏美尔人,它被传递给古代的巴比伦人,并且它仍被用于 - 以修改的形式 - 用于测量时间,角度和角度的地理坐标." 资源

等等...

这份清单是一个很好的起点.

Answer 3

我前几天读了你的问题,今天遇到了一个问题:如何生成一组的所有分区？我遇到的解决方案,以及我使用的解决方案(可能是因为阅读了您的问题)是:

对于具有(n)个元素的集合,我需要(p)分区,计算基数(p)中的所有(n)个数字.

每个数字对应一个分区.每个数字对应于集合中的元素,数字的值告诉您将元素放入哪个分区.

这并不奇怪,但它很整洁.它完整​​,没有冗余,并使用任意基础.您使用的基础取决于特定的分区问题.

Answer 4

我最近遇到了一个很酷的算法,用于根据0到2 ⁿ -1 之间数字的二进制表示,按字典顺序生成子集.它使用数字的位来确定应该为集合选择哪些元素以及本地重新排序生成的集合使它们进入字典顺序.如果你很好奇,我会在这里发布一篇文章.

此外,许多算法基于缩放(例如Ford-Fulkerson最大流算法的弱多项式版本),其使用输入问题中的数字的二进制表示来逐步地将粗略近似细化为完整解.

Answer 5

不完全是一个聪明的基础系统,而是巧妙地使用基本系统:Van der Corput序列是通过反转数字的base-n表示形成的低差异序列.它们被用于构建看起来像这样的2-d Halton序列.

Answer 6

我依稀记得一些关于加速某些矩阵乘法的双基系统.

双基系统是一个冗余系统,它使用两个基数作为一个数字.

 n = Sum(i=1 --> l){ c_i * 2^{a_i} * 3 ^ {b_i}, where c in {-1,1}

冗余意味着可以通过多种方式指定一个数字.

您可以通过Vassil Dimitrov,Todor Cooklev查找文章"计算矩阵多项式的混合算法".

我试图给出最好的简短概述.

他们试图计算矩阵多项式G(N,A) = I + A + ... + A^{N-1}.

Supoosing N是复合的G(N,A) = G(J,A) * G(K, A^J),如果我们申请J = 2,我们得到:

         / (I + A) * G(K, A^2)        , if N = 2K
G(N,A) = |
         \ I + (A + A^2) * G(K, A^2)  , if N = 2K + 1

也,

         / (I + A + A^2) * G(K, A^3)           , if N = 3K
G(N,A) = | I + (A + A^2 + A^3) * G(K, A^3)     , if N = 3K + 1
         \ I + A * (A + A^2 + A^3) * G(K, A^3) , if N = 3K + 2

因为它是"显而易见的"(开玩笑地),其中一些方程式在第一个系统中很快,而在第二个系统中则更好 - 所以选择最好的方程式是个好主意N.但是这需要对2和3进行快速模运算.这就是为什么双基进来 - 你基本上可以快速进行模运算,因为它们都为你提供了一个组合系统:

         / (I + A + A^2) * G(K, A^3)       , if N = 0 or 3 mod 6
G(N,A) = | I + (A + A^2 + A^3) * G(K, A^3) , if N = 1 or 4 mod 6
         | (I + A) * G(3K + 1, A^2)        , if N = 2 mod 6
         \ I + (A + A^2) * G(3K + 2, A^2)  , if N = 5 mod 6

请看文章以获得更好的解释,因为我不是这方面的专家.

Answer 7

RadixSort可以使用各种数量的基础. http://en.wikipedia.org/wiki/Radix_sort 一个非常有趣的bucketSort实现.

Answer 8

这里有一篇关于使用三元数来解决"伪造硬币"问题的好帖子(你需要在一袋普通硬币中检测一个伪造硬币,尽量少用余额)

Answer 9

散列字符串(例如在Rabin-Karp算法中)通常将字符串评估为由n个数字组成的base-b数字(其中n是字符串的长度,b是一些足够大的选定基数).例如,字符串"ABCD"可以散列为:

'A'*b^3+'B'*b^2+'C'*b^1+'D'*b^0

将ASCII值替换为字符并将b替换为256,

65*256^3+66*256^2+67*256^1+68*256^0

但是,在大多数实际应用中,所得到的值是以一些合理大小的数量为模,以保持结果足够小.