Комбинации с заменой Java - PullRequest
       7

Комбинации с заменой Java

0 голосов
/ 04 октября 2018

В последние пару дней я пытаюсь решить эту проблему комбинаций с заменой в Java.Я также проверил другие языки, возможно, это было сделано на них, и я мог бы перевести на java, но безуспешно, поэтому любая помощь очень ценится.1003 *

Объединение из диапазона 0 - 6 (n) В массиве размером r (скажем, 3)

Таким образом, формула для комбинаций с заменой: C (n, r) = (n + r-1)!/ r! (n − 1) !.В этом случае комбинации будут 84

000
010,
011,
...,
025,
055,
...,
666.

Однако я не могу обойтись без этого алгоритма С ЗАМЕНОЙ, который представляет собой совершенно другую историю без замены.

Еще раз спасибозаранее за вашу помощь.

Ответы [ 2 ]

0 голосов
/ 24 июня 2019
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]
0 голосов
/ 04 октября 2018

Получена первая версия ответа:

Вы можете использовать nn=(n+1) варианты цифр в каждом из r мест, поэтому общее количество комбинаций составляет P = nn^r.Обратите внимание, что каждая комбинация соответствует числу в диапазоне 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);
    }
}

Python-код:

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
...