问题标签 [finite-group-theory]

昨天我有一个有趣的想法。想象一下，你有一个魔方，每个面上已经有相同的颜色。现在，如果我扭曲它一次并且我知道如何扭曲它，我总是可以通过反转此步骤将立方体恢复到原来的状态。如果我扭转两次，我总是可以用最少的两步来恢复立方体。所以我在想，如果我随机扭曲 n 步，总有 n 步可以将立方体反转为原来的。

但是，我认为当 n 变大时，进行反转的最小步骤可能会小于 n，因为在使用更多步骤时，会有一些特定的步骤序列可以使用更少的步骤来达到相同的效果。

例如，如果n=100，在n=30时可能有相同的模式，所以相当于n=30。那么也许我可以使用 m 步的操作将 n 减少到 20，但 m 小于 10。

所以我在想，无论 n 有多大，它总是会收敛到一个
很小的数字，这意味着无论魔方最初如何，我总是可以在小于或等于 k ​​步内将它恢复到原来的值，其中 k 是n 的收敛。

我的问题是是否存在可用于找到 n 收敛的算法？我想图论或群论中的一些东西会有所帮助。

我想要一个find大小有界类型的流的函数，它类似于 Lists 和 Vects 的查找函数。

挑战在于如何做到：

1. 完全
2. 消耗不超过常数log_2 N 空间，其中 N 是编码最大所需的位数a。
3. 在编译时检查不超过一分钟
4. 不强加运行时成本

通常，Streams 的总 find 实现听起来很荒谬。流是无限的，一个谓词const False将使搜索永远持续下去。处理这种一般情况的一个好方法是无限燃料技术。

这对我的用例很有效，但我想知道在某些特殊情况下是否可以在不使用forever. 否则，有人可能会忍受等待find forever ?predicateWhichHappensToAlwaysReturnFalse (iterate S Z)结束的无聊生活。

考虑特殊情况 where ais Bits32。

Nothing两个问题：它不是全部的，即使有有限数量的Bits32居民可以尝试，它也不可能返回。也许我可以用它take (pow 2 32)来构建一个 List，然后使用 List 的 find...呃，等等...单独的列表会占用 GBs 的空间。

原则上，这似乎不应该是困难的。有许多居民可以尝试，现代计算机可以在几秒钟内遍历所有 32 位排列。有没有办法让整体检查器验证the (Stream Bits32) $ iterate (+1) 0最终循环回到0并且一旦它断言所有元素都已经被尝试过，因为(+1)它是纯的？

这是一个开始，虽然我不确定如何填补这些漏洞并find足够专业化以使其完全。也许界面会有所帮助？

有没有办法告诉整体检查器使用无限燃料来验证对特定流的搜索是否完全？

这是我关于堆栈溢出的第一篇文章。我将在 4 月 30 日之前提交我的数学作业，这是我一直在寻找的问题，但我在任何地方都找不到任何答案。

我知道我可以列出所有可能的排列，即 = 4！= 24 但问题是其中哪些是偶数，哪些是奇数？(1,2,3,4), (1,2,4,3), (1,3,2,4) 等等.... 每个排列都有 3 个编号。换位意味着所有这些都是奇怪的那么问题的重点是什么？我对吗？

例如，如果我们让

G:= 符号 (6);

A:= 自同构组(G);

P:= 排列组（A）；

我：= {@ 我：我在 G | Order(i) eq 2 @};

那么如何通过映射构建 P 作用于 I 的 G 集，显示自同构如何置换对合？

我是 MAGMA 的新手，但最近我花了很多时间阅读手册，但我还没有找到任何方法来做到这一点。有没有人有任何有用的建议？

我已经使用元组的排列实现了一个魔方。没有变化的立方体表示为 (0, 1, 2, ... , 45, 46, 47)。

为了对立方体应用“转”，数字被打乱了。我已经非常全面地测试了我所有的轮次，以至于我相当确定没有错别字。

我一直在尝试实现一种检查多维数据集是否有效的方法，因为 (1, 2, ... 47, 48) 的 12 个随机排列中只有 1 个是有效的多维数据集。要使排列成为有效的魔方，它必须满足 3 个要求。这在这个 SO 线程中有很好的记录：https ://math.stackexchange.com/questions/127577/how-to-tell-if-a-rubiks-cube-is-solvable

这 3 个步骤是： 边缘方向：边缘翻转的数量必须是偶数。拐角方向：拐角扭曲的数量必须能被 3 整除。排列奇偶校验：这是我遇到麻烦的地方。排列奇偶校验必须是偶数，这意味着角奇偶校验必须匹配边缘奇偶校验。

SymPy 库为我提供了一种处理许多排列组属性的好方法，因此我将它包含在我计算排列奇偶性的尝试中。

它应该成功时失败的最简单的测试输入是立方体的后转，表示为 B。

这是代码：

使用一堆打印语句，我概述了整个代码中发生的情况：

这是初始状态。这是立方体的 B 排列，看起来和预期的一样。

接下来我们看看角落和边缘。请记住，每个边缘都减去了 24。这对于最终转换为 SymPy 排列是必要的。

然后我们只提取每 3 个角和每 2 个边。这让我们只看每个部分的排列，因为我们不关心方向。

然后我们按 2 或 3 占卜以转换为 SymPy

转换为 SymPy 后，角落看起来像这样：

边缘看起来像这样：

给我们这个奇偶校验，因为角由 3 个周期组成，边缘由 2 个周期组成：

角、边等价

1

0

因为奇偶校验不同，所以函数返回 false。

B：错误

我们知道奇偶校验应该匹配，但我无法得到这个结果，而且我有点迷失在哪里进行进一步的调试。所有代码都可以在我的 GitHub 上找到：https ://github.com/elliotmartin/RubikLite/blob/master/Rubik.py

存储一系列不同元素的排列的一种简单方法是作为字符串（或列表），例如“acb”，这显然是“abc”的排列。但是，如果我使用一个字符串来表示我的排列，我最终会得到像“abb”这样的字符串不对应任何排列的可能性。结果，可以说，字符串中排列的表示并不密集。像 [2,3,1] 这样的索引列表也有同样的问题。

或者，我可以认识到超过 N 个元素有 N！排列，可以以某种方式枚举。然后，我可以将排列存储为整数。然而，这并不理想，因为整数对解释是不透明的（没有人会知道“排列数 43”是什么意思），并且还因为整数的组结构超过加法与排列的组结构完全不同。

有没有一种方法可以在没有我建议的方法的缺点的计算机中表示排列？

我想检查像下面这样的乘法表是否不是代码，但我找不到另一种写法

它在我的代码中存储为带有子列表的列表，例如

我想从排列中提取最大的数字。我现在正在使用组模块，所以下面代码中的输出应该是 15

这是一个由两部分组成的问题，但第二部分取决于第一部分。

出于教育目的，我正在尝试为组（抽象代数的概念）实现一个抽象基类和测试套件。代数群的部分定义等同于类型约束，我想在 ABC 上实现该类型约束，如果具体类上的方法不符合该约束，我会抱怨。

对于逻辑下的布尔值组，我有一个第一遍实现and，但它至少有两个问题，我希望你能帮我解决它。

首先：兴趣线#1 是在做类型约束工作，但当前的实现是错误的。它只检查该方法是否接收并返回一个AbsGroup实例。这可以是任何AbsGroup实例。我希望它检查它所继承的具体类，它接收并返回该具体类的实例（因此在Bool它接收并返回的实例的情况下Bool）。练习的重点是在一个位置执行此操作，而不必在每个具体类上专门设置它。我认为这是通过一些类型提示泛型完成的，这些泛型比我尚未深入研究的类型提示要深一些。我该怎么做呢？

其次：如何检查具体方法是否符合抽象类型提示？我的 IDE (PyCharm) 中的类型检查器在 Line-of-interest #2 处抱怨，因为它预计other是 type AbsGroup，它没有val属性。这是意料之中的，如果我能找出第一个问题的解决方案，它就会消失，但我的 IDE 是我能找到的唯一能注意到这种差异的东西。mypy默认情况下对此事保持沉默，flake8 和 pylint 也是如此。PyCharm 很好，但如果我想将其合并到工作流中，如果我的具体方法不符合抽象签名，我必须运行什么命令会失败？

问题

如何实现运行长度编码模数n>=1？因为n=4，考虑到输入AAABBBBABCCCCBBBDAAA，我们想要一个输出[('D', 1), ('A', 3)]。请注意由于模运算而导致的长距离合并。见说明。

解释

第一次出现的编码BBBB为who is ，从而抵消了自身。参见图表（忽略空格；它们仅用于说明目的）：(B, 4)modulus 4(B, 0)

一个更简单的例子，当没有合并发生时，因为没有被取消modulus 4：输入AAABABBBC产生输出[('A',3),('B',1),('A',1),('B',3),('C',1)]。

要求

• Haskell 实现是首选，但也欢迎其他实现！
• 首选标准/通用库函数而不是 3rd 方库。
• 更喜欢使用高阶函数的可读和简洁的程序。
• 更喜欢效率（不必要时不要循环整个列表）

我的程序

我在 Haskell 中实现了这个，但它看起来太冗长且难以阅读。关键思想是一次检查三个元组，如果我们既不能取消0元组，也不能合并手头的三个元组中的一对元组，就只能向前推进一个元组。

想法

我的输入就像test上面截图中的变量。我们可以继续这样做flatten，nest直到它的结果没有改变，并且看起来肯定会更简单。但感觉它是多次扫描整个列表，而我的 3 指针实现只扫描整个列表一次。也许我们可以在合并相同的连续项目时从左侧弹出一个元素并将其添加到新堆栈中？或者也许使用应用函子？例如，这可行，但不确定其效率/性能：reduce = (until =<< ((==) =<<)) (nest . flatten)。