Add List permutation function and its test

1 files changed, 30 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;
     }
+
 }