Java的code的号码列表的排列 [英] Java Code for permutations of a list of numbers

问题描述

我写了一个程序，找出项目的特定列表的所有可能的排列。这precisely意味着我的程序打印出所有可能的P（N，R）的R值= 0到n

下面是code：

 包com.algorithm;

进口的java.util.ArrayList;
进口的java.util.Calendar;
进口java.util.Collection的;
进口java.util.HashSet中;
进口的java.util.List;
进口java.util.Set中;

公共类置换＆LT; T＆GT; {
    公共静态无效的主要（字符串的args []）{
        置换＆LT;整数GT; OBJ =新的置换＆LT;整数GT;（）;
        收藏＆LT;整数GT;输入=新的ArrayList＆LT;整数GT;（）;
        input.add（1）;
        input.add（2）;
        input.add（3）;

        收藏＆LT;列表＆LT;整数GT;＆GT;输出= obj.permute（输入）;
        INT K = 0;
        设置＆LT;列表＆LT;整数GT;＆GT; PNR = NULL;
        的for（int i = 0; I＆LT; = input.size（）;我++）{
            PNR =新的HashSet＆LT;列表＆LT;整数GT;＆GT;（）;
            对于（名单＆LT;整数GT;的整数：输出）{
            pnr.add（integers.subList（ⅰ，integers.size（）））;
            }
            K = input.size（） - 我;
            的System.out.println（P（+ input.size（）+，+ K +）：+
            计数（+ pnr.size（）+）： - + PNR）;
        }
    }
    公文集＆LT;列表＆LT; T＆GT;＆GT;置换（集合＆LT; T＆GT;输入）{
        收藏＆LT;列表＆LT; T＆GT;＆GT;输出=新的ArrayList＆LT;列表＆LT; T＆GT;＆GT;（）;
        如果（input.isEmpty（））{
            output.add（新的ArrayList＆LT; T＆GT;（））;
            返回输出;
        }
        名单＆LT; T＆GT;名单=新的ArrayList＆LT; T＆GT;（输入）;
        牛逼头= list.get（0）;
        名单＆LT; T＆GT;其余= list.subList（1，则为list.size（））;
        对于（名单＆LT; T＆GT;排列：置换（休息））{
            名单＆LT;列表＆LT; T＆GT;＆GT;子列表=新的ArrayList＆LT;列表＆LT; T＆GT;＆GT;（）;
            的for（int i = 0; I＆LT; = permutations.size（）;我++）{
                名单＆LT; T＆GT;子列表=新的ArrayList＆LT; T＆GT;（）;
                subList.addAll（排列）;
                subList.add（我，头）;
                subLists.add（子列表）;
            }
            output.addAll（子列表）;
        }
        返回输出;
    }
}
 

输出

的 P（3,3）：计算（6）： -  [[1，2，3]，[2，3，1]，[3，2，1]， [3，1,2]，[2，1,3]，[1,3，2]]
P（3,2）：计算（6）： -  [[3,1]，[2，1]，[3，2]，[1,3]，[2，3]，[1，2]]
P（3,1）：计算（3）： -  [[3]，[1]，[2]]
P（3,0）：计算（1）： -  [[]]
 

我的问题是，当我去增加数量在输入列表中。运行时间的增加和后输入列表中的11个数字，该方案几乎死亡。大约需要2 GB的内存来运行。

我有8GB的RAM和i5处理器的机器上运行此，所以速度和空间是没有问题的。

我会AP preciate，如果有人可以帮我写一个更有效的code。

解决方案

如果你想在15十岁上下或多个元素的所有排列，它们写入到磁盘或DB或东西，因为它们不适合在内存中。 编辑：豪斯 - 约翰逊特罗特算法。 这可能是你要寻找的。

I have written a program to find all the possible permutations of a given list of items. This precisely means that my program prints all possible P(n,r) values for r=0 to n

Below is the code:

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;
    }
}

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) :- [[]]

My problem is, as I go increasing the numbers in the input list. Running time increases and after 11 numbers in the input list, the program almost dies. Takes around 2 GB memory to run.

I am running this on a machine having 8GB RAM and i5 processor, so the speed and space is not a problem.

I would appreciate, if anyone can help me writing a more efficient code.

解决方案

If you want all permutations of 15-ish or more elements, write them to disk or a db or something, since they won't fit in memory. Edit: Steinhaus–Johnson–Trotter algorithm. This is probably what you're looking for.

这篇关于Java的code的号码列表的排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！