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

Question

我注意到很多的回溯问题有解决的方法有两种。

一个是返回“无论是必需的名单”，VS，贯穿每个呼叫的“结果”，并追加到它。 返回的缺点是什么？（它是更少的内存/时间效率）？ 示例：要打印所有可能的排列，与第二个排序相比，这种解决方案的效率如何？ 对不起，如果这不是合适的论坛问这个问题，我找不到更好的地方。

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

这两种解决方案是无效的，因为他们使用递归（这是一个巨大的记忆猪），我建议你的第一个解决方案转换为迭代一个不依赖在堆栈上（也是一个内存问题，但不会引起堆栈溢出），例如这一个：https://stackoverflow.com/a/11471673/5991334

Answer 2

我认为最好通过讨论涉及的内存使用情况来开始讨论这些实现。正元件序列的排列的数量为n！和因为每一个都有一个长度为n，的空间来简单地存储所有的结果所需要的量将是为O（n＆middot;！n），其是一个相当壮观的记忆量。在n = 14的情况下，你处于危险的结果列表中，因为你的结果列表太大，以至于Java数组的32位索引不足以保存结果。

我提到这一点，因为当你在这里谈论效率时，你有很类似的方法，只有在你使用outparameter还是你返回值时有所不同 - 通常意味着该表现绝对至关重要，或者您认为这是某处的瓶颈。如果是这样的话，可能需要退后一步，并考虑真正的瓶颈是这个细节的效率，还是在内存中生成和保存一个怪物列表的效率。

例如，你在寻找一个排列有一定的财产 - 说，尽在其中满足特定的期限有些任务的顺序？或者，你是否正在寻找一种最小化一些数量的排列？在任何一种情况下，您都不需要执行生成所有可能排列的两遍系统，然后对每个排列进行测试。在第一种情况下，您可以使用递归回溯方式，每次只存储一个排列，在每个点上查看它是否有您想要的属性，并在您找到属性时立即停止。在第二个中，您可以一次生成一个排列，仅存储您在每个点找到的最佳排列。这两种方法都大大降低了内存需求，我怀疑内存压力的降低会显着提高性能。

另外，如果你真的是这样，那么很可能你的n是足够小，因为没有那么多的工作要做展位方法不会花费太长的时间来完成，简单。在这种情况下，你可能只想说“没关系”，因为你的瓶颈将会在别处。也许这是一个瓶颈，因为你碰到这样的N = 10，或者是因为这是一个紧密循环和低效确实成为一个问题，但同样，在这些情况下，你在做什么可能是一个更大的画面回顾为了。

如果您已经承诺将所有的排列存储在内存中 - 并且您已经决定要递归生成它们，而不是使用像C++的next_permutation这样的迭代算法，该算法使用更少的内存并且可能快得多 - 那么你可以做更多的事情来获得效率，而不是决定是返回结果还是使用outparameter。

请注意，例如，在您编写的第一个函数中，您将元素预先添加到一堆ArrayList中。 ArrayLists没有针对这种情况进行优化 - 与开始时相比，添加到ArrayList的末尾要快得多 - 并且单独进行更改可能会使您获得更大的性能提升，而不是从返回值切换到传出参数。

但是，让我们假设您完全决定了解问题的核心，并决定使用outparameters还是返回值，并且您已经确定这可能是一个重要的效率来源，并且您绝对必须将所有结果存储在内存中。

这归结为分配的数量以及JVM执行分配和垃圾回收的速度。

在这两种方法中，你将会以n列表结束！排列。存储这些列表所需的内存在两种情况下都是相同的，您无法避免。

在使用outparameter的情况下，您将有一个最终列表，其中将存储结果以及一个辅助列表，其中存储小的临时部分列表。你正在做的唯一的分配是建立最终被添加到结果中的列表。这与即将获得的最小分配数量差不多。

返回结果列表的函数将生成大量较小的中间列表，其中包含较小列表的排列。一旦上面的递归调用完成使用它们，那些列表就不需要了，因此在基线之上有很多分配。

但是，JVM通常非常擅长分配和回收“年轻化”的对象，并且典型的代代收集器通常针对这种情况进行优化。因此，这实际上可能不是什么大问题 - 你必须分析事情以找出答案。

总结：

• 之前，你甚至开始问这个问题，请检查您是否甚至需要。真的有必要在内存中列出所有的排列吗？如果你这样做，在你的程序中这样做的瓶颈是否真的是瓶颈，还是有更大的鱼要炒？在查看这些细节之前，您还会对这些功能进行其他优化或改进吗？

• 代码的参数外部版本可以减少不必要的分配，因此可能比第二个版本快一点。但是，JVM针对短物体寿命进行了优化，因此第二种方法可能不会太慢​​。