java - 如果条件可以为真或为假，为什么有必要

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);
    }
  }
}

我的问题很简单，这怎么可能？如果是 true 或 false，代码可以工作，但完全删除它是行不通的。

Answer 1

我可以确认您的代码在否定或不否定条件的最后一部分的情况下产生相同的结果，并且在删除条件时产生不同的结果。

这看起来像是一个奇迹，除非你认为整个条件在一个循环中被评估了很多次，而且这三种情况(有条件、有否定条件、无条件)很可能都有不同的处理方式并得出结果。我想说的是，使用条件和否定条件可以达到相同的结果但方式不同。

这里是这样的。如果您在循环中引入一些 printf 调试，您将看到以完全不同的方式达到结果。具有否定的现有条件使完整条件在其他迭代中变为真，而不是没有否定的条件。最终两者会导致相同的结果纯属偶然(无需进一步查看算法)。

这里是第i个i的执行轨迹，完全条件的结果，还有nums的中间值，seen，和结果在这个地方:

没有条件:

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

三种情况下的执行步骤都不同。两个(偶然)有相同的结果。