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

问题描述 投票：1回答：2

我对此非常困惑。代码是生成给定整数列表的所有排列。一旦你这样做，他们添加另一个约束，即给定的输入可以有重复，我们只想要唯一的排列。

我的代码有效......我对我注意到的事情感到惊讶。在查看代码之后，我质疑我的具体条件是否必要，所以我否定了它会看到会发生什么。该代码在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);
    }
  }
}

我的问题是这怎么可能？代码工作如果是真或假，但完全删除它不起作用。

java algorithm permutation
2个回答
2
投票

我可以确认您的代码产生相同的结果，有或没有否定条件的最后部分，并且当条件被移除时它会产生不同的结果。

这可能看起来像一个奇迹，除非你认为整个条件在一个循环中被多次评估，并且很可能是三个案例（有条件，有条件，无条件）都有不同的处理方式和来结果。我想说的是，条件和否定条件会达到相同的结果，但方式不同。

这就是这种情况。如果在循环中引入一些printf-debugging，您将看到以完全不同的方式达到结果。具有否定的现有条件使得完整条件在除了没有否定的条件之外的其他迭代中变为真。纯粹的机会（没有进一步研究算法）最终都会导致相同的结果。

这是数字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]]

在所有三种情况下，执行步骤都不同。两个（偶然）具有相同的结果。

0
投票

当你删除看到的[i-1]或！see [i -1]时，对于2个或更多int数组值匹配和实现的输入类型

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

if条件变为TRUE并迭代int数组，而不添加。

并且按顺序调用“permutation.add”和“permutation.remove”，对于导致空集的第一个/最后一个元素。尝试{1,1,2} OR {1,2,2} OR {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);
        }
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.