Oct
30
比赛的起因是这样的,@Tranch同学在SegmentFault.com提了个问题,求一个代码,可以列出字符串"qwerty"被 "." 分割的所有情况,比如 q.werty qwe.rty q.w.e.r.t.y 等等。
这个问题其实很简单,qwerty中间最多可以塞5个". ",每个地方用1表示塞,0表示不塞,也就是正好循环 2^5 次就行了(对于全0的情况不做特别要求,可有可无),实现起来也非常容易,这里是写这篇文章时补充的一个C语言实现:
不过当时没想写这样的代码,而是特意脑抽用python写了个递归的版本:
因为前一段时间看到 这里用21行python代码实现了一个拼写检查器,于是一时兴起,简化成了这个等价但是更难读的版本:
虽然已经很短了,但是我还是想知道,是否有更简单些的实现(一定程度上可以忽略效率和可读性),于是在MSTC的群里发了这个问题,简单起见,把字符串改成了"abcde",问问有没有更短的代码来给出各种组合。
然后 @杭神 扔了个代码出来,被喷“能不能用人话”。这段代码看起来是有些费解,主要思路是,生成 ['****', '***.', '**..', '*...', '....'] 的各种排列,然后用zip('abcd', p)交错组合起来(再删掉'*'):
然后 @霄妹纸 说,实际上那个是笛卡尔积。于是用上itertools.product,再改善下语法,可以写成这样,看起来就清晰多了:
@霄妹纸 还给出了另外两个奇葩的代码,一个是 C 的,充分利用和宏、main函数的参数和递归:
另一个是ruby的:
由于不懂ruby语法,所以这个代码我也只能勉强看看,不过思路上跟上面的python代码是一样的,使用笛卡尔积生成组合序列,然后再与'abcde'交错组合。
结果是,ruby赢了(58个字节),python紧随其后(80字节,不包括import),C语言则意外地以106个字节的代码实现了这个目标。
这个问题从实践的角度上来说没有太大意义,不过可以对比下,不同的语言(C/Ruby/Python)、不同的编程范型(过程式/函数式)的表达方式,一窥函数式编程的魅力~
转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
这个问题其实很简单,qwerty中间最多可以塞5个". ",每个地方用1表示塞,0表示不塞,也就是正好循环 2^5 次就行了(对于全0的情况不做特别要求,可有可无),实现起来也非常容易,这里是写这篇文章时补充的一个C语言实现:
#include <stdio.h>
int main()
{
char str[] = "qwerty";
int i, j;
for (i = 0; i < (1<<5); i++)
{
for (j = 0; j < 5; j++)
{
putchar(str[j]);
if (((i >> j) & 1) == 1)
putchar('.');
}
printf("y\n");
}
return 0;
}
int main()
{
char str[] = "qwerty";
int i, j;
for (i = 0; i < (1<<5); i++)
{
for (j = 0; j < 5; j++)
{
putchar(str[j]);
if (((i >> j) & 1) == 1)
putchar('.');
}
printf("y\n");
}
return 0;
}
不过当时没想写这样的代码,而是特意脑抽用python写了个递归的版本:
def add_dots_l(str):
ret = []
for i in range(1, len(str)):
left = str[:i]
right = str[i:]
ret.append(left + '.' + right)
ret += [j + '.' + right for j in add_dots_l(left)]
ret += [left + '.' + j for j in add_dots_l(right)]
return set(ret)
ret = []
for i in range(1, len(str)):
left = str[:i]
right = str[i:]
ret.append(left + '.' + right)
ret += [j + '.' + right for j in add_dots_l(left)]
ret += [left + '.' + j for j in add_dots_l(right)]
return set(ret)
因为前一段时间看到 这里用21行python代码实现了一个拼写检查器,于是一时兴起,简化成了这个等价但是更难读的版本:
def add_dots(s):
r = [s[:i] + '.' + s[i:] for i in range(1, len(s))]
r += [j + '.' + s[i:] for i in range(1, len(s)) for j in add_dots(s[:i])]
r += [s[:i] + '.' + j for i in range(1, len(s)) for j in add_dots(s[i:])]
return set(r)
r = [s[:i] + '.' + s[i:] for i in range(1, len(s))]
r += [j + '.' + s[i:] for i in range(1, len(s)) for j in add_dots(s[:i])]
r += [s[:i] + '.' + j for i in range(1, len(s)) for j in add_dots(s[i:])]
return set(r)
虽然已经很短了,但是我还是想知道,是否有更简单些的实现(一定程度上可以忽略效率和可读性),于是在MSTC的群里发了这个问题,简单起见,把字符串改成了"abcde",问问有没有更短的代码来给出各种组合。
然后 @杭神 扔了个代码出来,被喷“能不能用人话”。这段代码看起来是有些费解,主要思路是,生成 ['****', '***.', '**..', '*...', '....'] 的各种排列,然后用zip('abcd', p)交错组合起来(再删掉'*'):
from itertools import permutations as p #itertools.permutations是python2.6引入的
map(lambda p: ''.join(j for i in zip('abcd', p) for j in i).replace('*', '') + 'e', [''.join(y) for x in map(lambda i: set(p('*' * (4-i) + '.' * i)), range(5)) for y in x])
map(lambda p: ''.join(j for i in zip('abcd', p) for j in i).replace('*', '') + 'e', [''.join(y) for x in map(lambda i: set(p('*' * (4-i) + '.' * i)), range(5)) for y in x])
然后 @霄妹纸 说,实际上那个是笛卡尔积。于是用上itertools.product,再改善下语法,可以写成这样,看起来就清晰多了:
from itertools import product #itertools.product也是2.6引入的
map(lambda p: ''.join(i + j for i, j in zip('abcd', p)) + 'e', product(['.', ''], repeat = 4))
map(lambda p: ''.join(i + j for i, j in zip('abcd', p)) + 'e', product(['.', ''], repeat = 4))
@霄妹纸 还给出了另外两个奇葩的代码,一个是 C 的,充分利用和宏、main函数的参数和递归:
#define z(a,b) printf(#a"%s",(x>>b)&1?".":""),
main(x){z(a,3)z(b,2)z(c,1)z(d,0)puts("e");16-x&&main(x+1);}
main(x){z(a,3)z(b,2)z(c,1)z(d,0)puts("e");16-x&&main(x+1);}
另一个是ruby的:
p ("b".."e").inject(["a"]){|a,q|a.product [q,"."+q]}.map &:join
如果是ruby 1.9+的话,还可以再少几个字符:p (?b..?e).inject([?a]){|a,q|a.product [q,?.+q]}.map&:join
由于不懂ruby语法,所以这个代码我也只能勉强看看,不过思路上跟上面的python代码是一样的,使用笛卡尔积生成组合序列,然后再与'abcde'交错组合。
结果是,ruby赢了(58个字节),python紧随其后(80字节,不包括import),C语言则意外地以106个字节的代码实现了这个目标。
这个问题从实践的角度上来说没有太大意义,不过可以对比下,不同的语言(C/Ruby/Python)、不同的编程范型(过程式/函数式)的表达方式,一窥函数式编程的魅力~
欢迎扫码关注:
转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。