My combinations algorithm

Why I do this 

When I solve problems in leetcode, I often have to use Python’s built-in combination function.

It’s fine when I only need to code with Python.

But it can get tricky if I need to use CPP or Golang to solve the same problem.

Unless I know exactly how the combinations function works, I won’t be able to rewrite it with CPP or Golang.

Then I start to rock. I spent a day trying to write my own version of combinations in Python.

Solutions

And then I did it. Instead of combinations, I wrote a permutations algorithm by accident.

def my_combinations(source_list, length_limit):
    result = []

    def loop(l, n, left_list):
        if n == length_limit:
            return 
        for i, e in enumerate(left_list):
            new = l+[e]
            if len(new) == length_limit:
                result.append(new)
                print(new)
            loop(new, n+1, left_list[:i] + left_list[i+1:])

    loop([], 0, source_list)

    #print(result)
    #return result

l = [1,2,3,4]
my_combinations(l, 3)

# shit, I have accidentally written a permutation algorithm

Then, on the second day morning, which is today. I spent 2 minutes look at my solution. Thinking about where I probably go wrong.

Suddenly, I deleted a few codes, Boom! I got the combinations algorithm that I just need:

def my_combinations(source_list, length_limit):
    result = []

    def loop(l, n, left_list):
        if n == length_limit:
            return 
        for i, e in enumerate(left_list):
            new = l+[e]
            if len(new) == length_limit:
                result.append(new)
                print(new)
            loop(new, n+1, left_list[i+1:])

    loop([], 0, source_list)

    #return result

l = [1,2,3,4]
my_combinations(l, 3)

# shit, I just spent 2 minutes turning the permutation algorithm into a combination algorithm. great!

Golang version:

package main

import "fmt"

var length_limit = 0
var result = make([][]int, 0)

func loop(l []int, n int, left_list []int) {
    if n == length_limit {
        return
    }
    for i, e := range left_list {
        var new = append(l, e)
        if len(new) == length_limit {
            result = append(result, new)
        }
        loop(new, n+1, left_list[i+1:])
    }
}

func my_combinations(source_list []int, length int) [][]int {
    result = result[:0]
    length_limit = length
    loop([]int{}, 0, source_list)
    return result
}

func main() {
    fmt.Println(my_combinations([]int{1, 2, 3, 4}, 2))
}

CPP is kind of special, I couldn’t just get a sub-vector from a vector. But I’ll figure it out. Maybe make my own implementation of python’s [:] in the future.

​