Today I was bored so I decided to write code to generate permutations with LINQ.
According to the article at mathsisfun there are two types of permutations
1) With repetitions
2) Without repetitions
The code for generating permutations with repetitions can be as follows
static IEnumerable<string> Permutations(int n, params char[] chars)
{
if (n > 1)
return from a in chars
from b in Permutations(n-1, chars)
select a+b;
else
return chars.Select(c=>c.ToString());
}
The code for generating permutations without repetitions can be as follows
static IEnumerable<string> Permutations(int n, params char[] chars)
{
if (n > chars.Length)
throw new ArgumentException("chars can not be less than n", "chars");
if (n > 1)
return from a in chars
from b in Permutations(n-1, chars.Where(c=>c!=a).ToArray())
select a+b;
else
return chars.Select(c=>c.ToString());
}
Note the check on chars length and n in the second version. This is necessary because you cant generate permutations of length 10 without repetitions using only 4 chars.
That permutation lock picture in the article reminds me of a object oriented hit counter I wrote (which is maybe inappropriately named ‘mechanical clock’).
The code for hit counter is as follows
class Clock<T>
{
Ring<T> firstRing;
List<Ring<T>> rings = new List<Ring<T>>();
public Clock(int length, params T[] digits)
{
if (digits.Length == 0)
throw new ArgumentException("You must provide one or more digits", "digits");
IVisitable<T> left = new NullVisitable<T>();
for (int i = 0; i < length; i++)
{
var nums = new Digit<T>[digits.Length];
for (int j = 0; j < nums.Length; j++)
nums[j] = new Digit<T>(digits[j]);
var ring = new Ring<T>(nums);
ring.Left = left;
left = ring;
rings.Add(ring);
}
this.firstRing = rings.Last();
}
public IEnumerable<T> GetValue()
{
for (int i = 0; i < rings.Count; i++)
yield return rings[i].Value;
}
public void Tick()
{
firstRing.Visit();
}
}
Every time a clock ticks or a hit occurs on a hit counter, the right most ring moves by one step.
When the ring reaches its last digit, it turns the ring on its left by one step (just like a clock’s needle work).
class Ring<T> : IVisitable<T>
{
IList<IVisitable<T>> digits;
int currentNumber;
public Ring(params IVisitable<T>[] digits)
{
this.digits = digits.ToList();
}
public T Value
{
get { return digits[currentNumber].Value; }
}
public IVisitable<T> Left
{
get { return digits[0].Left; }
set { digits[0].Left = value; }
}
public void Visit()
{
currentNumber = (currentNumber + 1) % digits.Count;
digits[currentNumber].Visit();
}
}
Ring as seen on a hit counter/car mileage tracker/permutation lock, is a set of digits
class Digit<T> : IVisitable<T>
{
public T Value { get; set; }
public IVisitable<T> Left { get; set; }
public Digit(T value)
{
Value = value;
Left = new NullVisitable<T>();
}
public void Visit()
{
Left.Visit();
}
}
IVisitable interface represents the behavior of being able to change a value, maybe it should have been named ITurnable that has Turn() instead of visit.
Null Visitable class represents a static value
class NullVisitable<T> : IVisitable<T>
{
public T Value { get; private set; }
public IVisitable<T> Left { get; set; }
public void Visit() { }
}
This is how you would use the clock
var clock = new Clock(5, 0, 1);
for (int i = 0; i < 5; i++)
{
Console.WriteLine(clock.GetValue().AsString());
clock.Tick();
}
AsString is an extension method which is as follows
public static string AsString(this IEnumerable<T> items)
{
string output = items.Aggregate(new StringBuilder(), (a, x) => a.Append(x)).ToString();
return output;
}
The net effect of calling tick repeatedly on the clock is of generating permutations with repetitions. This can be modified to generate permutations without repetitions which is left as an exercise for you.
