Распечатать все комбинации x объектов в y слотах (Java)

Question

Если у вас есть x объектов (могут быть представлены 1 с), которые должны быть размещены в y слотах (пустые слоты могут быть представлены в виде 0), напишите функцию, которая печатает все возможные способы размещения объектов в слоты. Метод будет принимать в качестве входных данных количество объектов и общее количество слотов.

Например, возможные комбинации (3, 5) должны печатать способы размещения 3 объектов в 5 слотах:

11100, 11010, 11001, 10110, 10101, 10011, 01110, 01101, 01011, 00111

Я рассмотрел рекурсию как вариант, но я не уверен, как ее настроить, чтобы она работала для любого количества объектов. Любая помощь будет принята с благодарностью!

Answer 1

Вот некоторый псевдокод, очевидно, я не использую очень хорошую структуру данных. Но вы можете видеть каждый вызов, если это возможно, проверяет случаи, когда каждый элемент либо включен, либо не включен, и продолжается оттуда. Это пара рекурсивных вызовов в операторе else.

func(a,b)
case 0,0
  return null;
case a>b
  return null;
else
  return {1,func(a-1,b-1)} & {0,func(a,b-1)};

Answer 2

вот некоторый код Java:

public static void possibilities(int k,int n) {
    aux(k,n,new StringBuilder());
}
public static void aux(int k,int n,StringBuilder sb) {
    if (n == 0 && k == 0) {
        System.out.println(sb);
        return;
    } else if (n<k) {
        return;
    }
    if (k>0) { 
        aux(k-1,n-1,new StringBuilder(sb).append(1));
    }
    aux(k,n-1,new StringBuilder(sb).append(0));
}

aux () фактически выполняет всю работу, он делает все возможности: добавляет 0 или добавляет 1 и печатает в конце только тех, кто «использовал» всевозможные 1-ые

РЕДАКТИРОВАТЬ: изменил условие окончания рекурсии, чтобы обрезать случаи, которые не будут напечатаны в конце.

Answer 3

Это напоминает мне, что вы можете искать Permutations[Join[Table[1, {3}],Table[0, {5-3}]]], на wolframalpha.com и получить правильный ответ.

Шаги в этом ответе:

• создать набор из 1: 111
• создать набор из 0: 00
• присоединиться к ним: 11100
• показать все перестановки:

Answer 4

Вот как бы я сделал 3, 5. Начните со строки 111. 5 - 3 = 2, поэтому добавляем 2 нуля. Есть четыре возможных местоположения для каждого нуля a1b1c1d. 4 ^ 2 означает 16 возможных местоположений, кодируя первое местоположение как 0 - 3, а второе как (0 - 3) * 4. Теперь перечислите 0 - 15 и распечатайте полученную комбинацию. В этой схеме первые 5 выходов:

00111, 01011, 01101, 01110, 01011

И у нас есть повтор. Этот механизм распечатывает перестановки, когда вы хотите комбинации. Вероятно, есть способ перечислить комбинацию, но самое простое решение - просто проиндексировать свои результаты и убедиться, что вы не возвращаете одно и то же дважды.