Сформировать все возможные комбинации - Java [дублировать]

Обновить

November 2018

Просмотры

4.9k раз

8

Этот вопрос уже есть ответ здесь:

У меня есть список элементов {а, б, в, г} и мне нужно генерировать все возможные комбинации, когда,

  • Вы можете выбрать любое количество элементов
  • порядок не важен (АВ = ВА)
  • пустое множество не считается

Если мы возьмем возможности, должно быть,

n=4, number of items
total #of combinations = 4C4 + 4C3 + 4C2 + 4C1 = 15

Я использовал следующий рекурсивный метод:

private void countAllCombinations (String input,int idx, String[] options) {
    for(int i = idx ; i < options.length; i++) {
        String output = input + "_" + options[i];
        System.out.println(output);
        countAllCombinations(output,++idx, options);
    }
}

public static void main(String[] args) {
    String arr[] = {"A","B","C","D"};
    for (int i=0;i<arr.length;i++) {
        countAllCombinations(arr[i], i, arr);
    }
}

Есть ли более эффективный способ сделать это, когда размер массива велик?

1 ответы

9

Рассмотрим комбинацию, как двоичная последовательность, если все 4 присутствуют, мы получаем 1111, если первый алфавит отсутствует, то мы получим 0111, и так on.So для русского алфавитов мы будем иметь 2 ^ п -1 (с 0 не входит) комбинаций.

Теперь в вашей двоичной последовательности производится, если код 1, то элемент присутствует в противном случае он не included.Below является реализация одного и того же: -

 String arr[] = { "A", "B", "C", "D" };
    int n = arr.length;
    int N = (int) Math.pow(2d, Double.valueOf(n));  
    for (int i = 1; i < N; i++) {
        String code = Integer.toBinaryString(N | i).substring(1);
        for (int j = 0; j < n; j++) {
            if (code.charAt(j) == '1') {
                System.out.print(arr[j]);
            }
        }
        System.out.println();
    }