Guest User

Horrible code bruteforcing the combinatorial Hirsch Conjectu

a guest
Jan 14th, 2014
63
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define GenerateFamilies
  2. #define Switch
  3. using System;
  4. using System.Collections.Generic;
  5. using System.Diagnostics;
  6. using System.Linq;
  7. using System.Text;
  8. using System.Threading.Tasks;
  9.  
  10. namespace HirschBruteforcer
  11. {
  12.     public static class Program
  13.     {
  14.         public const int N = 6;
  15.         public const int D = 3;
  16.         public const int F = 2;
  17.         public static List<Subset> AllSubsets;
  18.         public static void Main(string[] args)
  19.         {
  20.             Stopwatch watch = Stopwatch.StartNew();
  21.             AllSubsets = Subset.AllSubsets(Program.N, Program.D);
  22.  
  23.             //BreadthFirstHirsch.BreadthFirstHirschSearch();
  24.             //DepthFirstHirsch.DepthFirstHirschSearch();
  25.             FasterDepthFirstHirsch.FasterDepthFirstHirschSearch();
  26.  
  27.             watch.Stop();
  28.             Console.WriteLine("Time taken: " + watch.Elapsed);
  29.             while (true) { }
  30.         }
  31.     }
  32.     public static class FasterDepthFirstHirsch
  33.     {
  34.         private static object theLock = new object();
  35.         private static int maxT = 0;
  36.         private static IntervalCompressedHirschSequence best = null;
  37.         private static object counterLock = new object();
  38.         private static int delayer = 0;
  39.         private static int currentCounter = 0;
  40.         private static int totalCounter = 0;
  41.         public static void FasterDepthFirstHirschSearch()
  42.         {
  43.             Subset first = Program.AllSubsets.Where(s => s.Flags[0] && s.Flags.Count(b => b) == 1).First();
  44.             Subset second = Program.AllSubsets.Where(s => s.Flags[0] && s.Flags[1] && s.Flags.Count(b => b) == 2).First();
  45.             Subset third = Program.AllSubsets.Where(s => s.Flags[Program.N - 1] && s.Flags.Count(b => b) == 1).First();
  46.             Subset fourth = Program.AllSubsets.Where(s => s.Flags[Program.N - 1] && s.Flags[Program.N - 2] && s.Flags.Count(b => b) == 2).First();
  47.             IntervalCompressedHirschSequence root = new IntervalCompressedHirschSequence(first, third, fourth);
  48.             IntervalCompressedHirschSequence root2 = new IntervalCompressedHirschSequence(root, new List<Subset>() { second }, second.Flags);
  49.             List<IntervalCompressedHirschSequence> currentSet = new List<IntervalCompressedHirschSequence>();
  50.             root2.TestCompatible(Program.AllSubsets);
  51.             IntervalCompressedHirschSequenceSet cache = new IntervalCompressedHirschSequenceSet();
  52.             root2.GenerateNewSets(currentSet, cache, 3);
  53.             foreach (IntervalCompressedHirschSequence chs in currentSet)
  54.             {
  55.                 todoList.Push(new ParallelData()
  56.                 {
  57.                     currentSequence = chs,
  58.                     t = 4
  59.                 });
  60.             }
  61.             currentCounter = currentSet.Count;
  62.             totalCounter = currentSet.Count;
  63.             Console.WriteLine("Initial generation done, for a total of " + totalCounter);
  64.             While(() =>
  65.             {
  66.                 lock (todoList)
  67.                 {
  68.                     return todoList.Any();
  69.                 }
  70.             }, () =>
  71.             {
  72.                 ParallelData data;
  73.                 lock (todoList)
  74.                 {
  75.                     if (todoList.Any())
  76.                     {
  77.                         data = todoList.Pop();
  78.                     }
  79.                     else
  80.                     {
  81.                         return;
  82.                     }
  83.                 }
  84.                 DepthFirstHirschSearchRec(data.currentSequence, data.t, cache, third, fourth);
  85.             });
  86.             Console.WriteLine("Done, best t found was " + maxT);
  87. #if GenerateFamilies
  88.             Console.WriteLine("An example is " + best.Wrap(fourth, third).GenerateFamily());
  89. #endif
  90.         }
  91.         private struct ParallelData
  92.         {
  93.             public IntervalCompressedHirschSequence currentSequence;
  94.             public int t;
  95.         }
  96.         private static Stack<ParallelData> todoList = new Stack<ParallelData>();
  97.         private static IEnumerable<bool> IterateUntilFalse(Func<bool> condition)
  98.         {
  99.             while (condition()) yield return true;
  100.         }
  101.         public static void While(Func<bool> condition, Action body)
  102.         {
  103.             Parallel.ForEach(IterateUntilFalse(condition), new ParallelOptions()
  104.                 {
  105.                     MaxDegreeOfParallelism = 7
  106.                 },
  107.                 ignored => body());
  108.         }
  109.         private static void DepthFirstHirschSearchRec(IntervalCompressedHirschSequence currentSequence, int t, IntervalCompressedHirschSequenceSet cache, Subset third, Subset fourth)
  110.         {
  111.             List<IntervalCompressedHirschSequence> newSet = new List<IntervalCompressedHirschSequence>();
  112.             currentSequence.TestCompatible(Program.AllSubsets);
  113.             currentSequence.GenerateNewSets(newSet, cache, t);
  114.             if (newSet.Count > 0)
  115.             {
  116.                 if ((t + 2) > maxT)
  117.                 {
  118.                     lock (theLock)
  119.                     {
  120.                         if ((t + 2) > maxT)
  121.                         {
  122.                             Console.WriteLine("New record at " + (t + 2));
  123.                             maxT = (t + 2);
  124.                             best = newSet[0];
  125. #if GenerateFamilies
  126.                             Console.WriteLine("An example is " + best.Wrap(fourth, third).GenerateFamily());
  127. #endif
  128.                         }
  129.                     }
  130.                 }
  131.                 lock (todoList)
  132.                 {
  133.                     foreach (IntervalCompressedHirschSequence chs in newSet)
  134.                     {
  135.                         todoList.Push(new ParallelData()
  136.                         {
  137.                             currentSequence = chs,
  138.                             t = t + 1
  139.                         });
  140.                     }
  141.                 }
  142.             }
  143.             if (t == 4)
  144.             {
  145.                 lock (counterLock)
  146.                 {
  147.                     currentCounter--;
  148.                     delayer++;
  149.                     if (delayer >= 1)
  150.                     {
  151.                         Console.WriteLine(currentCounter + "/" + totalCounter);
  152.                         delayer = 0;
  153.                     }
  154.                 }
  155.             }
  156.         }
  157.     }
  158.     public class IntervalCompressedHirschSequence
  159.     {
  160. #if GenerateFamilies
  161.         private IntervalCompressedHirschSequence previous;
  162. #endif
  163.         public const int NotUsedYet = 0;
  164.         public const int Forbidden = 1;
  165.         public const int Active = 2;
  166.         public int[] SetStatus;
  167.         public List<Subset> LastFamily;
  168.         private bool[] UnionSubset;
  169.         bool usedNminus1th;
  170.         bool usedNminus2th;
  171.         bool usedNminus12th;
  172.         public IntervalCompressedHirschSequence(Subset lastFamily, params Subset[] forbiddenSets)
  173.         {
  174.             LastFamily = new List<Subset>();
  175.             LastFamily.Add(lastFamily);
  176.             SetStatus = new int[Program.AllSubsets.Count];
  177.             UnionSubset = lastFamily.Flags;
  178.             SetStatus[lastFamily.Index] = Active;
  179.             foreach (Subset s in forbiddenSets)
  180.             {
  181.                 SetStatus[s.Index] = Forbidden;
  182.             }
  183. #if GenerateFamilies
  184.             this.previous = null;
  185. #endif
  186.         }
  187.         public IntervalCompressedHirschSequence(IntervalCompressedHirschSequence intervalCompressedHirschSequence, List<Subset> newFamily, bool[] unionSubset)
  188.         {
  189.             usedNminus1th = intervalCompressedHirschSequence.usedNminus1th || newFamily.Any(s => s.Flags[Program.N - 1]);
  190.             usedNminus2th = intervalCompressedHirschSequence.usedNminus2th || newFamily.Any(s => s.Flags[Program.N - 2]);
  191.             usedNminus12th = intervalCompressedHirschSequence.usedNminus12th || newFamily.Any(s => s.Flags[Program.N - 1] && s.Flags[Program.N - 2]);
  192.             LastFamily = new List<Subset>(newFamily);
  193.             SetStatus = (int[])intervalCompressedHirschSequence.SetStatus.Clone();
  194.             for (int i = 0; i < SetStatus.Length; i++)
  195.             {
  196.                 switch (SetStatus[i])
  197.                 {
  198.                     case NotUsedYet:
  199.                         // Forbid B if there exists A with A subseteq B and (A subseteq (some old active set C)) and not (A subseteq (some new active set D))
  200.                         // Equivalent to:
  201.                         // Forbid B if there exists an old active set C such that for no new active set D, B intersect C subseteq D
  202.                         Subset B = Program.AllSubsets[i];
  203.                         if (intervalCompressedHirschSequence.LastFamily.Any(C => !newFamily.Any(D => Subset.IntersectionIsSubsetOf(B, C, D))))
  204.                         {
  205.                             SetStatus[i] = Forbidden;
  206.                         }
  207.                         break;
  208.                     case Forbidden:
  209.                         break;
  210.                     case Active:
  211.                         SetStatus[i] = Forbidden;
  212.                         break;
  213.                     default:
  214.                         break;
  215.                 }
  216.             }
  217.             foreach (Subset s in newFamily)
  218.             {
  219.                 SetStatus[s.Index] = Active;
  220.             }
  221.             UnionSubset = unionSubset;
  222. #if GenerateFamilies
  223.             this.previous = intervalCompressedHirschSequence;
  224. #endif
  225.         }
  226.         private List<Subset> compatibleSubsets = new List<Subset>();
  227.         public void TestCompatible(IEnumerable<Subset> allSubsets)
  228.         {
  229.             compatibleSubsets.AddRange(allSubsets.Where(s => IsCompatible(s)));
  230.         }
  231.         public bool IsCompatible(Subset S)
  232.         {
  233.             return SetStatus[S.Index] == NotUsedYet;
  234.         }
  235.         public void GenerateNewSets(List<IntervalCompressedHirschSequence> currentSet, IntervalCompressedHirschSequenceSet cache, int t)
  236.         {
  237.             if (usedNminus1th
  238.                 &&
  239.                 !compatibleSubsets.Any(s => s.Flags[Program.N - 1]))
  240.             {
  241.                 return;
  242.             }
  243.             if (usedNminus2th
  244.                 &&
  245.                 !compatibleSubsets.Any(s => s.Flags[Program.N - 2]))
  246.             {
  247.                 return;
  248.             }
  249.             if (usedNminus12th
  250.                 &&
  251.                 !compatibleSubsets.Any(s => s.Flags[Program.N - 1] && s.Flags[Program.N - 2]))
  252.             {
  253.                 return;
  254.             }
  255.             List<Subset> newFamily = new List<Subset>();
  256.             GenerateNewSetsRec(0, newFamily, currentSet, t, cache, false, false, false);
  257.         }
  258.         private void GenerateNewSetsRec(int start, List<Subset> newFamily, List<IntervalCompressedHirschSequence> currentSet, int t, IntervalCompressedHirschSequenceSet cache, bool gotNminus1th, bool gotNminus2th, bool gotNminus12th)
  259.         {
  260.             if (start == compatibleSubsets.Count)
  261.             {
  262.                 if ((newFamily.Count > 0)
  263.                     &&
  264.                     (newFamily.Count <= Program.F)
  265.                     &&
  266.                     (!usedNminus1th || gotNminus1th)
  267.                     &&
  268.                     (!usedNminus2th || gotNminus2th)
  269.                     &&
  270.                     (!usedNminus12th || gotNminus12th))
  271.                 {
  272.                     bool[] unionSubset = (bool[])UnionSubset.Clone();
  273.                     newFamily.ForEach(s =>
  274.                     {
  275.                         for (int i = 0; i < s.Flags.Length; i++)
  276.                         {
  277.                             unionSubset[i] |= s.Flags[i];
  278.                         }
  279.                     });
  280.                     if (Subset.IsAscending(unionSubset))
  281.                     {
  282.                         cache.GenerateIfNew(this, newFamily, unionSubset, currentSet, t);
  283.                     }
  284.                 }
  285.             }
  286.             else
  287.             {
  288.                 GenerateNewSetsRec(start + 1, newFamily, currentSet, t, cache, gotNminus1th, gotNminus2th, gotNminus12th);
  289.  
  290.                 if (newFamily.All(s => !s.ContainsSubset(compatibleSubsets[start])
  291.                                        &&
  292.                                        !s.IsContainedBySuperset(compatibleSubsets[start])))
  293.                 {
  294.                     if (compatibleSubsets[start].Flags[Program.N - 1])
  295.                     {
  296.                         gotNminus1th = true;
  297.                     }
  298.                     if (compatibleSubsets[start].Flags[Program.N - 2])
  299.                     {
  300.                         gotNminus2th = true;
  301.                     }
  302.                     if (compatibleSubsets[start].Flags[Program.N - 1] && compatibleSubsets[start].Flags[Program.N - 2])
  303.                     {
  304.                         gotNminus12th = true;
  305.                     }
  306.                     newFamily.Add(compatibleSubsets[start]);
  307.                     GenerateNewSetsRec(start + 1, newFamily, currentSet, t, cache, gotNminus1th, gotNminus2th, gotNminus12th);
  308.                     newFamily.RemoveAt(newFamily.Count - 1);
  309.                 }
  310.             }
  311.         }
  312.         public IntervalCompressedHirschSequence Wrap(params Subset[] rest)
  313.         {
  314.             IntervalCompressedHirschSequence current = this;
  315.  
  316.             for (int i = 0; i < rest.Length; i++)
  317.             {
  318.                 current = new IntervalCompressedHirschSequence(current, new List<Subset>() { rest[i] }, null);
  319.             }
  320.  
  321.             return current;
  322.         }
  323. #if GenerateFamilies
  324.         public string GenerateFamily()
  325.         {
  326.             StringBuilder b = new StringBuilder();
  327.  
  328.             GenerateFamilies(b);
  329.  
  330.             return b.ToString();
  331.         }
  332.         private void GenerateFamilies(StringBuilder b)
  333.         {
  334.             if (previous != null)
  335.             {
  336.                 previous.GenerateFamilies(b);
  337.                 b.Append(" ");
  338.             }
  339.             GenerateFamily(b);
  340.         }
  341.         private void GenerateFamily(StringBuilder b)
  342.         {
  343.             b.Append("{");
  344.             for (int i = 0; i < LastFamily.Count - 1; i++)
  345.             {
  346.                 LastFamily[i].ToString(b);
  347.                 b.Append(",");
  348.             }
  349.             LastFamily[LastFamily.Count - 1].ToString(b);
  350.             b.Append("}");
  351.         }
  352. #endif
  353.     }
  354.     public class IntervalCompressedHirschSequenceSet
  355.     {
  356.         private class Node<T>
  357.         {
  358.             public Node<T>[] lookup1;
  359.             public Node<T>[] lookup2;
  360.             public T value;
  361.             public Node<T> Retrieve1(int p)
  362.             {
  363.                 if (lookup1 == null)
  364.                 {
  365.                     lock (this)
  366.                     {
  367.                         if (lookup1 == null)
  368.                         {
  369.                             lookup1 = new Node<T>[Program.AllSubsets.Count];
  370.                         }
  371.                     }
  372.                 }
  373.                 if (lookup1[p] == null)
  374.                 {
  375.                     lock (lookup1)
  376.                     {
  377.                         if (lookup1[p] == null)
  378.                         {
  379.                             lookup1[p] = new Node<T>();
  380.                         }
  381.                     }
  382.                 }
  383.                 return lookup1[p];
  384.             }
  385.             public Node<T> Retrieve2(int p)
  386.             {
  387.                 if (lookup2 == null)
  388.                 {
  389.                     lock (this)
  390.                     {
  391.                         if (lookup2 == null)
  392.                         {
  393.                             lookup2 = new Node<T>[Program.AllSubsets.Count];
  394.                         }
  395.                     }
  396.                 }
  397.                 if (lookup2[p] == null)
  398.                 {
  399.                     lock (lookup2)
  400.                     {
  401.                         if (lookup2[p] == null)
  402.                         {
  403.                             lookup2[p] = new Node<T>();
  404.                         }
  405.                     }
  406.                 }
  407.                 return lookup2[p];
  408.             }
  409.         }
  410.         Node<int> root = new Node<int>();
  411.         public void GenerateIfNew(IntervalCompressedHirschSequence compressedHirschSequence, List<Subset> newFamily, bool[] unionSubset, List<IntervalCompressedHirschSequence> currentSet, int t)
  412.         {
  413.             IntervalCompressedHirschSequence newHirschSequence = new IntervalCompressedHirschSequence(compressedHirschSequence, newFamily, unionSubset);
  414.             Node<int> current = root;
  415.             for (int i = 0; i < newHirschSequence.SetStatus.Length; i++)
  416.             {
  417.                 switch (newHirschSequence.SetStatus[i])
  418.                 {
  419.                     case IntervalCompressedHirschSequence.NotUsedYet:
  420.                         break;
  421.                     case IntervalCompressedHirschSequence.Active:
  422.                         current = current.Retrieve1(i);
  423.                         break;
  424.                     case IntervalCompressedHirschSequence.Forbidden:
  425.                         current = current.Retrieve2(i);
  426.                         break;
  427.                 }
  428.             }
  429.             if (current.value < t)
  430.             {
  431.                 lock (current)
  432.                 {
  433.                     if (current.value < t)
  434.                     {
  435.                         current.value = t;
  436.                         currentSet.Add(newHirschSequence);
  437.                     }
  438.                 }
  439.             }
  440.         }
  441.     }
  442.     public static class DepthFirstHirsch
  443.     {
  444.         private static object theLock = new object();
  445.         private static int maxT = 0;
  446.         private static CompressedHirschSequence best = null;
  447.         private static int delayer = 0;
  448.         private static List<int> currentCounters = new List<int>();
  449.         private static List<int> totalCounters = new List<int>();
  450.         public static void DepthFirstHirschSearch()
  451.         {
  452.             Subset first = Program.AllSubsets.Where(s => s.Flags[0] && s.Flags.Count(b => b) == 1).First();
  453.             Subset second = Program.AllSubsets.Where(s => s.Flags[0] && s.Flags[1] && s.Flags.Count(b => b) == 2).First();
  454.             Subset third = Program.AllSubsets.Where(s => s.Flags[Program.N - 1] && s.Flags.Count(b => b) == 1).First();
  455.             Subset fourth = Program.AllSubsets.Where(s => s.Flags[Program.N - 1] && s.Flags[Program.N - 2] && s.Flags.Count(b => b) == 2).First();
  456.             CompressedHirschSequence root = new CompressedHirschSequence(first, third, fourth);
  457.             root.UnionAll[2] = true;
  458.             CompressedHirschSequence root2 = new CompressedHirschSequence(root, new List<Subset>() { second }, second.Flags);
  459.             root.UnionAll[2] = false;
  460.             List<CompressedHirschSequence> currentSet = new List<CompressedHirschSequence>();
  461.             root2.TestCompatible(Program.AllSubsets);
  462.             CompressedHirschSequenceSet cache = new CompressedHirschSequenceSet();
  463.             root2.GenerateNewSets(currentSet, cache, 3);
  464.             DepthFirstHirschSearchRec(currentSet, 4, cache, third, fourth);
  465.             Console.WriteLine("Done, best t found was " + maxT);
  466. #if GenerateFamilies
  467.             Console.WriteLine("An example is " + best.Wrap(fourth, third).GenerateFamily());
  468. #endif
  469.         }
  470.         private static void DepthFirstHirschSearchRec(List<CompressedHirschSequence> currentSet, int t, CompressedHirschSequenceSet cache, Subset third, Subset fourth)
  471.         {
  472.             while (currentCounters.Count <= t)
  473.             {
  474.                 currentCounters.Add(0);
  475.                 totalCounters.Add(0);
  476.             }
  477.             lock (currentCounters)
  478.             {
  479.                 currentCounters[t] += currentSet.Count;
  480.                 totalCounters[t] += currentSet.Count;
  481.                 delayer += currentSet.Count;
  482.                 if (delayer > 100000)
  483.                 {
  484.                     delayer = 0;
  485.                     for (int i = 4; i < currentCounters.Count; i++)
  486.                     {
  487.                         Console.Write(currentCounters[i]);
  488.                         Console.Write(" ");
  489.                     }
  490.                     Console.WriteLine();
  491.                     for (int i = 4; i < totalCounters.Count; i++)
  492.                     {
  493.                         Console.Write(totalCounters[i]);
  494.                         Console.Write(" ");
  495.                     }
  496.                     Console.WriteLine();
  497.                 }
  498.             }
  499.             Parallel.ForEach(currentSet, chs =>
  500.             {
  501.                 List<CompressedHirschSequence> newSet = new List<CompressedHirschSequence>();
  502.                 chs.TestCompatible(Program.AllSubsets);
  503.                 chs.GenerateNewSets(newSet, cache, t);
  504.                 if (newSet.Count > 0)
  505.                 {
  506.                     if ((t + 2) > maxT)
  507.                     {
  508.                         lock (theLock)
  509.                         {
  510.                             if ((t + 2) > maxT)
  511.                             {
  512.                                 Console.WriteLine("New record at " + (t+2));
  513.                                 maxT = (t + 2);
  514.                                 best = newSet[0];
  515. #if GenerateFamilies
  516.                                 Console.WriteLine("An example is " + best.Wrap(fourth, third).GenerateFamily());
  517. #endif
  518.                             }
  519.                         }
  520.                     }
  521.                     DepthFirstHirschSearchRec(newSet, t + 1, cache, third, fourth);
  522.                 }
  523.                 if (t == 4)
  524.                 {
  525.                     lock (currentCounters)
  526.                     {
  527.                         currentCounters[t]--;
  528.                     }
  529.                 }
  530.             });
  531.             if (t != 4)
  532.             {
  533.                 lock (currentCounters)
  534.                 {
  535.                     currentCounters[t] -= currentSet.Count;
  536.                 }
  537.             }
  538.         }
  539.     }
  540.     public static class BreadthFirstHirsch
  541.     {
  542.         public static void BreadthFirstHirschSearch()
  543.         {
  544.             List<Subset> allSubsets = Subset.AllSubsets(Program.N, Program.D);
  545.             Subset last = allSubsets.Where(s => s.Flags[Program.N - 1] && s.Flags.Count(b => b) == 1).First();
  546.             int maxT = 0;
  547.             CompressedHirschSequence best = null;
  548.             CompressedHirschSequence root = new CompressedHirschSequence(allSubsets[0]);
  549.             List<CompressedHirschSequence> currentSet = new List<CompressedHirschSequence>();
  550.             root.TestCompatible(allSubsets);
  551.             CompressedHirschSequenceSet cache = new CompressedHirschSequenceSet();
  552.             root.GenerateNewSets(currentSet, cache, 2);
  553.             int t = 2;
  554.             while (currentSet.Count > 0)
  555.             {
  556.                 Console.WriteLine("Found " + currentSet.Count + " sequences for t=" + (t+1));
  557.                 if ((t + 1) > maxT)
  558.                 {
  559.                     maxT = (t + 1);
  560.                     best = currentSet[0];
  561.                 }
  562.                 t++;
  563.                 List<CompressedHirschSequence> newSet = new List<CompressedHirschSequence>();
  564.                 foreach (CompressedHirschSequence chs in currentSet)
  565.                 {
  566.                     chs.TestCompatible(allSubsets);
  567.                     chs.GenerateNewSets(newSet, cache, t);
  568.                 }
  569.                 currentSet = newSet;
  570.             }
  571.             Console.WriteLine("Done, best t found was " + maxT);
  572. #if GenerateFamilies
  573.             Console.WriteLine("An example is " + best.Wrap(last).GenerateFamily());
  574. #endif
  575.         }
  576.     }
  577.     public class CompressedHirschSequence
  578.     {
  579. #if GenerateFamilies
  580.         private CompressedHirschSequence previous;
  581. #endif
  582.         public List<Subset> LastFamily = new List<Subset>();
  583.         public List<Subset> UnionOfPreviousFamilies = new List<Subset>();
  584.         public bool[] UnionAll;
  585.         private bool[] UnionSubset;
  586.         bool usedNminus1th;
  587.         bool usedNminus2th;
  588.         bool usedNminus12th;
  589.         public CompressedHirschSequence(Subset lastFamily, params Subset[] forbiddenSets)
  590.         {
  591.             usedNminus1th = lastFamily.Flags[Program.N - 1];
  592.             usedNminus2th = lastFamily.Flags[Program.N - 2];
  593.             LastFamily.Add(lastFamily);
  594.             UnionSubset = lastFamily.Flags;
  595.             UnionAll = new bool[Program.AllSubsets.Count];
  596.             UnionAll[lastFamily.Index] = true;
  597.             foreach (Subset s in forbiddenSets)
  598.             {
  599.                 UnionAll[s.Index] = true;
  600.             }
  601. #if GenerateFamilies
  602.             this.previous = null;
  603. #endif
  604.         }
  605.         public CompressedHirschSequence(CompressedHirschSequence compressedHirschSequence, List<Subset> newFamily, bool[] unionSubset)
  606.         {
  607.             usedNminus1th = compressedHirschSequence.usedNminus1th || newFamily.Any(s => s.Flags[Program.N - 1]);
  608.             usedNminus2th = compressedHirschSequence.usedNminus2th || newFamily.Any(s => s.Flags[Program.N - 2]);
  609.             usedNminus12th = compressedHirschSequence.usedNminus12th || newFamily.Any(s => s.Flags[Program.N - 1] && s.Flags[Program.N - 2]);
  610.             LastFamily = new List<Subset>(newFamily);
  611.             UnionOfPreviousFamilies = new List<Subset>(compressedHirschSequence.UnionOfPreviousFamilies);
  612.             UnionOfPreviousFamilies.AddRange(compressedHirschSequence.LastFamily);
  613.             UnionOfPreviousFamilies.Sort((s1, s2) => s1.Index.CompareTo(s2.Index));
  614.             UnionAll = (bool[])compressedHirschSequence.UnionAll.Clone();
  615.             UnionSubset = unionSubset;
  616. #if GenerateFamilies
  617.             this.previous = compressedHirschSequence;
  618. #endif
  619.         }
  620.         private List<Subset> compatibleSubsets = new List<Subset>();
  621.         public void TestCompatible(IEnumerable<Subset> allSubsets)
  622.         {
  623.             compatibleSubsets.AddRange(allSubsets.Where(s => IsCompatible(s)));
  624.         }
  625.         public bool IsCompatible(Subset S)
  626.         {
  627.             return !UnionAll[S.Index] && UnionOfPreviousFamilies.All(R => LastFamily.Any(T => Enumerable.Range(0, S.Flags.Length).All(i=>!R.Flags[i] || !S.Flags[i] || T.Flags[i])));
  628.         }
  629.         public void GenerateNewSets(List<CompressedHirschSequence> currentSet, CompressedHirschSequenceSet cache, int t)
  630.         {
  631.             if (usedNminus1th
  632.                 &&
  633.                 !compatibleSubsets.Any(s => s.Flags[Program.N - 1]))
  634.             {
  635.                 return;
  636.             }
  637.             if (usedNminus2th
  638.                 &&
  639.                 !compatibleSubsets.Any(s => s.Flags[Program.N - 2]))
  640.             {
  641.                 return;
  642.             }
  643.             if (usedNminus12th
  644.                 &&
  645.                 !compatibleSubsets.Any(s => s.Flags[Program.N - 1] && s.Flags[Program.N - 2]))
  646.             {
  647.                 return;
  648.             }
  649.             List<Subset> newFamily = new List<Subset>();
  650.             GenerateNewSetsRec(0, newFamily, currentSet, t, cache, false, false, false);
  651.         }
  652.         private void GenerateNewSetsRec(int start, List<Subset> newFamily, List<CompressedHirschSequence> currentSet, int t, CompressedHirschSequenceSet cache, bool gotNminus1th, bool gotNminus2th, bool gotNminus12th)
  653.         {
  654.             if (start == compatibleSubsets.Count)
  655.             {
  656.                 if ((newFamily.Count > 0)
  657.                     &&
  658.                     (newFamily.Count <= Program.F)
  659.                     &&
  660.                     (!usedNminus1th || gotNminus1th)
  661.                     &&
  662.                     (!usedNminus2th || gotNminus2th)
  663.                     &&
  664.                     (!usedNminus12th || gotNminus12th))
  665.                 {
  666.                     bool[] unionSubset = (bool[])UnionSubset.Clone();
  667.                     newFamily.ForEach(s =>
  668.                     {
  669.                         for (int i = 0; i < s.Flags.Length; i++)
  670.                         {
  671.                             unionSubset[i] |= s.Flags[i];
  672.                         }
  673.                     });
  674.                     if (Subset.IsAscending(unionSubset))
  675.                     {
  676.                         cache.GenerateIfNew(this, newFamily, unionSubset, currentSet, t);
  677.                     }
  678.                 }
  679.             }
  680.             else
  681.             {
  682.                 GenerateNewSetsRec(start + 1, newFamily, currentSet, t, cache, gotNminus1th, gotNminus2th, gotNminus12th);
  683.  
  684.                 if (newFamily.All(s => !s.ContainsSubset(compatibleSubsets[start])
  685.                                        &&
  686.                                        !s.IsContainedBySuperset(compatibleSubsets[start])))
  687.                 {
  688.                     if (compatibleSubsets[start].Flags[Program.N - 1])
  689.                     {
  690.                         gotNminus1th = true;
  691.                     }
  692.                     if (compatibleSubsets[start].Flags[Program.N - 2])
  693.                     {
  694.                         gotNminus2th = true;
  695.                     }
  696.                     if (compatibleSubsets[start].Flags[Program.N - 1] && compatibleSubsets[start].Flags[Program.N - 2])
  697.                     {
  698.                         gotNminus12th = true;
  699.                     }
  700.                     newFamily.Add(compatibleSubsets[start]);
  701.                     UnionAll[compatibleSubsets[start].Index] = true;
  702.                     GenerateNewSetsRec(start + 1, newFamily, currentSet, t, cache, gotNminus1th, gotNminus2th, gotNminus12th);
  703.                     newFamily.RemoveAt(newFamily.Count - 1);
  704.                     UnionAll[compatibleSubsets[start].Index] = false;
  705.                 }
  706.             }
  707.         }
  708.         public CompressedHirschSequence Wrap(params Subset[] rest)
  709.         {
  710.             CompressedHirschSequence current = this;
  711.  
  712.             for (int i = 0; i < rest.Length; i++)
  713.             {
  714.                 current = new CompressedHirschSequence(current, new List<Subset>() { rest[i] }, null);
  715.             }
  716.  
  717.             return current;
  718.         }
  719. #if GenerateFamilies
  720.         public string GenerateFamily()
  721.         {
  722.             StringBuilder b = new StringBuilder();
  723.  
  724.             GenerateFamilies(b);
  725.  
  726.             return b.ToString();
  727.         }
  728.         private void GenerateFamilies(StringBuilder b)
  729.         {
  730.             if (previous != null)
  731.             {
  732.                 previous.GenerateFamilies(b);
  733.                 b.Append(" ");
  734.             }
  735.             GenerateFamily(b);
  736.         }
  737.         private void GenerateFamily(StringBuilder b)
  738.         {
  739.             b.Append("{");
  740.             for (int i = 0; i < LastFamily.Count - 1; i++)
  741.             {
  742.                 LastFamily[i].ToString(b);
  743.                 b.Append(",");
  744.             }
  745.             LastFamily[LastFamily.Count - 1].ToString(b);
  746.             b.Append("}");
  747.         }
  748. #endif
  749.     }
  750.     public class CompressedHirschSequenceSet
  751.     {
  752.         private class Node<T>
  753.         {
  754.             public Node<T>[] lookup;
  755.             public T value;
  756.             public Node<T> Retrieve(int p)
  757.             {
  758.                 if (lookup == null)
  759.                 {
  760.                     lock (this)
  761.                     {
  762.                         if (lookup == null)
  763.                         {
  764.                             lookup = new Node<T>[Program.AllSubsets.Count];
  765.                         }
  766.                     }
  767.                 }
  768.                 if (lookup[p] == null)
  769.                 {
  770.                     lock(this)
  771.                     {
  772.                         if (lookup[p] == null)
  773.                         {
  774.                             lookup[p] = new Node<T>();
  775.                         }
  776.                     }
  777.                 }
  778.                 return lookup[p];
  779.             }
  780.         }
  781.         Node<Node<int>> root = new Node<Node<int>>();
  782.         public void GenerateIfNew(CompressedHirschSequence compressedHirschSequence, List<Subset> newFamily, bool[] unionSubset, List<CompressedHirschSequence> currentSet, int t)
  783.         {
  784.             Node<Node<int>> current1 = root;
  785.             foreach (Subset s in newFamily)
  786.             {
  787.                 current1 = current1.Retrieve(s.Index);
  788.             }
  789.             if (current1.value == null)
  790.             {
  791.                 lock (current1)
  792.                 {
  793.                     if (current1.value == null)
  794.                     {
  795.                         current1.value = new Node<int>();
  796.                     }
  797.                 }
  798.             }
  799.             Node<int> current2 = current1.value;
  800.             int unionIndex = 0;
  801.             int lastIndex = 0;
  802.             while (unionIndex < compressedHirschSequence.UnionOfPreviousFamilies.Count
  803.                    ||
  804.                    lastIndex < compressedHirschSequence.LastFamily.Count)
  805.             {
  806.                 if (unionIndex == compressedHirschSequence.UnionOfPreviousFamilies.Count)
  807.                 {
  808.                     current2 = current2.Retrieve(compressedHirschSequence.LastFamily[lastIndex].Index);
  809.                     lastIndex++;
  810.                 }
  811.                 else if (lastIndex == compressedHirschSequence.LastFamily.Count)
  812.                 {
  813.                     current2 = current2.Retrieve(compressedHirschSequence.UnionOfPreviousFamilies[unionIndex].Index);
  814.                     unionIndex++;
  815.                 }
  816.                 else
  817.                 {
  818.                     if (compressedHirschSequence.LastFamily[lastIndex].Index < compressedHirschSequence.UnionOfPreviousFamilies[unionIndex].Index)
  819.                     {
  820.                         current2 = current2.Retrieve(compressedHirschSequence.LastFamily[lastIndex].Index);
  821.                         lastIndex++;
  822.                     }
  823.                     else
  824.                     {
  825.                         current2 = current2.Retrieve(compressedHirschSequence.UnionOfPreviousFamilies[unionIndex].Index);
  826.                         unionIndex++;
  827.                     }
  828.                 }
  829.             }
  830.             if (current2.value < t)
  831.             {
  832.                 lock (current2)
  833.                 {
  834.                     if (current2.value < t)
  835.                     {
  836.                         current2.value = t;
  837.                         currentSet.Add(new CompressedHirschSequence(compressedHirschSequence, newFamily, unionSubset));
  838.                     }
  839.                 }
  840.             }
  841.         }
  842.     }
  843.     public class Subset
  844.     {
  845.         public int Index;
  846.         public bool[] Flags;
  847.         public static List<Subset> AllSubsets(int n, int d)
  848.         {
  849.             bool[] template = new bool[n];
  850.             List<Subset> result = new List<Subset>();
  851.  
  852.             AllSubsetsRec(n, d, 0, n, template, result);
  853.  
  854.             return result;
  855.         }
  856.         public static void AllSubsetsRec(int n, int d, int size, int current, bool[] template, List<Subset> result)
  857.         {
  858.             if (current == 0)
  859.             {
  860.                 if (size > 0)
  861.                 {
  862.                     result.Add(new Subset()
  863.                     {
  864.                         Index = result.Count,
  865.                         Flags = (bool[])template.Clone()
  866.                     });
  867.                 }
  868.             }
  869.             else
  870.             {
  871.                 AllSubsetsRec(n, d, size, current - 1 , template, result);
  872.                 if (size < d)
  873.                 {
  874.                     template[current - 1] = true;
  875.                     AllSubsetsRec(n, d, size + 1, current - 1, template, result);
  876.                     template[current - 1] = false;
  877.                 }
  878.             }
  879.         }
  880.         public bool IsContainedBySuperset(Subset subset)
  881.         {
  882.             return Enumerable.Range(0, Flags.Length).All(i => !Flags[i] || subset.Flags[i]);
  883.         }
  884.         public bool ContainsSubset(Subset subset)
  885.         {
  886.             return Enumerable.Range(0, Flags.Length).All(i => Flags[i] || !subset.Flags[i]);
  887.         }
  888. #if GenerateFamilies
  889.         public void ToString(StringBuilder b)
  890.         {
  891.             for (int i = 0; i < Flags.Length; i++)
  892.             {
  893.                 if (Flags[i])
  894.                 {
  895.                     b.Append(i);
  896.                 }
  897.             }
  898.         }
  899. #endif
  900.         public bool IsAscending()
  901.         {
  902.             return IsAscending(Flags);
  903.         }
  904.         public static bool IsAscending(bool[] flags)
  905.         {
  906.             int index = 0;
  907.             while (index < flags.Length && flags[index])
  908.             {
  909.                 index++;
  910.             }
  911.             for (int i = index; i < flags.Length; i++)
  912.             {
  913.                 if (flags[i])
  914.                 {
  915.                     return false;
  916.                 }
  917.             }
  918.             return true;
  919.         }
  920.         public static bool IntersectionIsSubsetOf(Subset B, Subset C, Subset D)
  921.         {
  922.             // return B intersect C subseteq D
  923.             return Enumerable.Range(0, B.Flags.Length).All(i => !(B.Flags[i] && C.Flags[i]) || D.Flags[i]);
  924.         }
  925.     }
  926. }
RAW Paste Data