在Java中优化排列代码

8 浏览
0 Comments

在Java中优化排列代码

这是我从互联网上获取的代码。

import java.util.ArrayList;
import java.util.Calendar;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Test {
    public static void main(String args[]) {
        Test obj = new Test();
        Collection input = new ArrayList();
        for (int i = 0; i < 14; i++) {
                       input.add(i);
        }
        Collection> output = obj.permute(input);
        int k = 0;
        Set> pnr = null;
        for (int i = 0; i <= input.size(); i++)
        {
            pnr = new HashSet>();
            for(List integers : output){
            pnr.add(integers.subList(i, integers.size()));
            }
            k = input.size()- i;
            System.out.println("P("+input.size()+","+k+") :"+ 
            "Count ("+pnr.size()+") :- "+pnr);
        }
    }
    public Collection> permute(Collection input) {
        Collection> output = new ArrayList>();
        if (input.isEmpty()) {
            output.add(new ArrayList());
            return output;
        }
        List list = new ArrayList(input);
        T head = list.get(0);
        List rest = list.subList(1, list.size());
        for (List permutations : permute(rest)) {
            List> subLists = new ArrayList>();
            for (int i = 0; i <= permutations.size(); i++) {
                List subList = new ArrayList();
                subList.addAll(permutations);
                subList.add(i, head);
                subLists.add(subList);
            }
            output.addAll(subLists);
        }
        return output;
    }
}

当我尝试执行它时，对于计数为7的元素，花费了很长时间。但是当我尝试14时，我得到了以下异常。

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at java.util.Arrays.copyOf(Arrays.java:2219)
    at java.util.ArrayList.toArray(ArrayList.java:329)
    at java.util.ArrayList.addAll(ArrayList.java:530)
    at Test.permute(Test.java:45)
    at Test.permute(Test.java:41)
    at Test.permute(Test.java:41)
    at Test.permute(Test.java:41)
    at Test.main(Test.java:18)
Java Result: 1

我的系统配置是第三代i5，8GB RAM。当程序运行时，CPU消耗为98-100%。

所以我的问题是：

  • 是否有可用的jar包可以有效地进行排列组合？
  • 在这个代码中我可以做什么来提高性能？

我的需求：

  • 需要对一组（即超过30个）整数进行排列组合。

给出负评的人请注明原因。

0

3 答案

0 Comments

问题：Optimized Permutation Code in Java的出现原因是内存不足，需要处理的元素过多。

解决方法：增加堆大小或者优化算法。

文章：

在处理大规模元素的排列组合时，常常会遇到内存不足的问题。如果想要得到30个元素的所有排列组合，需要的内存大小将达到3e+22 TB，这是一个极其庞大的数字。面对如此巨大的内存需求，我们需要寻找解决方法。

一种解决方法是增加堆大小。在Eclipse中，我们可以通过调整堆大小来解决内存不足的问题。另外，我们也可以通过命令行来增加堆大小。这样做可以为程序提供更多的内存，从而解决内存不足的问题。

然而，仅仅增加堆大小并不能完全解决问题。如果我们要处理的元素数量非常庞大，那么即使增加了堆大小，程序仍然会遇到内存不足的问题。例如，如果要处理30个元素的所有排列组合，所需的内存大小将达到3e+22 TB，这是一个难以想象的数字。在这种情况下，我们需要通过优化算法来解决内存不足的问题。

以上是关于Optimized Permutation Code in Java问题出现原因和解决方法的介绍。通过增加堆大小或者优化算法，我们可以有效地解决内存不足的问题，使得程序能够正常运行并处理大规模的排列组合操作。

0
0 Comments

问题的出现原因是需要找到一种更高效或者优化的方法来找到一组数字的所有排列。然而，对于30个整数的可能排列数，其位数大约为32位。而一GB的内存对应的字节数只有10位。即使你拥有全世界所有的内存，也无法将所有的答案同时存储在内存中。

为了解决这个问题，需要采取Peter提出的方法，即虽然无法存储超过30个数字的整个解决方案（更不用说计算所需的时间了），但是可以计算部分答案，并在需要时生成更多的答案。

根据这一点，可以优化排列代码，使其能够在需要时动态生成排列，而不是一次性生成所有排列。这样可以节省大量的内存空间，并且可以在需要时快速生成所需的排列。

下面是一个Java的优化排列代码示例：

public class Permutation {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        permute(nums, 0);
    }
    private static void permute(int[] nums, int start) {
        if (start == nums.length - 1) {
            System.out.println(Arrays.toString(nums));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            permute(nums, start + 1);
            swap(nums, start, i);
        }
    }
    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

这段代码使用递归的方式生成排列。它通过交换数组中的元素来生成不同的排列。每次递归时，都会将当前位置与后面的位置进行交换，并继续递归生成下一个位置的排列。当递归到最后一个位置时，即生成了一个完整的排列。这样，通过控制递归的起始位置，可以在需要时动态生成排列。

通过这种优化方法，可以避免将所有排列存储在内存中，而是根据需要生成排列。这样不仅节省了内存空间，还能够快速生成所需的排列。

0
0 Comments

优化的排列代码在Java中的出现原因是为了解决生成所有排列的问题所需的内存占用过大的问题。为了解决这个问题，建议在生成排列时立即处理每个排列，这意味着您只需要一次存储一个组合。您可以生成所有大小为1（如果允许则为零）的排列，并逐渐增长到所有大小的所有排列。请注意：对于输出，您只需要计算您将生成的数量，而不必实际生成它们。是否有可用于高效排列的JAR库呢？可能有，但考虑到这只是一个练习，我怀疑通过自己完成它可以学到更多。这只是几行代码而已。

0