diff options
-rw-r--r-- | src/ch/epfl/xblast/Lists.java | 35 | ||||
-rw-r--r-- | test/ch/epfl/xblast/ListsTest.java | 15 |
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 @@ | |||
1 | package ch.epfl.xblast; | 1 | package ch.epfl.xblast; |
2 | 2 | ||
3 | import java.util.ArrayList; | 3 | import java.util.*; |
4 | import java.util.Collections; | ||
5 | import java.util.List; | ||
6 | import java.util.stream.Collectors; | 4 | import java.util.stream.Collectors; |
7 | import java.util.stream.Stream; | 5 | import java.util.stream.Stream; |
8 | 6 | ||
@@ -45,12 +43,39 @@ public final class Lists { | |||
45 | } | 43 | } |
46 | 44 | ||
47 | /** | 45 | /** |
46 | * Returns a copy of the given list with element e inserted at index i. | ||
47 | * | ||
48 | * @param l the list | ||
49 | * @param i the insertion index | ||
50 | * @param e the element to insert | ||
51 | * @param <T> the type of the list's elements | ||
52 | * @return a copy of the list with the element inserted | ||
53 | */ | ||
54 | public static <T> List<T> inserted(List<T> l, int i, T e) { | ||
55 | List<T> r = new LinkedList<>(l); | ||
56 | r.add(i, e); | ||
57 | return r; | ||
58 | } | ||
59 | |||
60 | /** | ||
48 | * Returns all the permutations of the elements of the given list | 61 | * Returns all the permutations of the elements of the given list |
49 | * | 62 | * |
50 | * @param l given list | 63 | * @param l given list |
64 | * @param <T> the type of the list's elements | ||
51 | * @return a list of all the permutations of the list | 65 | * @return a list of all the permutations of the list |
66 | * @throws IllegalArgumentException if the given list is null | ||
52 | */ | 67 | */ |
53 | public static <T> List<List<T>> permutations(List<T> l) { | 68 | public static <T> List<List<T>> permutations(List<T> l) { |
54 | return null; | 69 | if (l == null) throw new IllegalArgumentException(); |
70 | if (l.size() <= 1) return Collections.singletonList(l); | ||
71 | if (l.size() == 2) return Arrays.asList(l, Lists.reversed(l)); | ||
72 | |||
73 | List<List<T>> p = new LinkedList<>(); | ||
74 | for (List<T> sp : Lists.permutations(l.subList(1, l.size()))) | ||
75 | for (int i = 0; i <= sp.size(); ++i) | ||
76 | p.add(Lists.inserted(sp, i, l.get(0))); | ||
77 | |||
78 | return p; | ||
55 | } | 79 | } |
80 | |||
56 | } | 81 | } |
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; | |||
4 | 4 | ||
5 | import java.util.ArrayList; | 5 | import java.util.ArrayList; |
6 | import java.util.Arrays; | 6 | import java.util.Arrays; |
7 | import java.util.LinkedList; | ||
7 | import java.util.List; | 8 | import java.util.List; |
8 | import java.util.stream.Collectors; | 9 | import java.util.stream.Collectors; |
9 | import java.util.stream.IntStream; | 10 | import java.util.stream.IntStream; |
@@ -48,4 +49,18 @@ public class ListsTest { | |||
48 | assertEquals(mirrored.get(i), mirrored.get(mirrored.size() - 1 - i)); | 49 | assertEquals(mirrored.get(i), mirrored.get(mirrored.size() - 1 - i)); |
49 | } | 50 | } |
50 | 51 | ||
52 | @Test | ||
53 | public void isListPermuted() { | ||
54 | List<Integer> sampleList = Arrays.asList(1, 2, 3); | ||
55 | List<List<Integer>> expected = new LinkedList<>(); | ||
56 | expected.add(Arrays.asList(1, 2, 3)); | ||
57 | expected.add(Arrays.asList(2, 1, 3)); | ||
58 | expected.add(Arrays.asList(2, 3, 1)); | ||
59 | expected.add(Arrays.asList(1, 3, 2)); | ||
60 | expected.add(Arrays.asList(3, 1, 2)); | ||
61 | expected.add(Arrays.asList(3, 2, 1)); | ||
62 | |||
63 | assertEquals(expected, Lists.permutations(sampleList)); | ||
64 | } | ||
65 | |||
51 | } | 66 | } |