# Horrible code bruteforcing the combinatorial Hirsch Conjectu

a guest
Jan 14th, 2014
174
0
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;
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.
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.                 {
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>();
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.         {
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.                     }
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;
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.             {
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.     }
541.     {
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];
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);
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.         {
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.                     }
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;
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.                 {
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. }