问题标签 [sequences]

得到答案后编辑

这里有一些很好的答案。我喜欢 Josh 的，因为它非常聪明并且使用 C++。但是，我决定接受 Dave 的回答，因为它简单且具有递归性。我对它们都进行了测试，它们都产生了相同的正确结果（尽管顺序不同）。所以再次感谢大家。

假设我有一个字符串 s 的字符 s[0]:s[N] 并且每个字符 s[i] <= s[i+1] 例如字符串

我想生成子字符串的所有组合，同时保持字符之间的相同关系。

所以例如我会得到

但不是

现在我知道如何计算出有多少种组合。您创建字符串中字母频率的直方图。所以在上面的例子中，那将是

对于字符串 aaacdddghzz

公式是(a+1)(c+1)(d+1)(g+1)(h+1)(z+1) = 4*4*2*2*2*3 = 384。有 384 个子字符串保持 s[i] <=s [i+1] 关系。

所以问题是如何递归地生成这 384 个子字符串？实际上，迭代方法同样好，也许更好，因为具有许多唯一字符的大字符串可能会导致堆栈溢出。这听起来像是家庭作业，但事实并非如此。我只是想出这样的算法没用。我使用 C++，但伪代码会很好。

我有我为 f# 中的 morris seq 编写的这个“学习代码”，它遭受了我不知道如何避免的堆栈溢出。"morris" 返回一个无限的 "see and say" 序列（即 {{1}, {1,1}, {2,1}, {1,2,1,1}, {1,1,1 ,2,2,1}, {3,1,2,2,1,1},...}）。

您可以使用 Seq.nth 选择第 n 次迭代，但您只能在遇到堆栈溢出之前完成此操作。我有一点递归是尾递归，它本质上构建了一组链接的枚举器。这不是问题所在。这是在第 4000 个序列上调用“枚举”的时候。请注意，对于 F# 1.9.6.16，之前的版本最高超过 14000）。这是因为链接序列的解析方式。序列是惰性的，因此“递归”是惰性的。也就是说， seq n 调用 seq n-1 ，后者调用 seq n-2 等等以获取第一项（第一个 # 是最坏的情况）。

我知道，[|0|] |> Seq.append str |> Seq.windowed 2这使我的问题变得更糟，如果我消除它，我可以产生三倍的#。实际上，代码运行良好。morris 的第 3125 次迭代长度将超过 10^359 个字符。

我真正想要解决的问题是如何保留惰性 eval，并且对于我可以选择的迭代没有基于堆栈大小的限制。我正在寻找合适的 F# 习惯用法来根据内存大小进行限制。

2010 年 10 月更新

在更好地学习 F#，一点点 Haskell，思考和研究这个问题一年多之后，我终于可以回答我自己的问题了。但与难题一样，问题始于错误的问题。问题不在于序列的序列——这实际上是因为递归定义的序列。我的函数式编程技能现在稍微好一点，所以更容易看到下面的版本发生了什么，它仍然得到一个 stackoverflow

这基本上创建了一个非常长的 Seq 处理函数调用链来生成序列。F#自带的Seq模块就是不使用栈就不能跟链的。它对追加和递归定义的序列进行了优化，但该优化仅在递归实现追加时才有效。

所以这会起作用

这个会得到一个stackoverflow。

为了证明 F# 库是问题所在，我编写了自己的 Seq 模块，该模块使用延续实现了追加、成对、扫描和收集，现在我可以毫无问题地开始生成和打印 50,000 个序列（它永远不会完成，因为它已经结束了10^5697 位长）。

一些附加说明：

• Continuations 是我一直在寻找的习语，但在这种情况下，它们必须进入 F# 库，而不是我的代码。我从Tomas Petricek 的 Real-World Functional Programming一书中了解了 F# 中的延续。
• 我接受的惰性列表答案是另一个成语；懒惰的评价。在我重写的库中，我还必须利用惰性类型来避免 stackoverflow。
• 惰性列表版本是靠运气工作的（可能是设计使然，但这超出了我目前的能力范围）——它在构建和迭代时使用的活动模式匹配导致列表在所需的递归变得太深之前计算值，所以它很懒，但不是那么懒，它需要继续以避免stackoverflow。例如，当第二个序列需要第一个序列中的一个数字时，它已经被计算出来了。换句话说，LL 版本对于序列生成并不是严格的 JIT 惰性，只是列表管理。

这里有几件事：

1. 谁能指点我 C 代码来解码 ANSI 控制台转义序列？
2. 有没有办法让 Cygwin BASH 模拟一个愚蠢的旧 TTY？

也许这应该是2个问题。

谢谢。

首先，我假设每个特定于结构的序列都有不同的删除项目的方法：向量可以按索引，List可以首先或最后删除，Set应该传递要删除的实际项目，等等。

其次，我假设有一些与结构无关的移除方法；他们在seq接口上工作。

由于序列在 Clojure 中是不可变的，我怀疑您实际上在做的是制作原始的廉价副本，只是没有原始项目。这意味着列表理解可以用于删除，但我怀疑它会不必要地冗长。

请给出一些从 Clojure 序列中删除项目的不同方法的惯用示例。

对不起这个困难的问题。

我有一大组序列要通过/或添加数字或替换它们（从不删除任何东西）来纠正，如下所示：

• 1,2,,3 => 1,7,4,3
• 4,,5,6 => 4,4,5,6
• 4,7,8,9 => 4,7,8,9,1
• 4,7 => 4,8
• 4,7,1 => 4,7,2

它从填充的原始序列和样本校正开始。

我希望能够通过计算要纠正的不同 n-gram 的频率来自动纠正序列，第一个样本将变为

• 1=>1
• 2=>7
• 3=>3
• 1,2=>1,7
• 2,3=>7,4,3
• 1,2,3=>1,7,4,3

我会收集这些 n-gram 校正的频率，并且我正在寻找一种方法来计算校正样本数据中可能存在或不存在的新输入的最佳方法。

这似乎类似于SMT。

我有一个类层次结构：

笔记：

• 我并不特别需要基类生成器，所以如果我应该删除它也没问题。
• 如果适用，这是一个 oracle 9i db
• 休眠 3.4 JPA
• Spring 2.5 也可用

谢谢

有没有办法e\d\d多次匹配模式（），将每个模式捕获到一个组中？例如，给定字符串..

..我希望得到四组：

要使用的明显正则表达式是（在 Python 正则表达式中：

..但我也想匹配以下任一：

你似乎不能做(e\d\d)+，或者说你可以，但它只捕获最后一次出现：

我想在单个正则表达式中执行此操作，因为我有多个模式来匹配电视剧集文件名，并且不想复制每个表达式来处理多个剧集：

..等等许多其他模式。

另一件使事情复杂化的事情 - 我希望将这些正则表达式存储在配置文件中，因此不需要使用多个正则表达式和函数调用的解决方案 - 但如果这被证明是不可能的，我将只允许用户添加简单的正则表达式

基本上，有没有办法使用正则表达式捕获重复模式？

给定两个有限的字符串序列A和B，每个序列的长度n，例如：

给出一个有限的索引序列，以便它们对 A 和 B 的集中给出相同的字符串。允许重复。

在此示例中，我找不到解决方案，但例如，如果列表(1,2,2,4)是解决方案，则A1 + A2 + A2 + A4 = B1 + B2 + B2 + B4. 在这个例子中只有两个字符，但已经非常困难了。实际上，找到一个字符的最短解决方案甚至都不是一件容易的事！

我试着想一些事情..例如，字符串长度的总和必须相等，并且对于第一个和最后一个字符串，我们需要相应的字符。但没有别的。我想对于某些字符串来说这是不可能的。任何人都可以想到一个好的算法？

编辑：显然，这是邮政通信问题

没有算法可以决定这样的实例是否有解决方案。如果有，就可以解决停机问题。肮脏的伎俩...

我读到向量不是序列，但列表是。我不确定使用其中一个的理由是什么。似乎向量使用得最多，但这是有原因的吗？

我对自动音乐制作很感兴趣。我正在考虑一个程序，它输入大量的 1 小节琶音（为简单起见，= 固定长度的音符序列）并根据它学到的内容生成自己的序列。

首先，我知道我可以使用字母（二字？三字？）频率分析，仅适用于音符音高，然后根据频率概率生成我的序列。

你知道有没有更高级的算法，也许是专门为音乐序列教授的？