Permutations of a certain length of a list (combinations, choose k of n, unordered)

ListPermutation.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class ListPermutation {

    public static void main(String[] args) {

        for (int i = 0; i < 6; i++) {
            System.out.println("Take " + i + " of 5: " + permutations(Arrays.asList(1, 2, 3, 4, 5), i));
        }
        System.out.println("Take 1 of 1: " + permutations(Collections.singletonList(1), 1));
        System.out.println("Take 1 of 0: " + permutations(new ArrayList<Integer>(), 1));

    }

    public static <T> List<List<T>> permutations(List<T> input, int select) {

        List<List<T>> res = new ArrayList<>();
        switch (select) {
            case 0:
                break;
            case 1:
                for (T t : input) {
                    res.add(Collections.singletonList(t));
                }
                break;
            default:
                for (int i = 0; i < input.size(); i++) {
                    T current = input.get(i);
                    List<T> subListBeforeCurrent = input.subList(0, i);

                    for (List<T> permutation : permutations(subListBeforeCurrent, select - 1)) {
                        List<T> currentRes = new ArrayList<>();
                        currentRes.addAll(permutation);
                        currentRes.add(current);
                        res.add(currentRes);
                    }
                }
        }
        return res;
    }
}

👍

Jo - looks good.

Nitpick: I believe the loop can be simplified a bit

// i from 1 and don't need the extra array copy
default:
    for (int i = 1; i < input.size(); i++) {
        T current = input.get(i);
        List<T> subListBeforeCurrent = input.subList(0, i);

        for (List<T> permutation : permutations(subListBeforeCurrent, select - 1)) {
            permutation.add(current);
            res.add(permutation);
        }
    }

Here's my attempt with C#

Not sure if it's more readable though .... The 2 Permut versions do the same thing only one is using link expression syntax. Matter of taste really. Also needed some helper methods that you normally would have in a lib of course.

To me this algorithm variation is easier to understand since it's building the results from left to right.

One thing to note is that these Permuts are actually lazy.

    public static class Debug
    {
        public static void Write<T>(IEnumerable<IEnumerable<T>> lists)
        {
            Console.WriteLine( "[" + string.Join(", ", lists.Select(l => "[" + string.Join(", ", l) + "]")) + "]");
        }
    }

    class MainClass
    {
        public static IEnumerable<T> Yield<T>(T t)
        {
            yield return t;
        }

        public static IEnumerable<T> Concat<T>(T t, IEnumerable<T> rest)
        {
            yield return t; foreach (var item in rest) yield return item;
        }

        public static IEnumerable<IEnumerable<T>> Permut<T>(IEnumerable<T> input, int groupSize, int start = 0)
        {
            return groupSize == 0
                ? Yield(Enumerable.Empty<T>())
                : input.Skip(start)
                    .SelectMany(
                        (first, idx)  => Permut(input, groupSize - 1, idx + start + 1),
                        (first, rest) => Concat(first, rest));
        }

        public static IEnumerable<IEnumerable<T>> Permut2<T>(IEnumerable<T> input, int groupSize, int start = 0)
        {
            return groupSize == 0
                ? Yield(Enumerable.Empty<T>())
                : from first in input.Skip(start).Select((val, idx) => new { val, idx })
                  from rest  in Permut2(input, groupSize - 1, first.idx + start + 1)
                  select Concat(first.val, rest);
        }

        public static void Main(string[] args)
        {
            Debug.Write(Permut(Enumerable.Range(0, 4), 2));
            // [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]
        }
    }

very cool! Lazy should also be possible in haskell 😄

@doubleday your comment on the Java solution wouldn't work because Collections.singletonList(t) (from case 1) doesn't allow .add() ;)

but my solution was also not correct in case 0, which should return an empty list inside the "result" list (selecting 0 out of n has always one solution, the empty list - otherwise it doesn't match https://en.wikipedia.org/wiki/Pascal's_triangle)

v2 fixes that, and actually doesn't need case 1 anymore, so of course we can simplify the loop (and yes start at 1 makes more sense..)
https://gist.github.com/LuzianW/4937cc6a5c98b1e07a6f

Excellent Code Luz!!