Repository: TheAlgorithms/Java
Pull request #2932 (2022-01-31 19:36:38)

add permutation
### **Describe your change:**

- [ x] Add an algorithm?
- [ ] Fix a bug or typo in an existing algorithm?
- [ ] Documentation change?

#### References

<!-- Add any reference to previous pull-request or issue -->

### **Checklist:**

<!-- Remove items that do not apply. For completed items, change [ ] to [x]. -->

- [ x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [ x] This pull request is all my own work -- I have not plagiarized.
- [ x] I know that pull requests will not be merged if they fail the automated tests.
- [ x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
- [ x] All new Java files are placed inside an existing directory.
- [ x] All filenames are in all uppercase characters with no spaces or dashes.
- [ x] All functions and variable names follow Java naming conventions.
- [ x] All new algorithms have a URL in its comments that points to Wikipedia or other similar explanation.
- [ x] If this pull request resolves one or more open issues then the commit message contains `Fixes: #{$ISSUE_NO}`.


cpiao3: @siriak can you review this; added combination as well.
cpiao3: @siriak added tests and deleted main()

Patch:
diff --git a/src/main/java/com/thealgorithms/backtracking/Combination.java b/src/main/java/com/thealgorithms/backtracking/Combination.java
new file mode 100644
index 00000000..1298621a
--- /dev/null
+++ b/src/main/java/com/thealgorithms/backtracking/Combination.java
@@ -0,0 +1,52 @@
+package com.thealgorithms.backtracking;
+
+import java.util.*;
+
+/**
+ * Finds all permutations of given array
+ * @author Alan Piao (https://github.com/cpiao3)
+ */
+public class Combination {
+    private static int length;
+    /**
+     * Find all combinations of given array using backtracking
+     * @param arr the array.
+     * @param n length of combination
+     * @param <T> the type of elements in the array.
+     * @return a list of all combinations of length n. If n == 0, return null.
+     */
+    public static <T> List<TreeSet<T>> combination(T[] arr, int n) {
+        if (n == 0) {
+            return null;
+        }
+        length = n;
+        T[] array = arr.clone();
+        Arrays.sort(array);
+        List<TreeSet<T>> result = new LinkedList<>();
+        backtracking(array, 0, new TreeSet<T>(), result);
+        return result;
+    }
+    /**
+     * Backtrack all possible combinations of a given array
+     * @param arr the array.
+     * @param index the starting index.
+     * @param currSet set that tracks current combination
+     * @param result the list contains all combination.
+     * @param <T> the type of elements in the array.
+     */
+    private static <T> void backtracking(T[] arr, int index, TreeSet<T> currSet, List<TreeSet<T>> result) {
+        if (index + length - currSet.size() > arr.length) return;
+        if (length - 1 == currSet.size()) {
+            for (int i = index; i < arr.length; i++) {
+                currSet.add(arr[i]);
+                result.add((TreeSet<T>) currSet.clone());
+                currSet.remove(arr[i]);
+            }
+        }
+        for (int i = index; i < arr.length; i++) {
+            currSet.add(arr[i]);
+            backtracking(arr, i + 1, currSet, result);
+            currSet.remove(arr[i]);
+        }
+    }
+}
diff --git a/src/main/java/com/thealgorithms/backtracking/Permutation.java b/src/main/java/com/thealgorithms/backtracking/Permutation.java
new file mode 100644
index 00000000..58cc2991
--- /dev/null
+++ b/src/main/java/com/thealgorithms/backtracking/Permutation.java
@@ -0,0 +1,53 @@
+package com.thealgorithms.backtracking;
+
+import java.util.Arrays;
+import java.util.LinkedList;
+import java.util.List;
+
+/**
+ * Finds all permutations of given array
+ * @author Alan Piao (https://github.com/cpiao3)
+ */
+public class Permutation {
+    /**
+     * Find all permutations of given array using backtracking
+     * @param arr the array.
+     * @param <T> the type of elements in the array.
+     * @return a list of all permutations.
+     */
+    public static <T> List<T[]> permutation(T[] arr) {
+        T[] array = arr.clone();
+        List<T[]> result = new LinkedList<>();
+        backtracking(array, 0, result);
+        return result;
+    }
+    /**
+     * Backtrack all possible orders of a given array
+     * @param arr the array.
+     * @param index the starting index.
+     * @param result the list contains all permutations.
+     * @param <T> the type of elements in the array.
+     */
+    private static <T> void backtracking(T[] arr, int index, List<T[]> result) {
+        if (index == arr.length) {
+            result.add(arr.clone());
+        }
+        for (int i = index; i < arr.length; i++) {
+            swap(index, i, arr);
+            backtracking(arr, index + 1, result);
+            swap(index, i, arr);
+        }
+    }
+    /**
+     * Swap two element for a given array
+     * @param a first index
+     * @param b second index
+     * @param arr the array.
+     * @param <T> the type of elements in the array.
+     */
+    private static <T> void swap(int a, int b, T[] arr) {
+        T temp = arr[a];
+        arr[a] = arr[b];
+        arr[b] = temp;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/backtracking/CombinationTest.java b/src/test/java/com/thealgorithms/backtracking/CombinationTest.java
new file mode 100644
index 00000000..78e75b54
--- /dev/null
+++ b/src/test/java/com/thealgorithms/backtracking/CombinationTest.java
@@ -0,0 +1,33 @@
+package com.thealgorithms.backtracking;
+
+import org.junit.jupiter.api.Test;
+
+import java.util.Arrays;
+import java.util.List;
+import java.util.TreeSet;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+public class CombinationTest {
+    @Test
+    void testNoElement()
+    {
+        List<TreeSet<Integer>> result  = Combination.combination(new Integer[]{1, 2}, 0);
+        assertTrue(result == null);
+    }
+    @Test
+    void testLengthOne()
+    {
+        List<TreeSet<Integer>> result  = Combination.combination(new Integer[]{1, 2}, 1);
+        assertTrue(result.get(0).iterator().next() == 1);
+        assertTrue(result.get(1).iterator().next() == 2);
+    }
+    @Test
+    void testLengthTwo()
+    {
+        List<TreeSet<Integer>> result  = Combination.combination(new Integer[]{1, 2}, 2);
+        Integer[] arr = result.get(0).toArray(new Integer[2]);
+        assertTrue(arr[0] == 1);
+        assertTrue(arr[1] == 2);
+    }
+}
diff --git a/src/test/java/com/thealgorithms/backtracking/PermutationTest.java b/src/test/java/com/thealgorithms/backtracking/PermutationTest.java
new file mode 100644
index 00000000..60916b3e
--- /dev/null
+++ b/src/test/java/com/thealgorithms/backtracking/PermutationTest.java
@@ -0,0 +1,32 @@
+package com.thealgorithms.backtracking;
+
+import org.junit.jupiter.api.Test;
+
+import java.util.Arrays;
+import java.util.List;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+public class PermutationTest {
+    @Test
+    void testNoElement()
+    {
+        List<Integer []> result = Permutation.permutation(new Integer[]{});
+        assertEquals(result.get(0).length, 0);
+    }
+    @Test
+    void testSingleElement()
+    {
+        List<Integer []> result = Permutation.permutation(new Integer[]{1});
+        assertEquals(result.get(0)[0], 1);
+    }
+    @Test
+    void testMultipleElements()
+    {
+        List<Integer []> result = Permutation.permutation(new Integer[]{1, 2});
+        assertTrue(Arrays.equals(result.get(0), new Integer[]{1,2}));
+        assertTrue(Arrays.equals(result.get(1), new Integer[]{2,1}));
+    }
+
+
+}