The best method so far


#1

public ArrayList<ArrayList> permute(ArrayList A) {
HashMap<Integer,Integer> map=new LinkedHashMap<Integer,Integer>();
for(int i:A){
map.put(i,map.containsKey(i)?map.get(i)+1:1);
}
Set<Map.Entry<Integer,Integer>> entryset=map.entrySet();
//System.out.println(map);
int arr[]=new int[map.size()];
int count[]=new int[map.size()];
ArrayList list2=new ArrayList(A.size());
for(int k=0;k<A.size();k++){
list2.add(0);
}
int i=0;
for(Map.Entry<Integer,Integer> entry: entryset){
arr[i]=entry.getKey();
count[i]=entry.getValue();
i++;
}
ArrayList<ArrayList> list1=new ArrayList<ArrayList>();
permutes(list1,list2,arr,count,0);
return list1;
}
private void permutes(ArrayList<ArrayList> list1,ArrayList list2,int[] arr,int[] count,int level){
if(level==list2.size()){
// System.out.println(list2+" i am list 2");
list1.add(new ArrayList(list2));
return;
}
for(int i=0;i<arr.length;i++){
if(count[i]==0){
continue;
}
list2.set(level,arr[i]);
count[i]–;
permutes(list1,list2,arr,count,level+1);
count[i]++;
}

}

#2

I would say Heap’s Algorithm is the best!
void heapPermutation(vector &A, int size, int n, vector<vector > &ans){
if(size==1){
ans.push_back(A);
}
else{
for(int i=0;i<size;i++){
heapPermutation(A,size-1,n,ans);
if(size & 1){
swap(A[0],A[size-1]);
}
else swap(A[i],A[size-1]);
}
}
}
vector<vector > Solution::permute(vector &A) {
vector temp = A;
int n =A.size();
vector<vector > ans;
heapPermutation(temp,n,n,ans);
return ans;
}