n 番目の組み合わせ

Squeak Smalltalk

id:sumim:20041206#p1 の続き。c. も比較的、簡単そうなのでトライしてみました。


    

     target chars 
    


target _ 99999999999999999.
chars _ '!"#$%&''()*+,-./:;<=>?@[\]^_`{|}~0123456789AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz'.

^ chars combinations: 16 atATimeAt: target + 1
=> "%'[03569FfLoUXy

定義は、

SequenceableCollection >> combinations: digits atATimeAt: target
   | sum cursor numOfCombs resultDigit |
   sum _ 0.
   cursor _ 1.
   numOfCombs _ (self size - cursor) take: digits - 1.
   [(sum + numOfCombs) < target] whileTrue: [
      sum _ sum + numOfCombs.
      cursor _ cursor + 1.
      numOfCombs _ (self size - cursor) take: digits - 1].
   resultDigit _ self species with: (self at: cursor).
   ^ resultDigit, ((digits - 1) > 0 
      ifTrue: [(self allButFirst: cursor) combinations: digits - 1 atATimeAt: target - sum]
      ifFalse: [self species new])

Integer >> #take: は、レシーバが n、パラメータが r のときの組み合わせの数 n C r を返すメソッドです。