java - 两种打印所有排列的方法-返回与通过“结果”列表

Question

我注意到许多回溯问题有两种解决方法。
一种是返回“所需列表的任何内容”，而不是传递每个调用的“结果”并将其追加。
回归有什么坏处？（内存/时间效率低吗？
示例：要打印所有可能的排列，是什么使此解决方案与第二个解决方案相比效率低下？
抱歉，如果这不是问这个问题的合适论坛，我找不到更好的地方。

public List<List<Integer>> perm(int[] nums){
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if(nums.length == 0){
        result.add(new ArrayList<Integer>());
        return result;        
    }
    for(int i= 0;i<nums.length;i++){
        int first = nums[i];
        int[] remnums = new int[nums.length-1];
        int j = 0;
        for(int cur : nums){
            if(cur != first){
                remnums[j] = cur;j++;
            }
        }
        List<List<Integer>> tmp = perm(remnums);

        for(List<Integer> t : tmp){
            t.add(0,first);

        }
        result.addAll(tmp);
    }
    return result;
}

第二次进近---

  public List<List<Integer>> permute(int[] nums) {
   List<List<Integer>> list = new ArrayList<>();
   // Arrays.sort(nums); // not necessary
   backtrack(list, new ArrayList<>(), nums);
   return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
   if(tempList.size() == nums.length){
      list.add(new ArrayList<>(tempList));
   } else{
      for(int i = 0; i < nums.length; i++){ 
         if(tempList.contains(nums[i])) continue; // element already exists, skip
         tempList.add(nums[i]);
         backtrack(list, tempList, nums);
         tempList.remove(tempList.size() - 1);
      }
   }
} 

Answer 1

我认为最好从讨论这些实现的内存使用情况开始。一个n元序列的置换数是n！，因为每个结果的长度都是n，所以简单地存储所有结果所需的空间量将是O（n·n！），这是相当惊人的记忆量。当n=14时，您所处的领域可能会导致结果列表太大，以至于Java数组的32位索引不够大，无法保存结果。
我之所以提到这一点，是因为当你在这里谈论效率的时候——你有非常相似的方法，这些方法只在你是使用一个输出参数还是返回值上有所不同——这通常意味着性能是绝对关键的，或者你已经将其确定为某个地方的瓶颈如果真是这样的话，或许值得退一步暂停一下，考虑一下真正的瓶颈是这个细节的效率，还是生成并保存一个怪物列表的效率。
例如，您是否正在搜索具有特定属性的排列，例如，执行某些任务的顺序是否满足特定的截止日期或者，你是在寻找一个最小数量的排列吗？在任何一种情况下，你都不需要做一个生成所有可能的排列然后测试每一个排列的两遍系统在第一种情况下，可以使用递归回溯，每次只存储一个置换，在每个点查看它是否具有所需的属性，并在找到属性后立即停止在第二种情况下，可以一次生成一个置换，只存储在每个点上找到的最佳置换。这两种方法都显著降低了内存需求，我怀疑降低的内存压力将显著提高性能。
另外，如果你真的这样做了，你的n足够小，booth方法不会花太长时间来完成，因为没有太多的工作要做。在这种情况下，你可能只想说“没关系”，因为你的瓶颈将在别处。也许这是一个瓶颈，因为你有类似于n=10的东西，或者因为这是一个紧密的循环，效率低下确实成为了一个问题，但是，在这些情况下，对你正在做的事情的一个更大的回顾可能是有序的。
如果您已经承诺将所有排列存储在内存中，并且您已经决定要递归地生成这些排列，而不是使用像C++的next_permutation之类的迭代算法，它使用更少的内存，并且可能要快得多。那么，为了获得效率胜过，还可以做更大的事情，而不是决定是否返回。结果或使用输出参数。
注意，例如，在您编写的第一个函数中，您将元素前置到一堆arraylistarraylist s并没有针对这种情况进行优化—附加到arraylist的末尾要比附加到arraylist的开头快得多—单是这种更改可能会比从返回值切换到传递输出参数带来更大的性能提升。
但是假设你下定决心要抓住问题的核心，在使用outparameters和返回值之间做出决定，而且你已经确定这可能是一个重要的效率来源，而且你绝对必须将所有结果存储在内存中。
这可以归结为分配的数量以及JVM进行分配和垃圾收集的速度。
在这两种方法中，您将得到一个n的列表！排列在这两种情况下，存储这些列表所需的内存是相同的，您无法避免。
在使用OutOutlook的情况下，将有一个最终结果列表，其中存储一个辅助列表，其中存储一个小的、临时的部分列表。您所做的唯一分配是构建最终添加到结果中的列表这几乎是您将获得的最小分配数。
返回结果列表的函数将生成大量较小的中间列表，其中包含较小列表的排列。一旦上面的递归调用完成使用，就不需要这些列表，因此在基线之上进行了许多分配。
然而，jvm通常非常擅长分配和回收“夭折”的对象，并且代收集器通常针对这种情况进行了优化。因此，这实际上可能并不是一个大问题——你需要对事情进行分析才能找到答案。
总结一下：
在你开始问这个问题之前，检查一下你是否需要有必要在内存中保存所有排列的列表吗？如果你这样做了，那么这样做的成本真的是你程序中的一个瓶颈，还是有更大的问题要解决？在查看这些细节之前，您是否对这些函数进行了其他优化或改进？
代码的outparameter版本减少了不必要的分配，因此可能比第二个版本快一些。然而，jvm是为短对象生命周期而优化的，因此第二种方法可能不会慢很多。