amb解决排列组合问题

看到这么一个题目:
    {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

时间: 2024-11-01 10:58:10

amb解决排列组合问题的相关文章

C语言实现的排列组合问题的通用算法、解决方法_C 语言

尽管排列组合是生活中经常遇到的问题,可在程序设计时,不深入思考或者经验不足都让人无从下手.由于排列组合问题总是先取组合再排列,并且单纯的排列问题相对简单,所以本文仅对组合问题的实现进行详细讨论.以在n个数中选取m(0<m<=n)个数为例,问题可分解为: 1. 首先从n个数中选取编号最大的数,然后在剩下的n-1个数里面选取m-1个数,直到从n-(m-1)个数中选取1个数为止. 2. 从n个数中选取编号次小的一个数,继续执行1步,直到当前可选编号最大的数为m. 很明显,上述方法是一个递归的过程,也

计算排列组合的php代码

前些天因为业务需要写了一段计算排列组合的代码,今天整理了一下,以备后用 <?php/** * 要解决的数学问题    :算出C(a,1) * C(b, 1) * ... * C(n, 1)的组合情况,其中C(n, 1)代表从n个元素里任意取一个元素 * * 要解决的实际问题样例:某年级有m个班级,每个班的人数不同,现在要从每个班里抽选一个人组成一个小组, *                       由该小组来代表该年级参加学校的某次活动,请给出所有可能的组合 */ /* ##########

集合-排列组合 找真子集 不包含空集

问题描述 排列组合 找真子集 不包含空集 ** void solve(int cur_totalvar, int nextVar){ // 解决向量选择子集并求和 放到向量 for (int i = 0; i<cur_totalvar; ++i){ printf("%f ",num[i]); printf("chengchangshengn"); // ??? 放入变量 sunMombre.sun += num[i]; } if(cur_totalvar){

数组-想找到一个排列组合的算法

问题描述 想找到一个排列组合的算法 比如数组里有1-500的非连续数值, 当传入345这样一个数值进来时, 可以从数组里拿出N个数值相加得到345这个值的方案, 且要求相加数值个数最少,或最接近的组合优先获取出来 解决方案 2009年1月15日 沈阳 晴?? 为解决1月7日遇到的排列组合的难题,进行了以下题目的研究,并用C#实现了一个非递归的算法.有一个List,List中存有N个对象,要求做出这N个对象所有无序组.?数学公式:组合数=C(n1) + C(n2) + ...... + C(nn)

转 排列组合

(常考)错位排列 有N封信和N个信封,每封信都不装在自己信封里的排列种数记作Dn,则 D1=0,D2=1,D3=2,D4=9,D5=44,D6=265 一.相邻问题---捆绑法 不邻问题---插空法 对于某几个元素不相邻的排列问题,可先将其他元素排好,再将不相邻元素在已排好的元素之间及两端空隙中插入即可. [例题1]一张节目表上原有3个节目,如果保持这3个节目的相对顺序不变,再添进去2个新节目,有多少种安排方法? A.20 B.12 C.6 D.4 [答案]A. [解析] 以下内容需要回复才能看

排列组合算法问题

问题描述 比如0102030405060708取其中的任意6个组合输出所有的组合字符串 解决方案 解决方案二:publicvoidCombinationCollocate(List<string>AStrings,stringANumbers,stringAPath,intALen){if(APath.Length>=ALen){AStrings.Add(APath);return;}for(inti=0;i<ANumbers.Length;i++){stringvNumbers=

算法 排列组合 迭代-把一个N位的数组,每M个组成一组新的数组,内容不重复,怎么做?

问题描述 把一个N位的数组,每M个组成一组新的数组,内容不重复,怎么做? 把一个N位的数组,每M个组成一组新的数组,内容不重复. M<=N 这个排列组合问题用java迭代或者别的什么方法怎么解决. 困扰我一天了.

使用php计算排列组合的方法_php实例

前些天因为业务需要写了一段计算排列组合的代码,今天整理了一下,以备后用 复制代码 代码如下: <?php/** * 要解决的数学问题    :算出C(a,1) * C(b, 1) * ... * C(n, 1)的组合情况,其中C(n, 1)代表从n个元素里任意取一个元素 * * 要解决的实际问题样例:某年级有m个班级,每个班的人数不同,现在要从每个班里抽选一个人组成一个小组, *                       由该小组来代表该年级参加学校的某次活动,请给出所有可能的组合 *//*

母函数与排列组合

在谈论母函数问题之前,我们先看一个简单的问题描述:假如有两组数据(A,B)和(C,D),每组中选出一个构成一个组合,总共有几种选法?很显然总共有4种选法:AC,AD,BC,BD.而且很容易联想到这个式子(A+B)*(C+D)=A*C+A*D+B*C+B*D.式子中的几个乘积项就是上面的4种选法.假如把问题换一下:每组中选出一个或0个数据构成组合,总共有几种组合?那么结果就变成:{空},A,B,C,D,AC,AD,BC,BD,而式子(1+A+B)*(1+C+D)=1+C+D+A+A*C+A*D+B