庄周梦蝶

生活、程序、未来
   :: 首页 ::  ::  :: 聚合  :: 管理

amb解决排列组合问题

Posted on 2009-10-19 11:37 dennis 阅读(2906) 评论(2)  编辑  收藏 所属分类: 动态语言计算机科学与基础
  看到这么一个题目:
    {3,2,2,6,7,8}排序输出,7不在第二位,68不在一起。
 
  这样的题目似乎避免不了遍历,关键还在于过滤条件的安排,怎么让过滤的范围尽量地小。通常的做法是循环遍历,对于类似Prolog这样的语言来说,由于内置了推理引擎,可以简单地描述问题,让引擎来帮你做递归遍历,解决这类问题是非常简单的。Prolog好久没写,以Ruby的amb操作符为例来解决这道题目:

#结果为hash,去重
$hash={}
amb
=Amb.new
array
=[3,2,2,6,7,8]
class << array
 alias remove delete
 
def delete(*nums)
   result
=dup
   nums.each do 
|n|
    result.delete_at(result.index(n)) 
if result.index(n)
   end
   result
 end
end
#从集合选元素
one=amb.choose(*array)
two
=amb.choose(*(array.delete(one)))
three
=amb.choose(*(array.delete(one,two)))
four
=amb.choose(*(array.delete(one,two,three)))
five
=amb.choose(*(array.delete(one,two,three,four)))
six
=amb.choose(*(array.delete(one,two,three,four,five)))

#条件1:第二个位置不能是7
amb.require(two!=7)
#条件2:6跟8不能一起出现
def six_eight_not_join(a,b)
   
"#{a}#{b}"!="68"&&"#{a}#{b}"!="86"
end
amb.require(six_eight_not_join(one,two))
amb.require(six_eight_not_join(two,three))
amb.require(six_eight_not_join(three,four))
amb.require(six_eight_not_join(four,five))
amb.require(six_eight_not_join(five,six))

#条件3:不重复,利用全局hash判断
def distinct?(one,two,three,four,five,six)
  
if $hash["#{one},#{two},#{three},#{four},#{five},#{six}"].nil?
     $hash[
"#{one},#{two},#{three},#{four},#{five},#{six}"]=1 #记录
     true
  
else
     false
  end
end
amb.require(distinct?(one,two,three,four,five,six))
puts 
"#{one},#{two},#{three},#{four},#{five},#{six}"
amb.failure


   三个条件的满足通过amb.require来设置,这里安排的只是一种顺序,可以根据实际测试结果来安排这些条件的顺序以最大程度地提高效率。代码注释很清楚了,我就不多嘴了。Ruby amb的实现可以看这里。什么是amb可以看这个



评论

# re: amb解决排列组合问题  回复  更多评论   

2009-10-19 17:48 by 淘宝皇冠大全
谢谢分享!

# re: amb解决排列组合问题  回复  更多评论   

2009-10-20 03:18 by 美容
amb解决排列组合问题 good

只有注册用户登录后才能发表评论。


网站导航: