using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using NUnit.Framework; namespace Combinatorics { [TestFixture] public class Weighting { private readonly List<int> codes = new List<int>(); private readonly HashSet<int> availableCodes = new HashSet<int>(); private readonly Dictionary<int, int>[] decode = new[] { new Dictionary<int, int>(), new Dictionary<int, int>(), new Dictionary<int, int>() }; private readonly int[][] output = new[] { new int[12], new int[12], new int[12] }; public Weighting() { for (var a2 = -1; a2 <= 1; a2++) for (var a1 = -1; a1 <= 1; a1++) for (var a0 = -1; a0 <= 1; a0++) { var code = a0 + 3 * a1 + 9 * a2; if (code == 0) continue; decode[2][code] = a0; decode[1][code] = a1; decode[0][code] = a2; availableCodes.Add(code); codes.Add(code); } } [Test] public void Generate() { var sw = new Stopwatch(); sw.Start(); NextStep(0, 0); sw.Stop(); Console.WriteLine("Count = {0}, Elapsed time = {1}s.", count, sw.ElapsedMilliseconds / 1000d); } private void NextStep(int depth, int codePosition) { if (depth == 12) { Output(); return; } for (var r = codePosition; r < codes.Count; r++) { var code = codes[r]; if (!Increase(code)) continue; for (var i = 0; i < 3; i++) output[i][depth] = decode[i][code]; NextStep(depth + 1, r + 1); Decrease(code); } } private readonly int[,] counters = new int[3,3]; private bool Increase(int code) { if (!availableCodes.Contains(code)) return false; for (var i = 0; i < 3; i++) { var j = decode[i][code] + 1; if (counters[i, j] + 1 > 4) return false; } for (var i = 0; i < 3; i++) { var j = decode[i][code] + 1; counters[i, j]++; } availableCodes.Remove(-code); return true; } private void Decrease(int code) { for (var i = 0; i < 3; i++) { var j = decode[i][code] + 1; counters[i, j]--; } availableCodes.Add(-code); } private readonly Dictionary<int, string> transcript = new Dictionary<int, string> { { -1, "L" }, { 0, "-" }, { 1, "R" } }; private int count; private void Output() { count++; for (var i = 0; i < 3; i++) { Console.Write("["); Console.Write(string.Join(", ", output[i].Select(x => transcript[x]))); Console.WriteLine("]"); } Console.WriteLine(); } } }