場合分けを数え上げる

今、k種類の椅子がそれぞれ、n1,n2,...,nk個あるとする。そこに、m人の人が座るとする。ただし、なので、全員が座れる。このようなときに、k種類のそれぞれに座る人数を、m1,m2,..,mk ()としたとき、このm1,..,mkのパターンは何通りあるのだろう。。。

Ｒのソース。その使い方

• 使い方

nlist<-c(10,20,15,30,20)
k<-40
Patterns(nlist,k)

• ずらーっと、m1,...,m5の人数が表示されて、最後にパターン数 NumPatterns が出る。こんな感じで。

...
[1]  0  0  9 30  1
[1]  1  0  9 30  0
[1]  0  1  9 30  0
[1]  0  0 10 30  0
$NumPatterns
[1] 59371

• そのソース

Patterns<-function(nlist,k){
 #write.table(res,file="TEXTFILE1.txt",quote=F,sep="\t",row.names=F,col.names=F)
 #sink("TEXTFILE1.txt")
 lenNlist<-length(nlist)

 MinMaxList<-LimitRange(nlist,k)
 #newNlist<-rep(0,lenNlist*2)
 N<-sum(nlist)
 patterncounter<-0
 plusQ<-InitPlusMinMax(MinMaxList$MinList,MinMaxList$MaxList,k)
 loop=plusQ$judge
 while(loop!=0){
  #newNlist<-UpDateNlist(nlist,plusQ$plus)
   #print(plusQ$plus)
  if(plusQ$judge==1){
   print(plusQ$plus)
   patterncounter<-patterncounter+1
  }
  

  plusQ<-UpdatePlusMinMax(plusQ$plus,MinMaxList$MinList,MinMaxList$MaxList,k)
  loop<-plusQ$judge
  
 }
 #sink()
 return(list(NumPatterns=patterncounter))
 
}
InitPlusMinMax<-function(MinList,MaxList,k){
 plus<-MinList
 plus[length(plus)]<-k-sum(plus)+plus[length(plus)]
 if(plus[length(plus)]<=MaxList[length(plus)] && plus[length(plus)]>=MinList[length(plus)]){
  return(list(plus=plus,judge=1))
 }else{
  ans<-UpdatePlusMinMax(plus,MinList,MaxList,k)
  return(list(plus=ans$plus,judge=ans$judge))
 }
}
UpdatePlusMinMax<-function(plus,MinList,MaxList,k){
 #print("update")
 plusLen<-length(plus)
 retplus<-plus
 success<-1
 while(success==1){
  retplus[1]<-retplus[1]+1
  retplus[plusLen]<-retplus[plusLen]-1
  for(i in 1:(plusLen-1)){
   
   if(retplus[i]<=MaxList[i]){
    #if(retplus[plusLen]<MinList[plusLen]){
    # loop<-0
    #}else if(retplus[plusLen]>MaxList[plusLen]){
    # retplus[i]<-retplus[i]+retplus[plusLen]-MaxList[plusLen]
    # retplus[plusLen]<-MaxList[plusLen]
    # if(retplus[i]<=MaxList[i] && retplus[i]>=MinList[i]){
    #  return(list(plus=retplus,judge=1))
    # }else{
    #  loop<-0
    # }
    #}else 
    if(retplus[plusLen]<=MaxList[plusLen] && retplus[plusLen]>=MinList[plusLen]){
     return(list(plus=retplus,judge=1))
    }else{
     return(list(plus=retplus,judge=2))
    }
    #retplus[i]<-retplus[i]+1
    #retplus[plusLen]<-retplus[plusLen]-1
   }
   retplus[plusLen]<-retplus[plusLen]+retplus[i]-MinList[i]-1
   retplus[i]<-MinList[i]
   retplus[i+1]<-retplus[i+1]+1
   if(i==(plusLen-1)){
    #if(retplus[i+1]>MaxList[i+1]){
     return(list(plus=retplus,judge=0))
    #}
   }
  }
 }
 
 
 #return(list(plus=retplus,judge=0))
}
LimitRangeKeta<-function(nlist,k,keta,loopMax=10){
 MinList<-rep(0,keta)
 MaxList<-nlist[1:keta]
 dif<-1
 loop<-0
 while(dif!=0 && loop<loopMax){
  loop<-loop+1
  tmpMinList<-UpdateMinList(MinList,MaxList,k)
  tmpMaxList<-UpdateMaxList(MinList,MaxList,k)
  dif<-sum(abs(tmpMinList-MinList)+abs(tmpMaxList-MaxList))
  MinList<-tmpMinList
  MaxList<-tmpMaxList
 }
 return(list(MinList=MinList,MaxList=MaxList))

}
LimitRange<-function(nlist,k,loopMax=10){
 MinList<-rep(0,length(nlist))
 MaxList<-nlist
 LEN<-length(nlist)
 dif<-1
 loop<-0
 while(dif!=0 && loop<loopMax){
  #print("#")
  loop<-loop+1
  #print(loop)
  tmpMinList<-UpdateMinList(MinList,MaxList,k)
  tmpMaxList<-UpdateMaxList(MinList,MaxList,k)
  #print(tmpMinList)
  #print(tmpMaxList)
  dif<-sum(abs(tmpMinList-MinList)+abs(tmpMaxList-MaxList))
  MinList<-tmpMinList
  MaxList<-tmpMaxList
 }
 return(list(MinList=MinList,MaxList=MaxList))
}



UpdateMinList<-function(MinList,MaxList,k){
 list<-MinList
 sumMax<-sum(MaxList)
 for(i in 1:(length(list))){
  if(MinList[i]<k-sumMax+MaxList[i]){
   list[i]<-k-sumMax+MaxList[i]
  }
 }
 return(list)
}
UpdateMaxList<-function(MinList,MaxList,k){
 list<-MaxList
 sumMin<-sum(MinList)
 for(i in 1:(length(list))){
  if(MaxList[i]>k-sumMin+MinList[i]){
   list[i]<-k-sumMin+MinList[i]
  }
 }
 return(list)
}

InitPlus<-function(nlist,k){
 retplus<-rep(0,length(nlist))
 sofar<-k
 for(i in 1:length(nlist)){
  if(sofar>=nlist[i]){
   retplus[i]<-nlist[i]
   sofar<-sofar-nlist[i]
  }else{
   retplus[i]<-sofar
   return(retplus)
  }
 }
 return(retplus)
}
UpdatePlus<-function(plus,nlist){
 plusLen<-length(plus)
 totalplus<-sum(plus)
 plus[1]<-plus[1]+1
# if(plusLen>2){
  for(i in 1:plusLen){
   #print(plus)
   if(plus[i]>nlist[i]){
    #plus[plusLen]<-plus[plusLen]+plus[i]-1
    plus[i]<-0
    if(i<plusLen){
     plus[i+1]<-plus[i+1]+1
    }else{
     plus[i]<-plus[i]+1
     return(plus)
    }
   }else{
    return(plus)
   }
  }
 #}
 return(plus)
}
UpDateNlist<-function(nlist,plus){
 newNlist<-rep(0,length(nlist)*2)
 for(i in 1:length(nlist)){
  newNlist[i*2-1]<-plus[i]
  newNlist[i*2]<-nlist[i]-plus[i]
 }
 return(newNlist)
}
lExp<-function(nlist,LogFact){
 ret<-0
 for(i in 1:length(nlist)){
  ret<-ret+LogFact[nlist[i]+1]
 }
 return(ret)
}

MakeLogFact<-function(n){
 ret<-rep(0,n+1)
 ret[1]<-0
 for(i in 2:(n+1)){
  ret[i]<-ret[i-1]+log(i-1)
 }
 return(ret)
}