Блог

Мое замешательство связано со следующим вопросом программирования:

Учитывая массив размером n, сгенерируйте и выведите все возможные комбинации элементов r в массиве.

Одна из программ решения этого вопроса выглядит следующим образом:

  /* arr[]  ---> Input Array 
    data[] ---> Temporary array to store current combination 
    start amp; end ---> Staring and Ending indexes in arr[] 
    index  ---> Current index in data[] 
    r ---> Size of a combination to be printed */
    static void combinationUtil(int arr[], int data[], int start, 
                                int end, int index, int r) 
    { 
        // Current combination is ready to be printed, print it 
        if (index == r) 
        { 
            for (int j=0; j<r; j  ) 
                System.out.print(data[j] " "); 
            System.out.println(""); 
            return; 
        } 
  
        // replace index with all possible elements. The condition 
        // "end-i 1 >= r-index" makes sure that including one element 
        // at index will make a combination with remaining elements 
        // at remaining positions 
        for (int i=start; i<=end amp;amp; end-i 1 >= r-index; i  ) 
        { 
            data[index] = arr[i]; 
            combinationUtil(arr, data, i 1, end, index 1, r); 
        } 
    } 
  
    // The main function that prints all combinations of size r 
    // in arr[] of size n. This function mainly uses combinationUtil() 
    static void printCombination(int arr[], int n, int r) 
    { 
        // A temporary array to store all combination one by one 
        int data[]=new int[r]; 
  
        // Print all combination using temprary array 'data[]' 
        combinationUtil(arr, data, 0, n-1, 0, r); 
    } 
 

Полный код можно найти здесь .

Меня смущает условие end-i 1 >= r-index в функции combinationUtil , и я изо всех сил пытаюсь понять его предыдущий комментарий:

     // replace index with all possible elements. The condition 
    // "end-i 1 >= r-index" makes sure that including one element 
    // at index will make a combination with remaining elements 
    // at remaining positions 
    for (int i=start; i<=end amp;amp; end-i 1 >= r-index; i  ) 
            { 
                data[index] = arr[i]; 
                combinationUtil(arr, data, i 1, end, index 1, r); 
            } 
 

Я предполагаю, что выражение r-index предназначено для проверки того, сколько позиций из r уже заполнено (когда index равно 0, r позиции все еще ожидают заполнения, а когда index равно 1, r-1 из них и так далее).
Я не могу понять, что end-i 1 происходит.Ранее я думал, что оно предназначено для обозначения того, как далеко программа находится во входном массиве через счетчик / переменную i . Другими словами, он хочет указать, сколько еще элементов во входном массиве все еще остается в используемом массиве. Однако эта идея больше не имеет для меня смысла.

Пожалуйста, объясните, что end-i 1 >= r-index означает в контексте этой проблемы.

РЕДАКТИРОВАТЬ 1:

Я все еще нахожу использование переменных запутанным. r это общее количество элементов и index соответствует индексам массива, поэтому оно будет не более чем на 1 меньше общего числа. Кажется странным вычитать их друг из друга.

РЕДАКТИРОВАТЬ 2:

Разве выражение end-i >= r-(index 1) не имеет больше смысла? Пожалуйста, дайте мне знать ваши мысли по этому поводу.

Это лишь небольшая оптимизация кода. i циклы от start до end . В следующей рекурсии start последняя i 1 из последней рекурсии. Таким образом, элементы добавляются data в их первоначальном порядке.

end - i указывает, сколько элементов все еще можно использовать после текущего элемента i . end - i 1 сколько элементов можно использовать, если включен текущий элемент.

r - index - 1 указывает, сколько элементов все еще должно использоваться (потому index что начинается с нуля). Если цикл зашел так далеко, что data не может быть заполнен, нет смысла идти вперед. Таким образом, эта оптимизация прерывает цикл и выполняет обратные пути.

Теперь это можно проверить с end - i 1 <= r - index - 1 помощью или end - i 1 < r - index . Другими словами end - i 1 < r - index , верно, что возможных комбинаций нет. Поэтому, когда его отрицание равно true, цикл не должен прерываться end - i 1 >= r - index .

Редактировать:

Я думаю end - i 1 >= r - index , это более понятно, чем end - i >= r - (index 1) . В приведенном выше есть условие r == index , поэтому имеет смысл использовать r - index его и ниже.

end - i 1 похоже на «сколько элементов можно использовать» и r - index похоже на «сколько элементов нужно использовать». Если у нас достаточно элементов, мы можем продолжить.

В end - i >= r - (index 1) нем «сколько элементов может быть использовано после этого» и «сколько элементов должно быть использовано после этого». Я лично считаю, что это сложнее. Это похоже на пропуск текущего шага. Я понимаю, почему было бы предпочтительнее r - (index 1) , чтобы значение because index увеличивалось на единицу перед сравнением с r .

Оба утверждения верны и имеют одинаковый результат. Какой из них вы предпочитаете, зависит от вашего стиля кодирования. Самое главное, что вы можете создать подобное утверждение, когда вам нужно.