Permutations in C#

Question

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<string> list = new HashSet<string>();
 for (Rational a = 1; a <= 9; a++)
 {
 for (Rational b = 1; b <= 9; b++)
 {
 HashSet<Rational> unique2 = new HashSet<Rational>() { a, b };
 if (unique2.Count != 2) continue;
 for (Rational c = 1; c <= 9; c++)
 {
 HashSet<Rational> unique3 = new HashSet<Rational>() { a, b, c };
 if (unique3.Count != 3) continue;
 for (Rational d = 1; d <= 9; d++)
 {
 HashSet<Rational> unique4 = new HashSet<Rational>() { a, b, c, d };
 if (unique4.Count != 4) continue;
 for (Rational e = 1; e <= 9; e++)
 {
 HashSet<Rational> unique5 = new HashSet<Rational>() { a, b, c, d, e };
 if (unique5.Count != 5) continue;
 for (Rational f = 1; f <= 9; f++)
 {
 HashSet<Rational> unique6 = new HashSet<Rational>() { a, b, c, d, e, f };
 if (unique6.Count != 6) continue;
 for (Rational g = 1; g <= 9; g++)
 {
 HashSet<Rational> unique7 = new HashSet<Rational>() { a, b, c, d, e, f, g };
 if (unique7.Count != 7) continue;
 for (Rational h = 1; h <= 9; h++)
 {
 HashSet<Rational> unique8 = new HashSet<Rational>() { a, b, c, d, e, f, g, h };
 if (unique8.Count != 8) continue;
 for (Rational i = 1; i <= 9; i++)
 {
 HashSet<Rational> unique = new HashSet<Rational>() { 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)
 {
 list.Add(string.Format("{0} + 13 * {1} / {2} + {3} + 12 * {4} - {5} - 11 + {6} * {7} / {8} - 10 == 66", a, b, c, d, e, f, g, h, i));
 }
 }
 }
 }
 }
 }
 }
 }
 }
 }
 File.WriteAllText("resultsNonUnique.txt", string.Join(Environment.NewLine, list));
 Console.WriteLine(list.Count);
 Console.ReadLine();
 }
}

Adding the HashSets before a nesting loop makes the program faster for me. I know I can do comparisons individually instead but this is less tedious for me and still faster.

Someone wrote a Haskell solution for this, which looks like:

solutions = [ l | (l @ [a, b, c, d, e, f, g, h, i]) <- permutations [1 .. 9], a % 1 + 13 * b % c + d % 1 + 12 * e % 1 - f % 1 - 11 % 1 + g * h % i - 10 == 66 ]

Okay, granted that my output is more elegant, this code is a little intimidating. It's incredibly...short (I wonder if people see the irony between code and real life like I do).

Is there a way I can make my code shorter? Like with LINQ? If possible no external packages that I would need, but that's all okay.

• Gareth Rees: Nothing special about Haskell: you can write something of similar terseness in any language that has a permutations functions. For example, in Python: solutions = [p for p in itertools.permutations(range(1, 10)) for a, b, c, d, e, f, g, h, i in [p] if a + 13 * b / c + d + 12 * e - f - 11 + g * h / i - 10 == 66]

Answer 1

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<T[]> GetPermutations<T>(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();
}

• Nick Udell: GetPermutations looks like a good candidate for an extension method on IEnumerable<T>. Lazy evaluation might also be wise for such a method.
• Matt Cole: @NickUdell Good idea, it would make a nice extension method. The implementation is already lazy because SelectMany() is lazy.
• Nick Udell: SelectMany is indeed lazy, but you're taking an array as the parameter, which is inherently not lazy, and the conversion to an array will evaluate any lazy evaluation set up prior to that call.

Answer 2

Code organization

The purpose of this is to find solutions to a function. The calculation of the function's result should be a separate function, not part of the solver routine.

Variable types

Since a through g can only be integers, just use int. You can switch to Rational when you're evaluating the function.

Finding duplicates

HashSet is better than doing everything, but it's still not as fast as it could be. It would be better to use an array of bool for whether each integer has been used yet.

Code repetition

You've got a lot of repeated code. You need to find a way to factor that out.

First, replace a through g with a 9-element array of int.

Next, look at the big picture. Basically you're trying to traverse an implicit tree structure, pruning branches if you find any duplicates. So you should structure your code similarly. Keep track of your current depth, the array so far, and the array of what's used. When you reach a leaf, evaluate the function.