与替代 Java 的组合

Question

在过去的几天里，我试图解决这个在 java 中与替换组合的问题。我也检查了其他语言，也许它是用它们完成的，我可以翻译成 java 但没有运气，所以非常感谢任何帮助。

所以这是我遇到的问题（模拟面试问题）：

组合范围 0 - 6(n) 在大小为 r 的数组中（假设为 3）

所以替换组合的公式是C(n,r)=(n+r−1)！/ r!(n−1)!。在这种情况下，组合将是 84

000

010,

011,

...,

025,

055,

...,

666.

但是，我无法理解这个带有替换的算法，这与没有替换的情况完全不同。

再次感谢您的帮助。

Answer 1

private static List<int[]> samples(int n, int k) {&nbsp; &nbsp; if (k < 0 || n < 0) throw new IllegalArgumentException();&nbsp; &nbsp; if (k == 0) return Collections.emptyList();&nbsp; &nbsp; List<Integer> set = new ArrayList<>();&nbsp; &nbsp; for (int i = 0; i < n; i++) set.add(i);&nbsp; &nbsp; if (k == 1) return set.stream().map(i -> new int[]{i}).collect(Collectors.toList());&nbsp; &nbsp; List<int[]> previous = samples(n, k - 1);&nbsp; &nbsp; List<int[]> out = new ArrayList<>();&nbsp; &nbsp; for (int i : set) for (int[] array : previous) out.add(glue(i, array));&nbsp; &nbsp; return out;}private static int[] glue(int i, int[] array) {&nbsp; &nbsp; int[] out = new int[array.length + 1];&nbsp; &nbsp; out[0] = i;&nbsp; &nbsp; System.arraycopy(array, 0, out, 1, array.length);&nbsp; &nbsp; return out;}例如，for (int[] sample : samples(2, 3)) {&nbsp; &nbsp; System.out.println(Arrays.toString(sample));}产量[0, 0, 0][0, 0, 1][0, 1, 0][0, 1, 1][1, 0, 0][1, 0, 1][1, 1, 0][1, 1, 1]和for (int[] sample : samples(4, 2)) {&nbsp; &nbsp; System.out.println(Arrays.toString(sample));}产量[0, 0][0, 1][0, 2][0, 3][1, 0][1, 1][1, 2][1, 3][2, 0][2, 1][2, 2][2, 3][3, 0][3, 1][3, 2][3, 3]

Answer 2

检索到答案的第一个版本：您可以nn=(n+1)在每个r位置使用数字的变体，因此组合的总数为P = nn^r. 请注意，每个组合都对应于 range 中的数字0..P-1。因此，您可以遍历范围内的所有整数值0..P-1并表示 nn-ary 系统中的循环计数器。Java代码public static void main (String[] args) throws java.lang.Exception{&nbsp; &nbsp; int n = 2;&nbsp; &nbsp; int r = 3;&nbsp; &nbsp; int nn = n + 1;&nbsp; &nbsp; int p = 1;&nbsp; &nbsp; for (int i=0; i<r; i++)&nbsp; &nbsp; &nbsp; p *= nn;&nbsp; &nbsp; for (int i=0; i<p; i++){&nbsp; &nbsp; &nbsp; &nbsp; int t = i;&nbsp; &nbsp; &nbsp; &nbsp; String comb = "(";&nbsp; &nbsp; &nbsp; &nbsp; for (int j=0; j<r; j++){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; comb = comb + String.format("%2d, ", t % nn);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; t = t / nn;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; comb = comb.substring(0, comb.length()-2) + ')';&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(comb);&nbsp; &nbsp; }}蟒蛇代码：n = 2r = 3nn = n + 1p = nn**rfor V in range(p):&nbsp; &nbsp; t = V&nbsp; &nbsp; comb = []&nbsp; &nbsp; for i in range(r):&nbsp; &nbsp; &nbsp; &nbsp; d = t % nn&nbsp; &nbsp; &nbsp; &nbsp; comb.append(d)&nbsp; &nbsp; &nbsp; &nbsp; t = t // nn&nbsp; &nbsp; print(comb)[0, 0, 0][1, 0, 0][2, 0, 0][0, 1, 0][1, 1, 0][2, 1, 0][0, 2, 0][1, 2, 0][2, 2, 0][0, 0, 1][1, 0, 1][2, 0, 1][0, 1, 1][1, 1, 1][2, 1, 1][0, 2, 1][1, 2, 1][2, 2, 1][0, 0, 2][1, 0, 2][2, 0, 2][0, 1, 2][1, 1, 2][2, 1, 2][0, 2, 2][1, 2, 2][2, 2, 2]第二个版本：用于替换组合。Python 中的递归（最简单的方式）生成。def cwrreq(maxlen, maxx, s):&nbsp; &nbsp; if len(s)== maxlen:&nbsp; &nbsp; &nbsp; &nbsp; print(s)&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; for i in range(maxx + 1):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; cwrreq(maxlen, i, s + str(i))def combwithrepl(maxlen, maxval):&nbsp; &nbsp; cwrreq(maxlen, maxval, "")combwithrepl(3, 6)生成 84 种组合000100110111200...663664665666(3,3) 的完整列表。含义：有三个无法区分的盒子和三种颜料（比如红、绿、蓝）。000&nbsp; &nbsp; all boxes are hollow100&nbsp; &nbsp; one box is red110111&nbsp; &nbsp; all boxes are red200210&nbsp; &nbsp; one box is green,&nbsp; another is red211220221222300310311320321&nbsp; &nbsp;all boxes have distinct colors322330331332333&nbsp; &nbsp;all boxes are blue