SPL=Surpass Python Language
5 回帖  •  391 浏览  • 
待解决      ...

排列组合两种递归写法的效率比较

 
集算器(187) 递归(2) 回溯(1) 剪枝(1) SPL插件(5)

查了一下论坛，很少有关 SPL 递归的文章。这里用 SPL 写了两种 m 选 n 组合的递归写法，模拟深度优先与回溯。写法可能不成熟，因为运行效率不是很理想，但同样的手法，在 JavaScript，VBA 和 Python 中的运行效率是很高的，甚至在 Power Query 里的效率也很理想。所以，想得到 SPL 大佬的指点，看能不能优化这两种写法，或者有没有其他的写法可以让排列组合的执行效率提高。此贴主要讨论组合的写法，因为组合可以无序，相对不那么复杂。场景很简单，从 m 个数中选出 n 个数，得到不重复组合。为了方便剪枝，例子中用到的数组（序列），都是升序排列的。此贴中就用 20 选 5 来做例子，因为 20.() 序列中没有重复的数字出现，所以没有不重复剪枝发生，但语句中还是写了剪枝方法。

第一种写法，模拟深度优先。IDE 里的语句如下：

A B C
1 >a=20.() >n=5
2 func
3 if B2==0 return [[]]
4 return A2.(if(~==~[-1],[],func(A2,A2.m(#+1:),B2-1)).(get(1)|~)).conj()
5 >t=now()
6 =func(A2,a,n)
7 >output(a.len()/"个数中选出"/n/"个数")
8 >output("生成"/A6.len()/"个不重复组合")
9 >output("耗时"/interval@ms(t,now())/"毫秒")

运行之后可以看到，这个写法的效率还是可以的。本机测得，20 选 5 生成 15504 个不重复组合
耗时 218 毫秒。如果是 26 选 7，甚至是 35 选 7，那就是另一种速度了。

第二种写法，模拟回溯。这个是 SPL 里最迷惑的写法，照理这个写法的效率是很高的，在其他语言环境中的运行效率很高。但在 SPL 里却是出奇的慢。IDE 里的语句如下：

A B C D
1 >arr=20.() >len=arr.len() >n=5
2 [] >path=[] // m 选 n
3 func
4 if path.len()==n >A2|=[path.m(:)] //path 要复制一份
5 for A3,len-n+path.len()+1 >v=arr.m(B5)
6 if v==null return
7 if B5>A3 && v==arr.m(B5-1) next B5
8 >path|=v
9 >func(A3,B5+1) // 注意此处入参是 B5+1, 不是 A3+1
10 >path.delete(-1)
11 return A2 clear A1:C2
12 >t=now()
13 =func(A3,1)
14 >output(len/"个数中选出"/n/"个数")
15 >output("生成"/A13.len()/"个不重复组合")
16 >output("耗时"/interval@ms(t,now())/"毫秒")

运行之后，本机测得，20 选 5 生成 15504 个不重复组合，耗时 15469 毫秒。1 万多个结果耗时 15 秒这个效率不能接受，不知道是哪里有问题，在其他语言环境中，这样的回溯剪枝 20 选 5 都是几十毫秒。

当然，还可以有另一种写法，用 xjoin，加上一定的剪枝，也能得到结果，速度还可以。但这不是递归写法，不在此贴讨论范围。

这种组合有一个实际运用场景，就是凑数，比如 100 个数里选出和等于目标值的所有组合，或者选出 n 个数的值使其和等于目标值。这次就不写了，无非就是加个判断条件和剪枝条件。先看看能不能提高效率，麻烦 SPL 大佬指点一二。

Thx in advance!

集算器(187) 递归(2) 回溯(1) 剪枝(1) SPL插件(5)