提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

amb解决排列组合问题

2023-03-14 10:30:12 时间
看到这么一个题目：
    {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可以看这个。

文章转自庄周梦蝶  ，原文发布时间2009-10-19

相关文章