7
Tôi đã viết một chương trình để tìm tất cả các hoán vị có thể có của một danh sách các mục nhất định. Đây chính xác có nghĩa là chương trình in của tôi tất cả có thể P (n, r) giá trị cho r = 0 đến nMã Java cho hoán vị của một danh sách các số
Dưới đây là các mã:
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) :- [[]]
Vấn đề của tôi là , khi tôi tăng số lượng trong danh sách đầu vào. Thời gian chạy tăng và sau 11 số trong danh sách đầu vào, chương trình gần như chết. Mất khoảng 2 GB bộ nhớ để chạy.
Tôi đang chạy trên máy có RAM 8GB và bộ xử lý i5, do đó tốc độ và không gian không phải là vấn đề.
Tôi sẽ đánh giá cao, nếu có ai có thể giúp tôi viết mã hiệu quả hơn.
Better phù hợp với [http://codereview.stackexchange.com/](http:/ /codereview.stackexchange.com/). –
@Anthony cảm ơn bạn :) Tôi mới đến điều này vì vậy, không có ý tưởng nơi để đặt những gì. – dharam