Generating permutations in F# and C#

Despite that article is called «Permutations Generation» I would rather want to emphasize on using functional recursive patterns helping to decompose complex problem on simple ones. Permutation algorithm is just an illustration of how we can implement algorithm using recursion. Here is the example. We have a list [1; 2; 3; 4] and want to get all permutations in lexicographic order. That's what should we get. [
[1; 2; 3; 4]; [1; 2; 4; 3]; [1; 3; 2; 4]; [1; 3; 4; 2]; [1; 4; 2; 3]; [1; 4; 3; 2];
[2; 1; 3; 4]; [2; 1; 4; 3]; [2; 3; 1; 4]; [2; 3; 4; 1]; [2; 4; 1; 3]; [2; 4; 3; 1];
[3; 1; 2; 4]; [3; 1; 4; 2]; [3; 2; 1; 4]; [3; 2; 4; 1]; [3; 4; 1; 2]; [3; 4; 2; 1];
[4; 1; 2; 3]; [4; 1; 3; 2]; [4; 2; 1; 3]; [4; 2; 3; 1]; [4; 3; 1; 2]; [4; 3; 2; 1]]
This data example sorted in lexicographic order gives us a key to solving this task: I intentionally formatted the output data such way that lists inside each row start from the same digit. First, we should divide source list on head and tail, 1 and [2; 3; 4], respectively. After that we can see that first row from output data can be produced by constructing list the following way: current head (1) and all possible permutations from current tail ([2; 3; 4]). So we get 1 and [2; 3; 4], 1 and [2; 4; 3]; 1 and [3; 4; 2] and etc. However, dividing into head and tail is not ordinary as in pattern matching where first element is the head and others are compose the tail. It is just a concept in our case. Implementation will be a little bit tricky. After we handled first row with 1 as head, we should go to the second row – the head in this case will be 2 and the tail will be [1; 3; 4]. In this case we constructed the tail by concatenating elements before the head and after the head – [1] and [3; 4], respectively. That's all theory we should know to start implementing the algorithm.

let generatePermutations source = 
    let rec generatePermutationsFrom prevElements tailElements =
        let rec nextStep source =
                match source with 
                            | [x; y] -> [[x; y]]
                            | x :: xs -> (generatePermutationsFrom [] xs |> List.map (fun perm -> x :: perm))
                            | _ -> []
        
        match tailElements with 
        | [] -> []
        | x :: xs ->
            let fullList = x :: (prevElements @ xs)
            (nextStep fullList) @ (generatePermutationsFrom (prevElements @ [x]) xs)
            
    generatePermutationsFrom [] source

The key aspects from this code are:
1. Constructing list the following way: current head (1) and all possible permutations from current tail ([2; 3; 4]).

let rec nextStep source =
                match source with 
                            | [x; y] -> [[x; y]]
                            | x :: xs -> (generatePermutationsFrom [] xs |> List.map (fun perm -> x :: perm))
                            | _ -> []

2. Selecting the new head and the new tail.

let fullList = x :: (prevElements @ xs)

Also we can use the main idea of this algorithm and easily rewrite it in C#.

static List<List<T>> GetPermutations<T>(List<T> source)
        {
            if (source.Count() < 2) return new List<List<T>> { source };
 
            var prevElements = new List<T>();
            var tailElements = source.Skip(1).ToList();
            var result = new List<List<T>>();
            foreach (var item in source)
            {
                var newList = Enumerable.Concat(prevElements, tailElements).ToList();
                var tailPermutations = GetPermutations(newList);
                foreach (var tailPermutation in tailPermutations)
                    result.Add(Enumerable.Concat(new T[] { item }, tailPermutation).ToList());
                prevElements.Add(item);
                tailElements = tailElements.Skip(1).ToList();
            }
            return result;
        }