如何生成列表元素的所有可能组合？
例如,给定列表[1,2,3],我想设计一个谓词,其形式comb([1,2,3], L).应返回以下答案L:
[1]
[2]
[3]
[1,2]
[2,1]
[1,3]
[3,1]
[2,3]
[3,2]
[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]
例如,对于元素a,b,c,d,有5种可能的方法来获取相邻元素并将它们简化为单个元素,其中一次必须组合两个元素(下面用括号表示):
(((ab)c)d), ((a(bc))d), ((ab)(cd)), (a((bc)d)) and (a(b(cd)))
第一个示例相乘a*b,然后将该乘积乘以,然后将该乘积c乘以d.第二个示例首先相乘b*c,然后将该乘积乘以,然后将该乘积a乘以d.
2n个元素的任何有效的括号表达式也会一定ñ (和n )与,从左至右,有至少许多人总是财产(作为).
我知道对于n个数字,方式的数量是第(n-1)个加泰罗尼亚数字.但是,如何准确地生成所有结果分组？
谢谢
(顺便说一句:这个问题有超过160个等效公式,都是基于加泰罗尼亚数字列举的不同组合对象.有关这些问题的最新列表,请参阅Richard Stanley的加泰罗尼亚语附录.)
我正在研究一个依赖于FParsec 0.9.2.0的F#Type Provider.它取决于FSharp.Core 4.0.0.0.当我尝试使用F#Type Provider时,出现此错误:
{"无法加载文件或程序集'FSharp.Core,Version = 4.0.0.0,Culture = neutral,PublicKeyToken = b03f5f7f11d50a3a'或其中一个依赖项.系统找不到指定的文件.":"FSharp.Core,Version = 4.0.0.0,Culture = neutral,PublicKeyToken = b03f5f7f11d50a3a"}
===预绑定状态信息===
日志:DisplayName = FSharp.Core,Version = 4.0.0.0,Culture = neutral,PublicKeyToken = b03f5f7f11d50a3a(完全指定)
LOG:Appbase = file:/// C:/ Program文件(x86)/ Microsoft Visual Studio 11.0/Common7/IDE/
LOG:初始PrivatePath = NULL
调用程序集:FParsec,Version = 0.9.2.0,Culture = neutral,PublicKeyToken = e5c8267bb3bd1265.
我尝试添加a Froto.Gen.dll.config和a FParsec.dll.config,两者都有这个:
<?xml version="1.0" encoding="utf-8"?>
<configuration>
<runtime>
<assemblyBinding xmlns="urn:schemas-microsoft-com:asm.v1">
<dependentAssembly>
<assemblyIdentity name="FSharp.Core" publicKeyToken="b03f5f7f11d50a3a" culture="neutral" />
<bindingRedirect oldVersion="4.0.0.0" newVersion="4.3.0.0" />
</dependentAssembly>
</assemblyBinding>
</runtime>
</configuration>
没运气.有任何想法吗？我的下一个行动计划是建立一个新的FParsec.dll,但这并不总是有用.
这是场景:
E:\<directories>\fsharp-tapl\arith从fsx文件向F#Interactive发送命令
> System.Environment.CurrentDirectory;;
val it : string = "C:\Users\Eric\AppData\Local\Temp"
我没想到Temp目录,但它有意义.
> #r @"arith.exe"
Examples.fsx(7,1): error FS0082: Could not resolve this reference.
Could not locate the assembly "arith.exe".
Check to make sure the assembly exists on disk.
If this reference is required by your code, you may get compilation errors.
(Code=MSB3245)
Examples.fsx(7,1): error FS0084: Assembly reference 'arith.exe' was not found
or is invalid
#r命令错误显示F#Interactive当前不知道arith.exe的位置.
> #I @"bin\Debug"
--> Added 'E:\<directories>\fsharp-tapl\arith\bin\Debug'
to library …我刚开始学习F#.本书使用以下符号:
let name() = 3
name()
与此不同的是:
let name = 3
name
？
假设我们将考虑具有长度2n且n可能是大约的二进制数1000.我们正在寻找具有以下特性的kth数字(k受限制10^9):
1's等于0's可以描述如下的金额:#(1) = #(0)0's的1's.在否定句子后可能更容易理解它,即:没有包含1's多于的前缀0's.基本上就是这样.所以为了说清楚,让我们做一些例子:
n=2,k=2
我们必须采用二进制数量的长度2n:
0000
0001
0010
0011
0100
0101
0110
0111
1000
and so on...
现在我们必须找到2nd满足这两个要求的数字.所以我们看到的0011是第一个,0101也是第二个.如果我们改变k=3,则答案不存在,因为存在具有相同数量的相反位的数字,但是因为0110存在前缀,011所以数字不满足第二约束,并且对于具有1最高有效位的所有数字也是如此.
那么我到目前为止所做的算法呢？
好吧,我的第一个想法是生成所有可能的位设置,并检查它是否具有这两个属性,但生成它们都将采用O(2^(2n))哪个不是一个选项n=1000.
另外我意识到没有必要检查所有小于0011for n=2,000111for n=3等的数字......坦率地说,那些最重要位的一半仍保持"未被触及",因为这些数字不可能满足#(1) = #(0) …
在线整数序列百科全书支持搜索包含您的查询作为子序列的序列,例如.搜索subseq:212,364,420,428将返回8*n+4序列.(http://oeis.org/search?q=subseq:212,364,420,428)
这个惊人的功能显然是由Russ Cox实现的http://oeis.org/wiki/User:Russ_Cox/OEIS_Server_Features实现的,但是没有用它实现的算法来指定.
我想知道它是如何完成的.对于搜索引擎来说,每次搜索显然要经过近一百万个序列是不切实际的.只保留一个索引(这是同一个Russ Cox对谷歌代码正则表达式搜索的方式)的第一个数字和暴力强迫其余的也不起作用,因为数字0几乎在所有序列中.实际上,一些查询0 1匹配总数据库的高百分比,因此算法需要对所需输出大小敏感的运行时间.
有谁碰巧知道这个功能是如何实现的？
这是我的功能:
let rec applyAll rules expr =
rules
|> List.fold (fun state rule ->
match state with
| Some e ->
match applyRule rule e with
| Some newE -> Some newE
| None -> Some e
| None -> applyRule rule expr) None
|> Option.bind (applyAll rules)
它采用一组规则并应用它们,直到输入表达式尽可能减少.我可以重写它Option.bind是一个match表达式,它显然会利用尾部调用优化.但是,这对我来说更优雅,所以我希望保持原样,除非它不必要地消耗堆栈.F#是否使用此代码执行TCO？
编辑:此代码始终返回None; 我会解决这个问题,但我认为这个问题仍然有意义.
我见过这样定义的函数:
let private applyTarget (logger:#ILogger) ceiling target =
logger.Debug "enforce ceiling"
match target > ceiling with
| true -> ceiling | false -> target
什么是#符号中的签名是什么意思？
什么区别logger:ILogger和logger:#ILogger？
新的F#开发人员,长期以来的C#开发人员.作为学习F#的练习,我正在通过Eric Lippert关于图形着色的系列工作,从C#转换为F#.我目前正在做第二部分.
最初的C#在博文中 - 这是迄今为止的F#翻译 - 但是它没有编译:
type BitSet = struct
val bits : int
private new(b) = { bits = b }
static member Empty = BitSet(0)
member this.Contains (item:int) = (this.bits &&& (1<<< item)) <> 0
member this.Add (item:int) = BitSet(this.bits ||| (1 <<< item))
member this.Remove (item:int) = BitSet(this.bits &&& ~~~(1<<<item))
member this.Bits = seq {
for item in 0..31 do
if this.Contains(item) then
yield item
}
end
这会产生非常神秘的错误"错误FS0406:byref-typed变量'this'以无效方式使用.Byrefs不能被闭包捕获或传递给内部函数"来自Bits:seq <int>的定义.
奇怪的是,将关键字"struct"更改为"class"会产生有效的代码.从C#的角度来看,这似乎是胡说八道,但我确信它背后有一个合理的原因.现在的问题是-如何应我写的位功能？为理解这一点,我需要理解的基本F#原则是什么？