Add List permutation function and its test

2 files changed, 45 insertions, 5 deletions

diff --git a/src/ch/epfl/xblast/Lists.java b/src/ch/epfl/xblast/Lists.java
index f541b37..4ea45c2 100644
--- a/src/ch/epfl/xblast/Lists.java
+++ b/src/ch/epfl/xblast/Lists.java
@@ -1,8 +1,6 @@
 package ch.epfl.xblast;
 
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.List;
+import java.util.*;
 import java.util.stream.Collectors;
 import java.util.stream.Stream;
 
@@ -45,12 +43,39 @@ public final class Lists {
     }
 
     /**
+     * Returns a copy of the given list with element e inserted at index i.
+     *
+     * @param l   the list
+     * @param i   the insertion index
+     * @param e   the element to insert
+     * @param <T> the type of the list's elements
+     * @return a copy of the list with the element inserted
+     */
+    public static <T> List<T> inserted(List<T> l, int i, T e) {
+        List<T> r = new LinkedList<>(l);
+        r.add(i, e);
+        return r;
+    }
+
+    /**
      * Returns all the permutations of the elements of the given list
      *
-     * @param l given list
+     * @param l   given list
+     * @param <T> the type of the list's elements
      * @return a list of all the permutations of the list
+     * @throws IllegalArgumentException if the given list is null
      */
     public static <T> List<List<T>> permutations(List<T> l) {
-        return null;
+        if (l == null) throw new IllegalArgumentException();
+        if (l.size() <= 1) return Collections.singletonList(l);
+        if (l.size() == 2) return Arrays.asList(l, Lists.reversed(l));
+
+        List<List<T>> p = new LinkedList<>();
+        for (List<T> sp : Lists.permutations(l.subList(1, l.size())))
+            for (int i = 0; i <= sp.size(); ++i)
+                p.add(Lists.inserted(sp, i, l.get(0)));
+
+        return p;
     }
+
 }
diff --git a/test/ch/epfl/xblast/ListsTest.java b/test/ch/epfl/xblast/ListsTest.java
index b898399..b18b05e 100644
--- a/test/ch/epfl/xblast/ListsTest.java
+++ b/test/ch/epfl/xblast/ListsTest.java
@@ -4,6 +4,7 @@ import org.junit.Test;
 
 import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.LinkedList;
 import java.util.List;
 import java.util.stream.Collectors;
 import java.util.stream.IntStream;
@@ -48,4 +49,18 @@ public class ListsTest {
             assertEquals(mirrored.get(i), mirrored.get(mirrored.size() - 1 - i));
     }
 
+    @Test
+    public void isListPermuted() {
+        List<Integer> sampleList = Arrays.asList(1, 2, 3);
+        List<List<Integer>> expected = new LinkedList<>();
+        expected.add(Arrays.asList(1, 2, 3));
+        expected.add(Arrays.asList(2, 1, 3));
+        expected.add(Arrays.asList(2, 3, 1));
+        expected.add(Arrays.asList(1, 3, 2));
+        expected.add(Arrays.asList(3, 1, 2));
+        expected.add(Arrays.asList(3, 2, 1));
+
+        assertEquals(expected, Lists.permutations(sampleList));
+    }
+
 }