LINQ Recipe No. 2-14: How to Generate Permutations

Contents

1. Introduction
2. Keywords
3. Problema
4. Solution
5. Discussion
5.1 Permutations
6. Practice: Generating Permutations
7. Conclusions
8. Literature & Links

1. Introduction

We will implement a recursive version to generate the permutations of a string literal. In discrete mathematics, specifically in counting techniques, a key topic is permutations: a permutation lets the programmer to count elements of a given set of a domain model. Given that, permutations has a great number of applications in computer science.

2. Keywords

• Computer science
• Counting
• Discrete mathematics
• Model
• Permutation

3. Problem

Generate permutations for the characters of a string literal.

4. Solution

An algorithm, in LINQ, will be implemented to generate partial permutations, and to generate all possible permutations.

5. Discussion

5.1 Permutations

In the context of mathematics, a permutation consists in the arrangement of elements of a set. For example, the list of numbers {1, 2, 3} has these six permutations (without repetition): 

(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 1), and (3, 2, 1).

In the same way, if we assign red to 1, green to 2, and blue to 3, we also have these six permutations ("Permutation [Wikipedia]", 2016): 

Illustration 1. Color permutations ("Permutation [Wikipedia]", 2016).

How do we calculate the number of permutations? It's easy: we must compute the factorial of the n elements in the set: 

6. Practice: Generating Permutations

For this LINQ recipe we are going to use LINQPad in C# Program mode: 

Illustration 2. LINQPad in C# Program mode.

Our code solution is implemented using C# programming language and LINQ standard query operators: 

LINQ file Permutations.linq [Alternative link][Alternative link]:

Method GeneratePartialPermutation(string) (lines 2-6) performs the following operations: 

• Lines 4-5: Creates a HashSet of string objects with partial permutations. If the string "abcd" is passed, it produces "abcd", "bacd", "cabd" and "dabc". These permutations are rotated versions of the given string object: each character is brung to the front and the others remain unchanged.

In the Main method these expressions are processed: 

• Line 13: Method GeneratePartialPermutation() is invoked to generate the first permutations for "abcd"; i.e., "abcd", "bacd", "cabd" and "dabc".
• Lines 17-45: Ensures that all possible permutations are generated.
• Lines 24-32: Partial permutations generated in line 13 are processed.
• Lines 35-43: Partial permutations generated in line 13 are processed in reverse order.

A test execution for this LINQ recipe is presented: 

7. Conclusions

Our implementation in section 6 has allowed us to understand a functional programming approach to generate permutations. We have also understood that permutations is a counting technique in discrete mathematics.

The next recipe will teach us how to generate a power set.

8. Literature & Links

Mukherjee, S (2014). Thinking in LINQ Harnessing the Power of Functional Programming in .NET Applications. United States: Apress.
Combinations and Permutations (2016, July 4). Retrieved from: https://www.mathsisfun.com/combinatorics/combinations-permutations.html
Permutation (2016, July 4). Retrieved from: http://mathworld.wolfram.com/Permutation.html
Permutation (2016, July 4). Retrieved from: https://en.wikipedia.org/wiki/Permutation

V