问题标签 [discrete-mathematics]

首先，我是一个 Java 初学者，所以我不确定这是否可能！基本上我有一个巨大的（3+百万）关系数据数据源（即A是B+C+D的朋友，B是D+G+Z的朋友（但不是A - 即不互惠的）等），我想要在这个（不一定是连接的）有向图中找到每个循环。

我找到了Finding all cycles in graph的线程，这让我想到了Donald Johnson 的（基本）循环查找算法，至少从表面上看，它看起来像我所追求的（我要试试当我周二回到工作岗位时 - 认为同时询问不会有什么坏处！）。

我快速浏览了Johnson算法的Java实现代码（在那个线程中），看起来关系矩阵是第一步，所以我想我的问题是：

a) Java 是否能够处理 3+million*3+million 矩阵？（计划用二元稀疏矩阵表示 A-friends-with-B）

b) 我需要找到每个连通子图作为我的第一个问题，还是循环查找算法会处理不相交的数据？

c) 这实际上是解决问题的合适方法吗？我对“基本”周期的理解是，在下图中，不是选择 ABCDEF，而是选择 ABF、BCD 等，但这并不是世界末日。

d) 如有必要，我可以通过加强关系中的相互性来简化问题 - 即 A-friends-with-B <==> B-friends-with-A，如果真的有必要，我可以减少数据大小，但是实际上，它总是在 100 万左右。

z) 这是 P 任务还是 NP 任务？！我咬得比我能咀嚼的多吗？

谢谢大家，任何帮助表示赞赏！安迪

我尝试找到一个问题的解决方案....我们有一个数字，例如：20 ...我们有 6 个数字：{ a ,b , c , d , e , f} < 20 , t 尝试找到这些数字的所有值，但前提是我们可以组合（whit + 或 -）这个数字中的 2 个并将以下所有值变为 20：例如

我们选择 31 ：

a = 22 b = 21 c = 14 d = 11 e = 9 f = 5

我们有：22 - 21 = 1；11 - 9 = 2；14 - 11 = 3；9 - 5 = 4；f = 5 ; 11 - 5 = 6；21 - 14 = 7；.... .... .... .... .... 21 + 9 = 30 ; 9 + 22 = 31；

假设输入总是相同的 N 个数字（例如，5）并假设整数实际上具有数学关系（数字“一”、“二”、第 n 个月中的天数等没有长度）。输出将是下一个整数和发现的规则，或者是无法检测到规则的消息。我想有一个一二三顺序的模块，该模块试图通过对相邻数字、一远、二远等数字之间的求和和/或差来查找算术序列规则。寻找模式，然后专注于模块通过以相同方式乘法和/或除法来处理几何序列，然后，如果有通用方法，则使用用于检测递归序列的模块。

谢谢！

我面临一个相当特殊的问题。我正在为不支持按位运算的架构开发编译器。但是，它处理有符号的 16 位整数运算，我想知道是否可以仅使用以下方法实现按位运算：

• 加法( c = a + b )
• 减法( c = a - b )
• 除法( c = a / b )
• 乘法( c = a * b )
• 模数( c = a % b )
• 最小值( c = min(a, b) )
• 最大值( c = max(a, b) )
• 比较（c =（a < b），c =（a == b），c =（a <= b）等）
• 跳转（goto、for 等）

我希望能够支持的按位运算是：

• 或( c = a | b )
• 和( c = a & b )
• 异或( c = a ^ b )
• 左移( c = a << b )
• 右移( c = a >> b )
• （所有整数都有符号，所以这是一个问题）
• 有符号移位( c = a >>> b )
• 一个的补码( a = ~b )
• （已经找到解决方案，见下文）

通常问题是相反的。如何使用按位 hack 实现算术优化。但是在这种情况下不是。

这种架构上的可写内存非常稀缺，因此需要按位运算。按位函数本身不应使用大量临时变量。但是，常量只读数据和指令内存是丰富的。附带说明一下，跳转和分支并不昂贵，并且所有数据都可以轻松缓存。跳转花费的周期是算术（包括加载/存储）指令的一半。换句话说，所有上述支持的功能都花费了单次跳转周期的两倍。

一些可能有帮助的想法：

我发现您可以使用以下代码进行补码（否定位）：

我还记得用 2 的幂除时的旧移​​位技巧，因此按位移位可以表示为：

对于其余的按位运算，我有点不知所措。我希望这种架构的架构师能够提供位操作。

我还想知道是否有一种快速/简单的方法可以在不使用内存数据表的情况下计算两个的幂（用于移位操作）。一个天真的解决方案是跳入乘法领域：

或 Set & Jump 方法：

有一个问题浮出水面。它是用基本的 SQL 术语设置的，但它的本质是纯数学（所以也许我也应该访问https://mathoverflow.net）。

我在一些理论数据库中有一个包含 6 个字段的表，都是数字。我们还有基本条件，如Field_1 > Field_5，Field_4 = 3等，一共7个条件。我需要写一个选择，它至少满足其中的4 个。

用(cond_1 AND cond_2 AND cond_3 and cond_4) OR (...)等许多逻辑条件编写 long select不是一种方法，因为 7 个元素的 4 组合等于 140，并且不想这样写很多条件。

那么如何以简化形式编写选择呢？

这是我长期以来一直在绞尽脑汁的一个问题，所以任何帮助都会很棒。我有一个文件，其中包含以下格式的几行（单词，单词出现的时间，以及在给定实例中包含给定单词的文档的频率）。下面是输入文件的示例。

我有下面的 Python 类，我用来创建二维字典来存储上述文件，使用作为键，频率作为值：

我的问题与在迭代此 2D 字典中的条目时计算某些事物有关。对于每个时间 't' 的每个单词 'w'，计算：

1. 在时间 't'内包含 单词 'w'的文档数。（一个）
2. 在时间 't'内没有 单词 'w'的文档数。(二)
3. 在时间 't'之外带有 单词 'w'的文档数。（C）
4. 在时间 't'之外没有 单词 'w'的文档数。(d)

上面的每个项目代表每个单词和时间的卡方列联表的一个单元格。所有这些都可以在一个循环中计算，还是需要一次完成一个？

理想情况下，我希望输出如下所示，其中 a、b、c、d 是上面计算的所有项目：

在上述输入文件的情况下，尝试在时间 '1' 查找单词 'apple' 的列联表的结果将是(3,2,1,6). 我将解释如何计算每个单元格：

• '3' 文档在时间'1' 内包含'apple'。
• 在时间“1”内有“2”个文档不包含“apple”。
• 在时间 '1' 之外有 '1' 个包含 'apple' 的文档。
• 在时间 '1' 之外有 6 个文档不包含单词 'apple' (1+4+1)。

我手头有一个问题，可以简化为这样的问题：

假设在二维平面 XY 中有一堆随机点，其中对于每个 Y，X 上可能有多个点，对于每个 X，Y 上可能有多个点。

无论何时选择一个点 (Xi,Yi)，都不能选择 X = Xi OR Y = Yi 的其他点。我们必须选择最大的点数。

我使用整数值（枚举）表示风向，范围从 0 代表北，到 15 代表北-北-西。

我需要检查给定的风向（0 到 15 之间的整数值）是否在一定范围内。我指定我的WindDirectionFrom值首先顺时针移动WindDirectionTo以指定允许的风向范围。

显然，如果WindDirectionFrom=0和WindDirectionTo=4（在 N 和 E 方向之间）且风向为 NE (2) 计算很简单

然而，对于另一种情况，比如WindDirectionFrom=15，WindDirectionTo=4并且风向再次为 NE (2)，计算立即中断......

我敢肯定这不会太难，但我对这个有一个真正的心理障碍。

我使用以下函数计算整数的对数基数 2：

它是否具有最佳性能？

有人知道为此目的准备好的 J2SE API 函数吗？

UPD1 令 我惊讶的是，浮点运算似乎比整数运算更快。

UPD2 由于评论，我将进行更详细的调查。

UPD3 我的整数算术函数比 Math.log(n)/Math.log(2) 快 10 倍。

问题说的差不多。我想出了

还有什么更易读的吗？或者这是不正确的？我知道当你可以在代码中使用 !~/bbb/ 时，你不应该真的用 Regex 做这种事情，但这是一个理论练习。

谢谢。

编辑澄清：我不是|用来表示正则表达式中的 OR 位+而是使用它。对困惑感到抱歉。

编辑 2：{a,b}适用于只有 'a' 和 'b' 字符的语言。不是{最小值，最大值}。再次抱歉。

编辑 3：因为这是理论课的一部分，所以我们只是在处理 Regex 的基础知识。您可以使用的唯一内容是 +、?、() 和 *。您不能使用 {minimum, maximum)。