与替代 Java 的组合

Question

在过去的几天里，我试图解决这个在 java 中与替换组合的问题。我也检查了其他语言，也许它是用它们完成的，我可以翻译成 java 但没有运气，所以非常感谢任何帮助。所以这是我遇到的问题（模拟面试问题）：组合范围 0 - 6(n) 在大小为 r 的数组中（假设为 3）所以替换组合的公式是C(n,r)=(n+r−1)！/ r!(n−1)!。在这种情况下，组合将是 84000010,011,...,025,055,...,666.但是，我无法理解这个带有替换的算法，这与没有替换的情况完全不同。再次感谢您的帮助。

Answer 1

private static List<int[]> samples(int n, int k) {

    if (k < 0 || n < 0) throw new IllegalArgumentException();

    if (k == 0) return Collections.emptyList();

    List<Integer> set = new ArrayList<>();

    for (int i = 0; i < n; i++) set.add(i);

    if (k == 1) return set.stream().map(i -> new int[]{i}).collect(Collectors.toList());

    List<int[]> previous = samples(n, k - 1);

    List<int[]> out = new ArrayList<>();

    for (int i : set) for (int[] array : previous) out.add(glue(i, array));

    return out;

}

private static int[] glue(int i, int[] array) {

    int[] out = new int[array.length + 1];

    out[0] = i;

    System.arraycopy(array, 0, out, 1, array.length);

    return out;

}

例如，

for (int[] sample : samples(2, 3)) {

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

    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

{

    int n = 2;

    int r = 3;

    int nn = n + 1;

    int p = 1;

    for (int i=0; i<r; i++)

      p *= nn;

    for (int i=0; i<p; i++){

        int t = i;

        String comb = "(";

        for (int j=0; j<r; j++){

            comb = comb + String.format("%2d, ", t % nn);

            t = t / nn;

        }

        comb = comb.substring(0, comb.length()-2) + ')';

        System.out.println(comb);

    }

}

蟒蛇代码：

n = 2

r = 3

nn = n + 1

p = nn**r

for V in range(p):

    t = V

    comb = []

    for i in range(r):

        d = t % nn

        comb.append(d)

        t = t // nn

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

    if len(s)== maxlen:

        print(s)

    else:

        for i in range(maxx + 1):

            cwrreq(maxlen, i, s + str(i))

def combwithrepl(maxlen, maxval):

    cwrreq(maxlen, maxval, "")

combwithrepl(3, 6)

生成 84 种组合

000

100

110

111

200

...

663

664

665

666

(3,3) 的完整列表。含义：有三个无法区分的盒子和三种颜料（比如红、绿、蓝）。

000    all boxes are hollow

100    one box is red

110

111    all boxes are red

200

210    one box is green,  another is red

211

220

221

222

300

310

311

320

321   all boxes have distinct colors

322

330

331

332

333   all boxes are blue