Write a recursive method public static ArrayList permuteArray(int[] array) that

Question

Write a recursive method public static ArrayList permuteArray(int[] array) that returns an ArrayList of all permutations of the the parameter array. The ArrayList may contain the arrays in any order.

Suppose array = {4, 7, 1, 2}. Then the ArrayList would contain the following arrays, but in any order:

4 7 1 2

7 4 1 2

2 1 4 7

1 2 4 7

4 7 2 1

7 4 2 1

2 1 7 4

1 2 7 4

4 2 1 7

7 1 2 4

2 7 4 1

1 4 2 7

4 2 7 1

7 1 4 2

2 7 1 4

1 4 7 2

4 1 2 7

7 2 1 4

2 4 1 7

1 7 2 4

4 1 7 2

7 2 4 1

2 4 7 1

1 7 4 2

Note: You are permitted to use at most two loops in solving this problem. A set of doubly-nested for-loops would count as two loops for this purpose. Recursion must be used in some non-trivial way to help solve the problem. You may write helper methods if you like.

Explanation / Answer

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

/**
*
* @author Surya
*/
public class permute {
  
   static ArrayList<ArrayList<Integer>> Permutation(ArrayList<Integer> ints) {//method which returns array with all permutations
    if (ints.size() == 1) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        list.add(ints);
        return list;
    } else {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        for (Integer i: ints) {
            ArrayList<Integer> subList = new ArrayList<>(ints);
            subList.remove(i);
            ArrayList<ArrayList<Integer>> subListNew = Permutation(subList);
            for (ArrayList<Integer> _list: subListNew) {
                ArrayList<Integer> local = new ArrayList<>();
                local.add(i);
                local.addAll(_list);
                list.add(local);
            }
        }
        return list;
    }
}

   public static ArrayList permuteArray(int[] array)//convernts array to array list
   {
       int l = array.length;
        ArrayList<Integer> chosen = new ArrayList<Integer>();
      
        int i,n;
        for(i=0;i<l;i++)
        {n=array[i];
        chosen.add(i,n);
        }
      
        //System.out.println(chosen);
      
        return Permutation(chosen);
      
      
   }

    public static void main(String[] args) {
  
     int[] a = {4,7,1,2};
   
       ArrayList<Integer> list=permuteArray(a);
       System.out.println(list);
    }
  
  
}

ouput:-

[[4, 7, 1, 2], [4, 7, 2, 1], [4, 1, 7, 2], [4, 1, 2, 7], [4, 2, 7, 1], [4, 2, 1, 7], [7, 4, 1, 2], [7, 4, 2, 1], [7, 1, 4, 2], [7, 1, 2, 4], [7, 2, 4, 1], [7, 2, 1, 4], [1, 4, 7, 2], [1, 4, 2, 7], [1, 7, 4, 2], [1, 7, 2, 4], [1, 2, 4, 7], [1, 2, 7, 4], [2, 4, 7, 1], [2, 4, 1, 7], [2, 7, 4, 1], [2, 7, 1, 4], [2, 1, 4, 7], [2, 1, 7, 4]]
BUILD SUCCESSFUL (total time: 0 seconds)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.