Если условие может быть истинным или ложным, зачем это нужно?

Question

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

Мой код работает ... Я просто поражен тем, что заметил.Просмотрев код, я спросил, было ли мне необходимо определенное условие, поэтому я отменил его, чтобы посмотреть, что произойдет.Код все еще работал без ошибок на 100 тестовых примерах.По сути, этот код работает независимо от того, является ли это условие true или false.

Естественно, я подумал, что могу просто удалить условие, так как оно кажется ненужным.Короче говоря .... код теперь возвращает пустой набор результатов.Я надеюсь, что кто-нибудь умнее меня сможет объяснить, как это возможно, потому что я сейчас спрашиваю, принадлежу ли я этой профессии.

Строка кода, о которой идет речь:

if(seen[i] || (i > 0 && nums[i] == nums[i - 1] && !seen[i - 1]))

В частности !seen[i - 1] Если вы запустите этот код как есть, он будет работать.Если вы удалите отрицание и запустите его как seen[i - 1], он все равно будет работать.Если вы полностью удалите !seen[i - 1] так, чтобы условие выглядело так:

if(seen[i] || (i > 0 && nums[i] == nums[i - 1])), тогда код вернет пустой набор результатов.Я полностью сбит с толку.

Я использую [1,1,2] в качестве входных данных для метода, и мой ожидаемый набор результатов: [[1,1,2],[1,2,1],[2,1,1]]

class PermutationGenerator {
  List<List<Integer>> result = new ArrayList<>();

  public List<List<Integer>> permuteUnique(int[] nums) {
    if(nums == null || nums.length == 0){
        return result;
    }
    Arrays.sort(nums);
    backtrack(nums, new ArrayList<>(), new boolean[100]);
    return result;
   }

  private void backtrack(int[] nums, List<Integer> permutation, boolean[] seen){
    if(permutation.size() == nums.length){
        result.add(new ArrayList<>(permutation));
        return;
    }

    for(int i = 0; i < nums.length; i++){
        if(seen[i] || (i > 0 && nums[i] == nums[i - 1] && !seen[i - 1])){
            continue;
        }
        seen[i] = true;
        permutation.add(nums[i]);
        backtrack(nums, permutation, seen);
        seen[i] = false;
        permutation.remove(permutation.size() - 1);
    }
  }
}

Мой вопрос просто какэто возможно?Код работает, если это правда или ложь, но полное его удаление не работает.

Answer 1

Я могу подтвердить, что ваш код выдает одинаковый результат с отрицательной последней частью условия или без нее, и что при удалении условия он дает разные результаты.

Это может показаться чудом, если вы не примете во вниманиечто все условие оценивается в цикле много раз, и вполне может быть, что все три случая (с условием, с отрицательным условием, без условия) имеют разные способы обработки и получения результата.Я пытаюсь сказать, что с условием и с отрицанным условием одни и те же результаты достигаются , но по-разному .

Так обстоит дело здесь.Если вы введете некоторую отладку printf в цикле, вы увидите, что результат достигается совершенно разными способами.Существующее условие с отрицанием позволяет выполнить полное условие на других итерациях, кроме условия без отрицания.Это чистый шанс (не смотря далее на алгоритм), что в итоге оба приводят к одному и тому же результату.

Вот трассировка выполнения числа i, результат выполнения условия и промежуточный результатзначения nums, seen и result в этом месте:

Без условия:

0 F [1, 1, 2] [0, 0, 0] []
0 T [1, 1, 2] [True, 0, 0] []
1 T [1, 1, 2] [True, 0, 0] []
2 F [1, 1, 2] [True, 0, 0] []
0 T [1, 1, 2] [True, 0, True] []
1 T [1, 1, 2] [True, 0, True] []
2 T [1, 1, 2] [True, 0, True] []
1 T [1, 1, 2] [False, 0, False] []
2 F [1, 1, 2] [False, 0, False] []
0 F [1, 1, 2] [False, 0, True] []
0 T [1, 1, 2] [True, 0, True] []
1 T [1, 1, 2] [True, 0, True] []
2 T [1, 1, 2] [True, 0, True] []
1 T [1, 1, 2] [False, 0, True] []
2 T [1, 1, 2] [False, 0, True] []

С условием seen[i-1]:

0 F [1, 1, 2] [0, 0, 0] []
0 T [1, 1, 2] [True, 0, 0] []
1 T [1, 1, 2] [True, 0, 0] []
2 F [1, 1, 2] [True, 0, 0] []
0 T [1, 1, 2] [True, 0, True] []
1 T [1, 1, 2] [True, 0, True] []
2 T [1, 1, 2] [True, 0, True] []
1 F [1, 1, 2] [False, 0, False] []
0 F [1, 1, 2] [False, True, False] []
0 T [1, 1, 2] [True, True, False] []
1 T [1, 1, 2] [True, True, False] []
2 F [1, 1, 2] [True, True, False] []
1 T [1, 1, 2] [False, True, False] [[1, 1, 2]]
2 F [1, 1, 2] [False, True, False] [[1, 1, 2]]
0 F [1, 1, 2] [False, True, True] [[1, 1, 2]]
1 T [1, 1, 2] [False, True, True] [[1, 1, 2], [1, 2, 1]]
2 T [1, 1, 2] [False, True, True] [[1, 1, 2], [1, 2, 1]]
2 F [1, 1, 2] [False, False, False] [[1, 1, 2], [1, 2, 1]]
0 F [1, 1, 2] [False, False, True] [[1, 1, 2], [1, 2, 1]]
0 T [1, 1, 2] [True, False, True] [[1, 1, 2], [1, 2, 1]]
1 T [1, 1, 2] [True, False, True] [[1, 1, 2], [1, 2, 1]]
2 T [1, 1, 2] [True, False, True] [[1, 1, 2], [1, 2, 1]]
1 F [1, 1, 2] [False, False, True] [[1, 1, 2], [1, 2, 1]]
0 F [1, 1, 2] [False, True, True] [[1, 1, 2], [1, 2, 1]]
1 T [1, 1, 2] [False, True, True] [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
2 T [1, 1, 2] [False, True, True] [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
2 T [1, 1, 2] [False, False, True] [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

И с отрицательным условием !seen[i-1]:

0 F [1, 1, 2] [0, 0, 0] []
0 T [1, 1, 2] [True, 0, 0] []
1 F [1, 1, 2] [True, 0, 0] []
0 T [1, 1, 2] [True, True, 0] []
1 T [1, 1, 2] [True, True, 0] []
2 F [1, 1, 2] [True, True, 0] []
2 F [1, 1, 2] [True, False, False] [[1, 1, 2]]
0 T [1, 1, 2] [True, False, True] [[1, 1, 2]]
1 F [1, 1, 2] [True, False, True] [[1, 1, 2]]
2 T [1, 1, 2] [True, False, True] [[1, 1, 2], [1, 2, 1]]
1 T [1, 1, 2] [False, False, False] [[1, 1, 2], [1, 2, 1]]
2 F [1, 1, 2] [False, False, False] [[1, 1, 2], [1, 2, 1]]
0 F [1, 1, 2] [False, False, True] [[1, 1, 2], [1, 2, 1]]
0 T [1, 1, 2] [True, False, True] [[1, 1, 2], [1, 2, 1]]
1 F [1, 1, 2] [True, False, True] [[1, 1, 2], [1, 2, 1]]
2 T [1, 1, 2] [True, False, True] [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
1 T [1, 1, 2] [False, False, True] [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
2 T [1, 1, 2] [False, False, True] [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

Шаги выполнения различны во всех трех случаях.Два (случайно) имеют одинаковый результат.

Answer 2

При удалении видимого [i-1] или! Seen [i -1], Для типов ввода, в которых 2 или более значений массива int совпадают и удовлетворяют

  nums[i] == nums[i - 1]

Ifусловие получает TRUE и выполняет итерацию по массиву int без добавления.

и "permutation.add" и "permutation.remove" вызываются последовательно, для первого / последнего элемента, приводящего к пустому набору.последовательность вызовов при попытке с {1,1,2} ИЛИ {1,2,2} ИЛИ {1,2,1}

Add called
Add called
Remove called
Remove called
Add called
Add called
Remove called
Remove called
[]

для {2,2,2}

Add called
Remove called
[]

Используемый код:

       for(int i = 0; i < nums.length; i++){
            //System.out.println(seen[i]);
            if(seen[i] || (i > 0 && nums[i] == nums[i - 1])){
                //System.out.println("Inside if");
                continue;
            }
            seen[i] = true;
            System.out.println("Add called");
            permutation.add(nums[i]);
            backtrack(nums, permutation, seen);
            seen[i] = false;
            System.out.println("Remove called");
            permutation.remove(permutation.size() - 1);
        }