logo标签列表

Java代码实现对一列数字的排列组合

javaalgorithmoptimizationpermutation
8
我已经编写了一个程序，用于查找给定项目列表的所有可能排列。这意味着我的程序会打印出 r=0 到 n 的所有可能 P(n,r) 值。
以下是代码： 
package com.algorithm;

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 Permutations<T> {
    public static void main(String args[]) {
        Permutations<Integer> obj = new Permutations<Integer>();
        Collection<Integer> input = new ArrayList<Integer>();
        input.add(1);
        input.add(2);
        input.add(3);

        Collection<List<Integer>> output = obj.permute(input);
        int k = 0;
        Set<List<Integer>> pnr = null;
        for (int i = 0; i <= input.size(); i++) {
            pnr = new HashSet<List<Integer>>();
            for(List<Integer> 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<List<T>> permute(Collection<T> input) {
        Collection<List<T>> output = new ArrayList<List<T>>();
        if (input.isEmpty()) {
            output.add(new ArrayList<T>());
            return output;
        }
        List<T> list = new ArrayList<T>(input);
        T head = list.get(0);
        List<T> rest = list.subList(1, list.size());
        for (List<T> permutations : permute(rest)) {
            List<List<T>> subLists = new ArrayList<List<T>>();
            for (int i = 0; i <= permutations.size(); i++) {
                List<T> subList = new ArrayList<T>();
                subList.addAll(permutations);
                subList.add(i, head);
                subLists.add(subList);
            }
            output.addAll(subLists);
        }
        return output;
    }
}

输出

P(3,3) : Count (6) :- [[1, 2, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2], [2, 1, 3], [1, 3, 2]]
P(3,2) : Count (6) :- [[3, 1], [2, 1], [3, 2], [1, 3], [2, 3], [1, 2]]
P(3,1) : Count (3) :- [[3], [1], [2]]
P(3,0) : Count (1) :- [[]]

我的问题是，当我增加输入列表中的数字时，运行时间会增加。在输入列表中有11个数字后，程序几乎无法运行。需要大约2GB内存才能运行。
我正在一台拥有8GB RAM和i5处理器的机器上运行此程序，因此速度和空间不是问题。
如果有人可以帮助我编写更高效的代码，我将不胜感激。
5
更适合在http://codereview.stackexchange.com/上进行代码审查。 - Anthony Grist
@Anthony 谢谢 :) 我是新手，不知道把什么放在哪里。 - dharam
4个回答
16
8
如果您想要15个或更多元素的所有排列，将它们写入磁盘或数据库等存储介质中，因为它们无法放入内存中。 编辑：斯坦豪斯-约翰逊-特罗特算法。 这可能是您正在寻找的。
我相信你说的是对的。问题不在于存储，而在于运行时间。对于大约13个数字的排列，它需要超过一分钟的时间。 - dharam
这个链接真的很棒。即使速度提升也可能会有所帮助。感谢指引。我会尝试并在这里发布的。 - dharam
7
2

您应该意识到您正在生成非常大的列表，而且随着列表长度的增加，运行时间会增加。您确定了哪些列表长度会给您带来麻烦吗？

有一件事可能会对您有所帮助，即在找到每个排列时将其打印出来，而不是将它们全部收集到一个列表中，然后再打印出来。当然，如果目的是实际存储整个列表，而不仅仅是打印它们，那么这种方法就无法帮助。

感谢回复。即使我打印出来，生成的10个数字的排列数量也是100000的数量级。假设我不存储它，即使在这种情况下，顺序也不会改变。此外，我的代码问题在于递归树是单侧的。如果我能找到一种算法，每次递归将输入分成两个相等的部分，然后找到较小列表的排列并在最后合并它们。只是想知道是否有人可以为我推荐一本高级算法书。 - dharam
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接