对n组字符串无重复全排列的算法.txt

学习(编程技巧_编程知识_程序代码),是学习编程不可多得的学习精验

对N组字符串无重复全排列的算法
 

--------------------------------------------------------------------------------
 
第八军团 时间：2004-1-18 11:02:34 
   
对 N 组 字符串无重复全排列的算法 
        要点：函数采用递归形式，理论上做到对任意 N 进行全排列 
        0<N<257; 
        每组字符数不限; 
    可以进行 N 选 X 形式的全排列（0<X<N+1） 
      
函数参数：as_value[]     string   value         存放需要全排列的字符串； 
        as_nLevel       int     value         N - X   ； 
  as_char         string   value         字符串排列起来用于分隔的字符； 
  as_allowrepeat boolean value         全排列允许重复，取值含义： 
                  true： 允许全排列重复   
        false：全排列不允许重复 
        as_value不存在重复元素也取值true，提高效率； 
  as_list[256]   int     reference     函数工作用的内部数组； 
  as_return[]     string   reference     存放生成的全排列字符串。 
  
调用详解：1.必须定义的变量   string as_return[];int as_list[256] 
  2.as_return,as_list切勿赋值 
        3.把需要排列的 N 组字符或字符串赋值给as_value[] 
  4.as_char，用来定义分隔生成的字符串的字符，不需要分隔就不用赋值 
  5.as_nLevel=N - X 
  5.调用本函数f_string_compages(as_value,as_nLevel,as_char,as_allowrepeat,as_list,as_return) 
  6.as_return[]就是生成的全排列的字符串序列 
  
特殊调用：要求函数返回 N 全排列的所有方案，即自然数系列的全排列， 
        设N=4，返回1 2 3 4、1 3 2 4、1 4 3 2........... 
  调用格式如下：f_string_compages({'N=4'},as_nLevel,as_char,true,as_list,as_return) 
                即赋值as_value数组第一个元素为字符串：'N=4' 

返回代码：0   成功 
        -1 N>256 或 N<1 
  -2 X<0   或 X>N 
  
N 选 X 全排列的估算： 
        N=X     全排列为 N! 
  0<x<N   全排列为 N!/(N-X)! 
  

实际使用代码演示： 
//对'AB','01','05','21','17','09'进行6选4的全排列 
string as_return[] 
int as_list[256] 
f_string_compages({'AB','01','05','21','17','09'},6 -4,' ',true,as_list,as_return) 

//接下去是对数组as_return[]进行处理，输出、打印........ 
//程序略 

========================================*/ 
//   [e-mail] 2003-06-05 

int nCount,nJudge,key,num,nCount1 
long l,i,k,t 
string s 
num=upperbound(as_value) 
if num<1 or num>256 then return -1   
  if pos(upper(as_value[1]),'N=')<>0 then 
    num=integer(mid(as_value[1],pos(upper(as_value[1]),'N=')+2,100)) 
  if num<1 or num>256 then return -1   
end if 
if as_nLevel<0 or as_nlevel>num then return -2 
  as_nLevel++ 
  if(as_nLevel>NUM) then   //求得一种组合形式 
  l=upperbound(as_return) 
  l++ 
  s='' 
      for nCount=1 to NUM //进行字符串排列 
    if as_List[nCount]<>0 then 
    if pos(upper(as_value[1]),'N=')=0 then 
      s=s+as_value[as_List[nCount]+as_char 
    else 
      s=s+string(as_List[nCount])+as_char 
    end if 
    end if 
  next 

  s=left(s,len(s) -1)   
  t=0 
  if as_allowrepeat=false then //寻找重复的字符串组合 
    k=upperbound(as_return)   
    for i=1 to k 
    if as_return=s then 
    t=1 
    exit 
    end if 
    next                     
  end if               //寻找end 
  if t=0 then as_return[l]=s 
      as_nLevel -- 
      return as_nLevel 
end if 
  for nCount=1 to NUM 
      key=0; 
      for nJudge=1 to as_nLevel -1 
          if nCount=as_List[nJudge] then 
              key=1 
              exit 
          end if 
  next 
      if key=0 then 
          as_List[as_nLevel]=nCount 
          as_nLevel=f_string_compages(as_value,as_nLevel,as_char,as_allowrepeat,as_List,as_return) 
  end if 
next 
as_nLevel -- 
return as_nLevel