Permutations in C#

I have a program that will get all possible permutations of a certain equation:


A + 13 B / C + D + 12 E - F - 11 + G * H / I - 10 == 66

Where A, B....I is a value 1-9, and where each digit is used only once in the equation (So if A is 1, no other variable can be 1). There are 136 different solutions for this.

```
using System;
using System.Collections.Generic;
using System.IO;
using Rationals;

class Program
{
static void Main(string[] args)
{
HashSet list = new HashSet();
for (Rational a = 1; a unique2 = new HashSet() { a, b };
if (unique2.Count != 2) continue;
for (Rational c = 1; c unique3 = new HashSet() { a, b, c };
if (unique3.Count != 3) continue;
for (Rational d = 1; d unique4 = new HashSet() { a, b, c, d };
if (unique4.Count != 4) continue;
for (Rational e = 1; e unique5 = new HashSet() { a, b, c, d, e };
if (unique5.Count != 5) continue;
for (Rational f = 1; f unique6 = new HashSet() { a, b, c, d, e, f };
if (unique6.Count != 6) continue;
for (Rational g = 1; g unique7 = new HashSet() { a, b, c, d, e, f, g };
if (unique7.Count != 7) continue;
for (Rational h = 1; h unique8 = new HashSet() { a, b, c, d, e, f, g, h };
if (unique8.Count != 8) continue;
for (Rational i = 1; i unique = new HashSet() { a, b, c, d, e, f, g, h, i };
if (unique.Count != 9) continue;
if (a + (Rational)13 b / c + d + (Rational)12 e - f - (Rational)11 + g * h / i - (Rational)10 == 66)
{

There is a lot of room for improvement here, both in terms of performance and readability. You should start to worry when you see code forming an arrow shape - there is almost always a nicer way. The solution below is one way of tackling this, and also offers a large performance improvement (around 19.4s to 3.2s on my machine).

Generating Permutations

In the Haskell snippet you referenced, permutations [1 .. 9] is generating the a list of all the possible permutations of the numbers 1 through 9. I'm not aware of any nice way of doing this in C# other than hand rolling it. You can write a pretty short generic recursive function to do this.

private static IEnumerable GetPermutations(T[] values)
{
    if (values.Length == 1)
        return new[] {values};

    return values.SelectMany(v => GetPermutations(values.Except(new[] {v}).ToArray()),
        (v, p) => new[] {v}.Concat(p).ToArray());
}

The equivalent C# then becomes GetPermutations(Enumerable.Range(1, 9)).

Equation

Depending on what you are doing, you might want to consider creating an Equation class with a Calculate() method and override ToString(). Failing that, you can at least pull the equation logic out into separate methods.

private static Rational EquationCalculate(Rational[] args)
{
    return args[0] + 13*args[1]/args[2] + args[3] + 12*args[4] - args[5] - 11 + args[6]*args[7]/args[8] - 10;
}

private static string EquationToString(Rational[] args)
{
    return string.Format("{0} + 13 * {1} / {2} + {3} + 12 * {4} - {5} - 11 + {6} * {7} / {8} - 10",
        args[0], args[1], args[2], args[3], args[4], args[5], args[6], args[7], args[8]);
}

Results

Using the above short helper methods, you can rewrite your Main() method to be much shorter and more readable.

public static void Main()
{
    var rationals = Enumerable.Range(1, 9).Select(n => new Rational(n));
    var arguments = GetPermutations(rationals.ToArray());

    var results = arguments.Where(a => EquationCalculate(a) == 66)
        .Select(a => string.Format("{0} = {1}", EquationToString(a), 66)).ToArray();

    File.WriteAllLines("results.txt", results);
    Console.WriteLine(results.Length);
    Console.ReadKey();
}

StackExchange Code Review Q#91808, answer score: 3