Compute all permutations of a list

ListPermutations.java

///usr/bin/env jbang "$0" "$@" ; exit $?

//DEPS org.junit.jupiter:junit-jupiter-api:5.7.2
//DEPS org.assertj:assertj-core:3.11.1

//JAVA 17

import static org.assertj.core.api.Assertions.assertThat;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Optional;
import java.util.stream.Collectors;

import org.junit.jupiter.api.Test;

public class ListPermutations {

    private static <T> List<List<T>> computePermutations(List<T> list) {
        return addOneRemaining(List.of(), list);
    }

    private static <T> List<List<T>> addOneRemaining(List<List<T>> list, List<T> remaining) {
        if (remaining.isEmpty()) {
            return list;
        }
        List<List<T>> r = new ArrayList<>();
        for (T e : remaining) {
            List<T> newRemaining = remaining.stream()
                    .filter(i -> i != e)
                    .toList();

            List<List<T>> newList;
            if (list.isEmpty()) {
                newList = List.of(List.of(e));
            } else {
                newList = list.stream()
                        .map(l -> {
                            List<T> n = new ArrayList<>();
                            n.addAll(l);
                            n.add(e);
                            return n;
                        })
                        .toList();
            }
            r.addAll(addOneRemaining(newList, newRemaining));
        }
        return r;
    }

    public static void main(String[] args) {
        List<String> list = Arrays.asList(args);
        System.out.println("input list:");
        System.out.println(listAsString(list));

        System.out.println("all permutations:");
        List<List<String>> all = computePermutations(list);
        System.out.println(allAsString(all));
    }

    private static String listAsString(List<String> list) {
        return list.stream()
                .collect(Collectors.joining(", ", "[", "]"));
    }

    private static String allAsString(List<List<String>> all) {
        return all.stream()
                .map(ListPermutations::listAsString)
                .collect(Collectors.joining("\n ", "[\n ", "\n]"));
    }

    @Test
    void testAB() throws Exception {
        List<String> list = List.of("a", "b");

        List<List<String>> result = computePermutations(list);
        System.out.println(allAsString(result));

        assertThat(result).hasSize(2)
                .anySatisfy(l -> assertThat(l).containsExactly("a", "b"))
                .anySatisfy(l -> assertThat(l).containsExactly("b", "a"));
    }

    @Test
    void testABC() throws Exception {
        List<String> list = List.of("a", "b", "c");
        runTest(list, 6);
    }

    @Test
    void testABCD() throws Exception {
        List<String> list = List.of("a", "b", "c", "d");
        runTest(list, 24);
    }

    @Test
    void testABCDE() throws Exception {
        List<String> list = List.of("a", "b", "c", "d", "e");
        runTest(list, 120);
    }

    private void runTest(List<String> list, int expected) {
        List<List<String>> result = computePermutations(list);
        System.out.println(allAsString(result));

        assertThat(result).hasSize(expected)
                .allSatisfy(l -> assertThat(l).containsExactlyInAnyOrderElementsOf(list));
        assertThat(result.stream()
                .distinct()
                .count()).isEqualTo(expected);
    }
}

Run it with jbang:

jbang run ListPermutations.java a b c

Produces the output:

input list:
[a, b, c]
all permutations:
[
 [a, b, c]
 [a, c, b]
 [b, a, c]
 [b, c, a]
 [c, a, b]
 [c, b, a]
]