Hello I was assigned to create a recursive method to compute the permutations of

Question

Hello

I was assigned to create a recursive method to compute the permutations of an array.

"Implement the recursive method named permutation (marked TO DO) which can be found in

Permutation.java. This method takes an ArrayList<Integer> as an argument and returns

ArrayList<ArrayList<Integer>> as a result. For example, suppose you have a list of class wrap-

per Integer named list which contains [1,2,3] (from the rst index to the last index). By

calling the method permutation using the following statement (Permutation is a static class):

ArrayList<ArrayList<Integer>> result = Permutation.permutation(list);

The result should be [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] (not necessary in

that order). To generate this, you can perform the following steps:

1. Remove the rst index of the list and store it in a variable (let's named this variable firstEntry)

2. Permute the rest of the list which should give you a list of list (let's call this result)

3. For every list inside result, insert firstEntry into every valid index. Every time you insert,

you get a new list which will be a member of your nal result.

For example, start with the list [1,2,3], at step 1, you store 1 in firstEntry and the rest of

the list is [2,3]. After you permute the list [2,3], you should get the list of list [[2,3],[3,2]]

(let's call this result. The rst index of result is the list [2,3]. In that list, there are three

valid indexes, 0, 1, and 2, that we can insert an item. By inserting firstEntry into [2,3] at all

possible valid indexes, you will get three new lists, [1,2,3], [2,1,3], and [2,3,1]. The second

index of the result is the list [3,2]. Again, by inserting firstEntry into [3,2] at all possible

valid indexes, you will get three new lists, [1,3,2], [3,1,2], and [3,2,1]. Note that all new

lists are permutation of the list [1,2,3]. You can see that the step 2 above is where recursive call

happens. Do not forget about the base case."

I have just learned about recursive cases and am having trouble implementing the method. This is what I have so far-

package cs0445Lab5;

import java.util.ArrayList;

public class Permutation

{

public static ArrayList<ArrayList<Integer>> permutation(final ArrayList<Integer> list)

{

//To take care of a permutation with one element

       if(list.size()==1)

      {

         //Causing an error

       //return(list);

    }

     int first;

     int i=0;

     ArrayList<Integer> lis = new ArrayList<Integer>();

     first=list.get(i);

     for(int x=0; x<list.size()-1; x++)

     {

            //The loop to make the actual permutations

     }

     if(i==list.size())

     {

          return(null);

     }

     else

     {

          return (permutation(lis));

     }

}

}

Any help would be greatly appreciated!!!

Thanks!

Explanation / Answer

SORRY I UNABLE TO USE YOUR INPUTS PROGRAM WHICH WAS GIVE FOR YOUR BASIC IDEA IT WILL NOT GENERATE OUTPUT.FOR GETTING OUTPUT FOR permutations YOU NEED USE MY PROGRAM . import java.util.Arrays; public class Permute { // swap 2 elements of an array, void swap(int[] arr, int x, int y) { int temp = arr[x]; arr[x] = arr[y]; arr[y] = temp; } /** * print permutations of array * @param arr * original int array, */ void permute(int[] arr) { permute(arr, 0, arr.length - 1); } /** * print permutations of array * * @param arr * original int array, * @param i * start index * @param n * end index */ void permute(int[] arr, int i, int n) { int j; if (i == n) System.out.println(Arrays.toString(arr)); else { for (j = i; j

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

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