所有N个元素的k组合数

Question

我将尝试编写一个算法，返回长度为n时值为0、1和2的所有可能组合的数组。

例如当n = 2时：

00

01

02

10

11

12

20

21

22

我已经开始写的代码还远远不够正确或完整：

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)
}

非常感谢您的帮助！

- Zander17

---

请分享一些代码，并尽可能具体地描述您遇到的问题。 - oren

@oren 更新了原始帖子。算法需要根据数值向左或向右移动，以便最终得到正确的组合。我只是在想解决方案时遇到了困难。 - Zander17

需要非常高效吗？如果不需要，我认为最容易理解的方法是编写一个递归函数f(n)，该函数查看来自f(n-1)的数组，并针对数组中的每个字符串生成三个新字符串，分别通过在末尾添加0、1或2来实现，然后返回由所有这些新字符串组成的数组。当然，这也可以变成非递归的形式。 - Countingstuff

@countingstuff：我必须说，我发现那个评论很讽刺，因为答案就是简单地计数。 - rici

Answer 1

这只是在 k 进制下的计数。你可以这样做 —— 把连续的整数转换为 k 进制 —— 但是那需要大量的除和余数运算，所以你最好使用更简单的方法。

1. 从 n 个0开始，然后尽可能多地重复以下步骤： 2. 将所有末尾的 k-1 改为 0，然后将前一个元素加 1。如果没有前一个元素，则完成。

如果想理解，你可以选择用普通的十进制数 k=10 试一下。例如：

3919 → 把结尾的 9 改为 0，把前一个数加 1，结果 3920 3920 → 没有以 9 结尾的数，把前一个数加 1，结果 3921 ... 3999 → 把三个结尾的 9 改为 0，把前一个数加 1，结果 4000

- rici

Answer 2

这是 rici 的解决方案（计数）的实现。（输出以 2D 切片的形式呈现，每个切片都是一个组合。）

要生成您的示例输出，请使用 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...))
    }
}

- John LaRocque

Answer 3

试试这段代码！

代码：

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)

输出：

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

- Usman

---

我认为OP的本意并不是让“n”成为每个字符串中字符的数量，而“k”则是可能字符的范围。你的双重循环只允许n=2... - dWinder