Number of k-combinations for all N

user_3577360 0
Viewed 264

I'm attempting to write an algo that returns an array of all possible combinations for values 0, 1, and 2 for length n.

For example where n = 2:

00

01

02

10

11

12

20

21

22

Code that I have started but far from right or finished:

func main() {
    var results []string
    matches := rangeSlice(2)

    for a := 0; a < len(matches); a++ {
        for b := 0; b < 3; b++ {
            matches[(len(matches) - a) - 1] = b
            results = append(results, strings.Join(convertValuesToString(matches), ""))
        } 
    }

    printResults(results)
}

Your help would be much appreciated!

go algorithm
3 Answers

This is just counting (in base k). You could do just that --convert consecutive integers to base k -- but that's a lot of divides and remainders, so you might as well use a simpler approach.

  1. Start with n 0s, and then repeat as many times as you can:
  2. Change all the trailing k-1 to 0, then add 1 to the previous element. If there is no previous element, you're done.

If it helps to understand, you could try this with k=10, which is ordinary decimal counting. Eg:

  • 3919 → change trailing 9 to 0, add one to 1, result 3920
  • 3920 → no nines at end, add one to 0, result 3921
  • ...
  • 3999 → change three trailing 9s to 0, add one to 3, result 4000
user_15662210

Here is an implementation of rici's solution (counting). (Output is in the form of a 2D slice, each slice a combination.)

To produce your example output, getCombinations(3, 2).

func getCombinations(base, length int) [][]int {
    // list of combinations always includes the zero slice
    combinations := [][]int{make([]int, length)}
    current := make([]int, length)
    for {
        incrementIndex := length - 1
        // zero trailing <base - 1>'s
        for current[incrementIndex] == base-1 {
            current[incrementIndex] = 0
            incrementIndex--
            // stop when the next digit to be incremented is "larger"
            // than the specified (slice) length
            if incrementIndex < 0 {
                return combinations
            }
        }
        // increment the least significant non-<base - 1> digit
        current[incrementIndex]++
        // copy current into list of all combinations
        combinations = append(combinations, append([]int{}, current...))
    }
}
user_62178900

Try this code !

Code :

n = int(input("Enter value of n :"))
result=[]
for num1 in range(0,n+1):
    for num2 in range(0,n+1):
        result.append(str(num1)+str(num2))
print(result)

Output :

Enter value of n :3                                                                                                    
['00', '01', '02', '03', '10', '11', '12', '13', '20', '21', '22', '23', '30', '31', '32', '33']
user_91801790
Related