package algoexpert.medium;

/*

PROBLEM:

Generate all possible permutations

Example:

[1,2,3] -> [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

Solution:

1. Recursion -> Time : O(n! * n^2) | Space : O(n! * n)

2. Index Swap -> Time : O(n! * n) | Space : O(n! * n)

*/

import java.util.ArrayList;

public class Permutations

{

public static void test()

{

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

testArr.add(1);

testArr.add(2);

testArr.add(3);

System.out.println(getPermutations(testArr));

}

// SOLUTION 1

// Time : O(n! * n^2) | Space : O(n! * n)

public static void recursionHelper(ArrayList<Integer> build, ArrayList<Integer> array, ArrayList<ArrayList<Integer>> solution)

{

if (array.size() == 0 && build.size() > 0)

{

solution.add(build);

return;

}

for (int i = 0; i < array.size(); ++i)

{

ArrayList<Integer> newArray = new ArrayList<Integer> (array);

newArray.remove(i);

ArrayList<Integer> newBuild = new ArrayList<Integer> (build);

newBuild.add(array.get(i));

recursionHelper(newBuild, newArray, solution);

}

}

// SOLUTION 2

public static void swap(ArrayList<Integer> array, int i, int j)

{

int temp = array.get(i);

array.set(i, array.get(j));

array.set(j, temp);

}

// time : O(n! * n) | space : O(n! *n)

public static void indexHelper(int index, ArrayList<Integer> array, ArrayList<ArrayList<Integer>> solution)

{

if (index == array.size() - 1)

{

solution.add(new ArrayList<Integer>( array));

return;

}

for (int j = index; j < array.size(); ++j)

{

swap(array, index, j);

indexHelper(index + 1, array, solution);

swap(array, index, j);

}

}

public static ArrayList<ArrayList<Integer>> getPermutations(ArrayList<Integer> array)

{

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

//recursionHelper(new ArrayList<Integer>(), array, solution);

indexHelper(0, array, solution);

return solution;

}

}