Functions for Hire: Combinations With Repetition

That last post hurt my head a little. I figured there must be a better way to do what I did: so I googled. Before I found a better way, I found that I wasn’t done. I had written functions for permutations, permutations with repetition, and combinations, but still one thing was left: combinations with repetition. Ugh. Dreading having to muddle through the same things again, I madly went at my already written code, changing it and jostling it. One of my fiddles worked. All I had to do was swap the order of removing from the pivotList in the addCombo function, and hey presto, I had a combinations with repetition function. Here it is:

func combosOfLengthWithRep
  <T>(objects: [T], length: Int) -> [[T]] {
  
  return [Int](1...length)
    .reduce([(objects, [T]())]) {
      
      (accum, _) in
      
      accum.flatMap() {addComboWithRep($0, $1)}
      
    }.map() {$0.1}
}

func addComboWithRep
  <T>(var pivotList: [T], prevCombo: [T])
  -> [([T], [T])] {
   
  return (0..<pivotList.count)
    .map() {
 
      _ -> ([T], [T]) in (
 
        pivotList,
        
        prevCombo + [pivotList.removeLast()]
        
      )
  }
}

combosOfLengthWithRep([1, 2, 3], 2)
//[[3, 3], [3, 2], [3, 1], [2, 2], [2, 1], [1, 1]]

Basically, it’s doing the same thing as the last combinations function, except every pivotObject is still left in its pivotList, so it can pair with itself.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s