/* Hitting Set (vertex cover) in Picat. http://mathworld.wolfram.com/VertexCover.html """ Let S be a collection of subsets of a finite set X. A subset Y of X that meets every member of S is called the vertex cover, or hitting set. The smallest possible such subset for a given graph G is known as a minimum vertex cover (Skiena 1990, p. 218), and its size is called the vertex cover number, denoted tau(G). """ For a graph example, see http://www.shannarasite.org/kb/kbse42.html (see below for the example) This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import mip. main => go. % % Problem 1..6. The easy ones. % go ?=> foreach(P in 1..6) do_hitting_set(P), nl end, nl. go => true. % % The harder problem 7. % % MIP: 4.5s % SAT: 16.7s % CP: > 4min % go2 => nolog, time2(do_hitting_set(7)), nl. do_hitting_set(P) => % N: number of nodes % V: the vertices % K: number of elements in the hitting set (to find) data(P,N,V,KK), println([problem=P,n=N,kk=KK]), % does x[i] belong to the hitting set? X = new_list(N), X :: 0..1, % number of elements in the hitting set K #= sum(X), hitting_set(V, X), solve($[min(K),ff,split,report(printf("k=%d\n",K))],X), println(k=K), println(x=X), println([I : I in 1..N, X[I] == 1]), nl. % % hitting_set(vertices, x) % hitting_set(V,X) => foreach(I in 1..X.len) % exists(j in v[i]) ( x[j] = 1 ) sum([ X[J] #= 1 : J in V[I]]) #>= 1 end. % % Data % % Example from % http://www.shannarasite.org/kb/kbse42.html % The hitting set according to this page is {3,5,6}, i.e. k = 3. % % There is another minimal hitting set: {3,4,6}. % data(1,N,V,K) => N=7, V = { {3}, {3}, {1,2,4,5}, {3,5,6}, {3,4,6}, {4,5,7}, {6}}, K = 3. % % The examples below are from the MiniZinc model % http://www.hakank.org/minizinc/maximal_independent_sets.mzn % % % Graph from % http://mathworld.wolfram.com/VertexCover.html % % 1 ------- 2 % | \ / | % | 3 - 4 | % | | | | % | 5 - 6 | % | / \ | % 7 ------- 8 % % There is 36 (minimal) hitting set with k = 4, e.g. % {1,2,3,4} % data(2,N,V,K) => N= 8, V = { {2,3,7}, {1,4,8}, {1,4,5}, {2,3,6}, {3,6,7}, {4,5,8}, {1,5,8}, {2,6,7} }, K = 4. % % http://mathworld.wolfram.com/VertexCover.html % % Wheel graph n = 8 % % 1 - 2 % / \ / \ % 3- 4 - 5 % | / | \ | % 6 - 7- 8 % % There is one minimal hitting set: {4} % data(3,N,V,K) => N = 8, V = { {2,3,4}, {1,4,5}, {1,4,6}, {1,2,3,4,6,7,8}, {2,4,8}, {3,4,6}, {4,6,8}, {4,5,7} }, K=1. % % http://mathworld.wolfram.com/VertexCover.html % % Bipartite graph K(3,3) % % There 9 minimal hitting sets with k = 2. % data(4,N,V,K) => K = 2, N = 6, V = { {2,4,6}, {1,3,5}, {2,4,6}, {1,3,5}, {2,4,6}, {1,3,5} }. % % http://mathworld.wolfram.com/VertexCover.html % % Petersen graph % There is 10 minimal hitting set with k = 4: % 1 2 3 6 % 1 2 4 7 % 1 3 5 8 % 2 4 5 9 % 4 6 8 9 % 3 7 8 9 % 3 4 5 10 % 5 6 7 10 % 2 7 8 10 % 1 6 9 10 % data(5,N,V,K) => K = 4, N = 10, V = { {2,3,6}, {1,4,7}, {1,5,8}, {2,5,9}, {3,4,10}, {1,9,10}, {2,8,10}, {3,7,9}, {4,6,8}, {5,6,7} }. % % From http://www.hakank.org/minizinc/misp.mzn % (GLPK:s example for maximal independent sets, misp.mod in MiniZinc) % Data from: % """ % M.G.C. Resende, T.A.Feo, S.H.Smith, "Algorithm 787 -- FORTRAN % subroutines for approximate solution of the maximum independent set % problem using GRASP," Trans. on Math. Softw., Vol. 24, No. 4, % December 1998, pp. 386-394. % """ % There are 13 solutions with optimal solution k=3. data(6,N,V,K) => K = 3, N = 50, V = { {2,3,5,7,8,12,15,16,19,20,21,22,28,30,34,35,37,41,42,47,50}, {1,3,5,6,7,8,9,10,13,17,19,20,21,23,25,26,29,31,35,36,44,45,46,50}, {1,2,5,6,8,9,10,11,14,16,23,24,26,27,28,29,30,31,34,35,36,39,41,42,43,44,50}, {6,7,9,10,11,13,14,15,17,21,22,23,24,25,27,28,30,31,33,34,35,36,37,38,40,41,42,46,49}, {1,2,3,6,11,14,21,24,25,28,35,38,39,41,44,49,50}, {2,3,4,5,8,9,10,13,14,16,17,19,22,23,26,27,30,34,35,38,39,40,41,44,45,47,50}, {1,2,4,8,9,10,11,13,15,16,18,20,22,23,24,25,33,35,36,38,43,45,46,47}, {1,2,3,6,7,10,11,13,16,17,18,19,20,21,22,23,24,25,26,33,35,36,39,42,44,48,49}, {2,3,4,6,7,12,14,17,19,20,23,28,30,31,32,33,34,38,39,42,44,45,46}, {2,3,4,6,7,8,11,13,15,16,17,20,21,22,23,25,26,27,28,30,31,32,37,38,41,43,44,45,50}, {3,4,5,7,8,10,12,14,15,18,21,24,25,26,29,32,33,35,36,37,39,40,42,43,45,47,49,50}, {1,9,11,13,16,17,19,24,25,26,30,31,32,34,36,37,39,41,44,47,48,49}, {2,4,6,7,8,10,12,15,16,18,19,20,22,23,24,27,28,29,31,33,35,36,37,44,47,49,50}, {3,4,5,6,9,11,15,16,17,18,19,20,21,26,28,29,30,31,32,34,35,36,38,39,41,44,46,47,48}, {1,4,7,10,11,13,14,18,21,22,23,25,28,29,30,33,34,36,37,38,39,40,43,44,46,50}, {1,3,6,7,8,10,12,13,14,17,19,20,25,26,29,35,38,39,40,41,42,44}, {2,4,6,8,9,10,12,14,16,18,19,21,22,23,25,26,28,29,33,37,44,45,48}, {7,8,11,13,14,15,17,20,24,27,28,31,32,34,35,36,37,38,45,48,49,50}, {1,2,6,8,9,12,13,14,16,17,22,24,28,29,36,37,39,41,43,45,48,49}, {1,2,7,8,9,10,13,14,16,18,21,22,24,25,26,27,29,30,31,33,34,35,38,39,41,42,43,44,45,46,48,49}, {1,2,4,5,8,10,11,14,15,17,20,22,23,29,31,35,38,42,46,47}, {1,4,6,7,8,10,13,15,17,19,20,21,23,26,27,28,29,30,39,40,41,42,44,45,46,47,49,50}, {2,3,4,6,7,8,9,10,13,15,17,21,22,28,31,32,33,34,35,36,39,40,41,42,44,45,48,49,50}, {3,4,5,7,8,11,12,13,18,19,20,25,27,29,30,31,33,34,38,42,43,44,49,50}, {2,4,5,7,8,10,11,12,15,16,17,20,24,26,27,29,30,33,34,36,38,40,41,42,44,46,47,48,49}, {2,3,6,8,10,11,12,14,16,17,20,22,25,28,31,32,33,37,38,39,40,41,42,45,47,48,49}, {3,4,6,10,13,18,20,22,24,25,29,30,33,34,35,39,40,46,48}, {1,3,4,5,9,10,13,14,15,17,18,19,22,23,26,29,37,40,42,44,46,47,50}, {2,3,11,13,14,15,16,17,19,20,21,22,24,25,27,28,35,38,39,41,42,48}, {1,3,4,6,9,10,12,14,15,20,22,24,25,27,31,32,35,37,38,40,43,45,46,47,48}, {2,3,4,9,10,12,13,14,18,20,21,23,24,26,30,33,35,38,40,41,42,44,46,47,50}, {9,10,11,12,14,18,23,26,30,33,35,39,40,46,49,50}, {4,7,8,9,11,13,15,17,20,23,24,25,26,27,31,32,34,36,37,40,42,43,44,45,50}, {1,3,4,6,9,12,14,15,18,20,23,24,25,27,33,35,36,37,38,40,43,44,49,50}, {1,2,3,4,5,6,7,8,11,13,14,16,18,20,21,23,27,29,30,31,32,34,36,38,41,42,43,45,46,47,49,50}, {2,3,4,7,8,11,12,13,14,15,18,19,23,25,33,34,35,37,39,40,41,42,43,48,50}, {1,4,10,11,12,13,15,17,18,19,26,28,30,33,34,36,38,41,43,46,47,48,49,50}, {4,5,6,7,9,10,14,15,16,18,20,21,24,25,26,29,30,31,34,35,37,41,45,46,48,49,50}, {3,5,6,8,9,11,12,14,15,16,19,20,22,23,26,27,29,32,36,43,46,47,48,49}, {4,6,11,15,16,22,23,25,26,27,28,30,31,32,33,34,36,43,45,48,50}, {1,3,4,5,6,10,12,14,16,19,20,22,23,25,26,29,31,35,36,37,38,42,43,44,45,46,48,49}, {1,3,4,8,9,11,16,20,21,22,23,24,25,26,28,29,31,33,35,36,41,43,44,46,48,49}, {3,7,10,11,15,19,20,24,30,33,34,35,36,37,39,40,41,42,45,46,48,50}, {2,3,5,6,8,9,10,12,13,14,15,16,17,20,22,23,24,25,28,31,33,34,41,42,45,48}, {2,6,7,9,10,11,17,18,19,20,22,23,26,30,33,35,38,40,41,43,44,46,47,48}, {2,4,7,9,14,15,20,21,22,25,27,28,30,31,32,35,37,38,39,41,42,43,45,49}, {1,6,7,11,12,13,14,21,22,25,26,28,30,31,35,37,39,45,49,50}, {8,12,14,17,18,19,20,23,25,26,27,29,30,36,37,38,39,40,41,42,43,44,45,49,50}, {4,5,8,11,12,13,18,19,20,22,23,24,25,26,32,34,35,37,38,39,41,42,46,47,48,50}, {1,2,3,5,6,10,11,13,15,18,22,23,24,28,31,32,33,34,35,36,37,38,40,43,47,48,49} }. % From % http://www2.research.att.com/~njas/doc/graphs.html % http://www2.research.att.com/~njas/doc/1dc.128.txt.gz % (this is an example of a hard problem in maximal % independent sets) % % Comment: fzntini solves this in 22:19minutes with this % solution; % k: 9 % 21 33 36 39 41 48 106 112 117 % data(7,N,V,K) => K = 9, N = 128, V = { {2,3,5,9,17,33,65}, % 1 {1,3,4,5,6,9,10,17,18,33,34,65,66}, % 2 {1,2,4,5,6,7,9,10,11,17,18,19,33,34,35,65,66,67}, % 3 {2,3,6,7,8,10,12,18,20,34,36,66,68}, % 4 {1,2,3,6,7,9,10,11,13,17,19,21,33,35,37,65,67,69}, % 5 {2,3,4,5,7,8,10,11,12,14,18,19,20,22,34,35,36,38,66,67,68,70}, % 6 {3,4,5,6,8,11,12,13,14,15,19,20,23,35,36,39,67,68,71}, % 7 {4,6,7,12,14,15,16,20,24,36,40,68,72}, % 8 {1,2,3,5,10,11,13,17,18,19,21,25,33,37,41,65,69,73}, % 9 {2,3,4,5,6,9,11,12,13,14,18,19,20,21,22,26,34,37,38,42,66,69,70,74}, % 10 {3,5,6,7,9,10,12,13,14,15,19,21,22,23,27,35,37,38,39,43,67,69,70,71,75}, % 11 {4,6,7,8,10,11,14,15,16,20,22,23,24,28,36,38,40,44,68,70,72,76}, % 12 {5,7,9,10,11,14,15,21,23,25,26,27,29,37,39,45,69,71,77}, % 13 {6,7,8,10,11,12,13,15,16,22,23,24,26,27,28,30,38,39,40,46,70,71,72,78}, % 14 {7,8,11,12,13,14,16,23,24,27,29,30,31,39,40,47,71,72,79}, % 15 {8,12,14,15,24,28,30,31,32,40,48,72,80}, % 16 {1,2,3,5,9,18,19,21,25,33,34,35,37,41,49,65,73,81}, % 17 {2,3,4,6,9,10,17,19,20,21,22,25,26,34,35,36,38,41,42,50,66,73,74,82}, % 18 {3,5,6,7,9,10,11,17,18,20,21,22,23,25,26,27,35,37,38,39,41,42,43,51,67,73,74,75,83}, % 19 {4,6,7,8,10,12,18,19,22,23,24,26,28,36,38,39,40,42,44,52,68,74,76,84}, % 20 {5,9,10,11,13,17,18,19,22,23,25,26,27,29,37,41,42,43,45,53,69,73,75,77,85}, % 21 {6,10,11,12,14,18,19,20,21,23,24,26,27,28,30,38,42,43,44,46,54,70,74,75,76,78,86}, % 22 {7,11,12,13,14,15,19,20,21,22,24,27,28,29,30,31,39,43,44,45,46,47,55,71,75,76,79,87}, % 23 {8,12,14,15,16,20,22,23,28,30,31,32,40,44,46,47,48,56,72,76,80,88}, % 24 {9,13,17,18,19,21,26,27,29,41,45,49,50,51,53,57,73,77,89}, % 25 {10,13,14,18,19,20,21,22,25,27,28,29,30,42,45,46,50,51,52,54,58,74,77,78,90}, % 26 {11,13,14,15,19,21,22,23,25,26,28,29,30,31,43,45,46,47,51,53,54,55,59,75,77,78,79,91}, % 27 {12,14,16,20,22,23,24,26,27,30,31,32,44,46,48,52,54,55,56,60,76,78,80,92}, % 28 {13,15,21,23,25,26,27,30,31,45,47,53,57,58,59,61,77,79,93}, % 29 {14,15,16,22,23,24,26,27,28,29,31,32,46,47,48,54,58,59,60,62,78,79,80,94}, % 30 {15,16,23,24,27,28,29,30,32,47,48,55,59,61,62,63,79,80,95}, % 31 {16,24,28,30,31,48,56,60,62,63,64,80,96}, % 32 {1,2,3,5,9,17,34,35,37,41,49,65,66,67,69,73,81,97}, % 33 {2,3,4,6,10,17,18,33,35,36,37,38,41,42,49,50,66,67,68,70,74,81,82,98}, % 34 {3,5,6,7,11,17,18,19,33,34,36,37,38,39,41,42,43,49,50,51,67,69,70,71,75,81,82,83,99}, % 35 {4,6,7,8,12,18,20,34,35,38,39,40,42,44,50,52,68,70,71,72,76,82,84,100}, % 36 {5,9,10,11,13,17,19,21,33,34,35,38,39,41,42,43,45,49,51,53,69,73,74,75,77,81,83,85,101}, % 37 {6,10,11,12,14,18,19,20,22,34,35,36,37,39,40,42,43,44,46,50,51,52,54,70,74,75,76,78,82,83,84,86,102}, % 38 {7,11,13,14,15,19,20,23,35,36,37,38,40,43,44,45,46,47,51,52,55,71,75,77,78,79,83,84,87,103}, % 39 {8,12,14,15,16,20,24,36,38,39,44,46,47,48,52,56,72,76,78,79,80,84,88,104}, % 40 {9,17,18,19,21,25,33,34,35,37,42,43,45,49,50,51,53,57,73,81,82,83,85,89,105}, % 41 {10,18,19,20,21,22,26,34,35,36,37,38,41,43,44,45,46,50,51,52,53,54,58,74,82,83,84,85,86,90,106}, % 42 {11,19,21,22,23,27,35,37,38,39,41,42,44,45,46,47,51,53,54,55,59,75,83,85,86,87,91,107}, % 43 {12,20,22,23,24,28,36,38,39,40,42,43,46,47,48,52,54,55,56,60,76,84,86,87,88,92,108}, % 44 {13,21,23,25,26,27,29,37,39,41,42,43,46,47,53,55,57,58,59,61,77,85,87,89,90,91,93,109}, % 45 {14,22,23,24,26,27,28,30,38,39,40,42,43,44,45,47,48,54,55,56,58,59,60,62,78,86,87,88,90,91,92,94,110}, % 46 {15,23,24,27,29,30,31,39,40,43,44,45,46,48,55,56,59,61,62,63,79,87,88,91,93,94,95,111}, % 47 {16,24,28,30,31,32,40,44,46,47,56,60,62,63,64,80,88,92,94,95,96,112}, % 48 {17,25,33,34,35,37,41,50,51,53,57,81,89,97,98,99,101,105,113}, % 49 {18,25,26,34,35,36,38,41,42,49,51,52,53,54,57,58,82,89,90,98,99,100,102,106,114}, % 50 {19,25,26,27,35,37,38,39,41,42,43,49,50,52,53,54,55,57,58,59,83,89,90,91,99,101,102,103,107,115}, % 51 {20,26,28,36,38,39,40,42,44,50,51,54,55,56,58,60,84,90,92,100,102,103,104,108,116}, % 52 {21,25,27,29,37,41,42,43,45,49,50,51,54,55,57,58,59,61,85,89,91,93,101,105,106,107,109,117}, % 53 {22,26,27,28,30,38,42,43,44,46,50,51,52,53,55,56,58,59,60,62,86,90,91,92,94,102,106,107,108,110,118}, % 54 {23,27,28,31,39,43,44,45,46,47,51,52,53,54,56,59,60,61,62,63,87,91,92,95,103,107,109,110,111,119}, % 55 {24,28,32,40,44,46,47,48,52,54,55,60,62,63,64,88,92,96,104,108,110,111,112,120}, % 56 {25,29,41,45,49,50,51,53,58,59,61,89,93,105,113,114,115,117,121}, % 57 {26,29,30,42,45,46,50,51,52,53,54,57,59,60,61,62,90,93,94,106,114,115,116,118,122}, % 58 {27,29,30,31,43,45,46,47,51,53,54,55,57,58,60,61,62,63,91,93,94,95,107,115,117,118,119,123}, % 59 {28,30,32,44,46,48,52,54,55,56,58,59,62,63,64,92,94,96,108,116,118,119,120,124}, % 60 {29,31,45,47,53,55,57,58,59,62,63,93,95,109,117,121,122,123,125}, % 61 {30,31,32,46,47,48,54,55,56,58,59,60,61,63,64,94,95,96,110,118,122,123,124,126}, % 62 {31,32,47,48,55,56,59,60,61,62,64,95,96,111,119,123,125,126,127}, % 63 {32,48,56,60,62,63,96,112,120,124,126,127,128}, % 64 {1,2,3,5,9,17,33,66,67,69,73,81,97}, % 65 {2,3,4,6,10,18,33,34,65,67,68,69,70,73,74,81,82,97,98}, % 66 {3,5,6,7,11,19,33,34,35,65,66,68,69,70,71,73,74,75,81,82,83,97,98,99}, % 67 {4,6,7,8,12,20,34,36,66,67,70,71,72,74,76,82,84,98,100}, % 68 {5,9,10,11,13,21,33,35,37,65,66,67,70,71,73,74,75,77,81,83,85,97,99,101}, % 69 {6,10,11,12,14,22,34,35,36,38,66,67,68,69,71,72,74,75,76,78,82,83,84,86,98,99,100,102}, % 70 {7,11,13,14,15,23,35,36,39,67,68,69,70,72,75,76,77,78,79,83,84,87,99,100,103}, % 71 {8,12,14,15,16,24,36,40,68,70,71,76,78,79,80,84,88,100,104}, % 72 {9,17,18,19,21,25,33,37,41,65,66,67,69,74,75,77,81,82,83,85,89,97,101,105}, % 73 {10,18,19,20,22,26,34,37,38,42,66,67,68,69,70,73,75,76,77,78,82,83,84,85,86,90,98,101,102,106}, % 74 {11,19,21,22,23,27,35,37,38,39,43,67,69,70,71,73,74,76,77,78,79,83,85,86,87,91,99,101,102,103,107}, % 75 {12,20,22,23,24,28,36,38,40,44,68,70,71,72,74,75,78,79,80,84,86,87,88,92,100,102,104,108}, % 76 {13,21,25,26,27,29,37,39,45,69,71,73,74,75,78,79,85,87,89,90,91,93,101,103,109}, % 77 {14,22,26,27,28,30,38,39,40,46,70,71,72,74,75,76,77,79,80,86,87,88,90,91,92,94,102,103,104,110}, % 78 {15,23,27,29,30,31,39,40,47,71,72,75,76,77,78,80,87,88,91,93,94,95,103,104,111}, % 79 {16,24,28,30,31,32,40,48,72,76,78,79,88,92,94,95,96,104,112}, % 80 {17,33,34,35,37,41,49,65,66,67,69,73,82,83,85,89,97,98,99,101,105,113}, % 81 {18,34,35,36,38,41,42,50,66,67,68,70,73,74,81,83,84,85,86,89,90,98,99,100,102,105,106,114}, % 82 {19,35,37,38,39,41,42,43,51,67,69,70,71,73,74,75,81,82,84,85,86,87,89,90,91,99,101,102,103,105,106,107,115}, % 83 {20,36,38,39,40,42,44,52,68,70,71,72,74,76,82,83,86,87,88,90,92,100,102,103,104,106,108,116}, % 84 {21,37,41,42,43,45,53,69,73,74,75,77,81,82,83,86,87,89,90,91,93,101,105,106,107,109,117}, % 85 {22,38,42,43,44,46,54,70,74,75,76,78,82,83,84,85,87,88,90,91,92,94,102,106,107,108,110,118}, % 86 {23,39,43,44,45,46,47,55,71,75,76,77,78,79,83,84,85,86,88,91,92,93,94,95,103,107,108,109,110,111,119}, % 87 {24,40,44,46,47,48,56,72,76,78,79,80,84,86,87,92,94,95,96,104,108,110,111,112,120}, % 88 {25,41,45,49,50,51,53,57,73,77,81,82,83,85,90,91,93,105,109,113,114,115,117,121}, % 89 {26,42,45,46,50,51,52,54,58,74,77,78,82,83,84,85,86,89,91,92,93,94,106,109,110,114,115,116,118,122}, % 90 {27,43,45,46,47,51,53,54,55,59,75,77,78,79,83,85,86,87,89,90,92,93,94,95,107,109,110,111,115,117,118,119,123}, % 91 {28,44,46,48,52,54,55,56,60,76,78,80,84,86,87,88,90,91,94,95,96,108,110,112,116,118,119,120,124}, % 92 {29,45,47,53,57,58,59,61,77,79,85,87,89,90,91,94,95,109,111,117,121,122,123,125}, % 93 {30,46,47,48,54,58,59,60,62,78,79,80,86,87,88,90,91,92,93,95,96,110,111,112,118,122,123,124,126}, % 94 {31,47,48,55,59,61,62,63,79,80,87,88,91,92,93,94,96,111,112,119,123,125,126,127}, % 95 {32,48,56,60,62,63,64,80,88,92,94,95,112,120,124,126,127,128}, % 96 {33,49,65,66,67,69,73,81,98,99,101,105,113}, % 97 {34,49,50,66,67,68,70,74,81,82,97,99,100,101,102,105,106,113,114}, % 98 {35,49,50,51,67,69,70,71,75,81,82,83,97,98,100,101,102,103,105,106,107,113,114,115}, % 99 {36,50,52,68,70,71,72,76,82,84,98,99,102,103,104,106,108,114,116}, % 100 {37,49,51,53,69,73,74,75,77,81,83,85,97,98,99,102,103,105,106,107,109,113,115,117}, % 101 {38,50,51,52,54,70,74,75,76,78,82,83,84,86,98,99,100,101,103,104,106,107,108,110,114,115,116,118}, % 102 {39,51,52,55,71,75,77,78,79,83,84,87,99,100,101,102,104,107,108,109,110,111,115,116,119}, % 103 {40,52,56,72,76,78,79,80,84,88,100,102,103,108,110,111,112,116,120}, % 104 {41,49,53,57,73,81,82,83,85,89,97,98,99,101,106,107,109,113,114,115,117,121}, % 105 {42,50,53,54,58,74,82,83,84,85,86,90,98,99,100,101,102,105,107,108,109,110,114,115,116,117,118,122}, % 106 {43,51,53,54,55,59,75,83,85,86,87,91,99,101,102,103,105,106,108,109,110,111,115,117,118,119,123}, % 107 {44,52,54,56,60,76,84,86,87,88,92,100,102,103,104,106,107,110,111,112,116,118,119,120,124}, % 108 {45,53,55,61,77,85,87,89,90,91,93,101,103,105,106,107,110,111,117,119,121,122,123,125}, % 109 {46,54,55,56,62,78,86,87,88,90,91,92,94,102,103,104,106,107,108,109,111,112,118,119,120,122,123,124,126}, % 110 {47,55,56,63,79,87,88,91,93,94,95,103,104,107,108,109,110,112,119,120,123,125,126,127}, % 111 {48,56,64,80,88,92,94,95,96,104,108,110,111,120,124,126,127,128}, % 112 {49,57,81,89,97,98,99,101,105,114,115,117,121}, % 113 {50,57,58,82,89,90,98,99,100,102,105,106,113,115,116,117,118,121,122}, % 114 {51,57,58,59,83,89,90,91,99,101,102,103,105,106,107,113,114,116,117,118,119,121,122,123}, % 115 {52,58,60,84,90,92,100,102,103,104,106,108,114,115,118,119,120,122,124}, % 116 {53,57,59,61,85,89,91,93,101,105,106,107,109,113,114,115,118,119,121,122,123,125}, % 117 {54,58,59,60,62,86,90,91,92,94,102,106,107,108,110,114,115,116,117,119,120,122,123,124,126}, % 118 {55,59,60,63,87,91,92,95,103,107,108,109,110,111,115,116,117,118,120,123,124,125,126,127}, % 119 {56,60,64,88,92,96,104,108,110,111,112,116,118,119,124,126,127,128}, % 120 {57,61,89,93,105,109,113,114,115,117,122,123,125}, % 121 {58,61,62,90,93,94,106,109,110,114,115,116,117,118,121,123,124,125,126}, % 122 {59,61,62,63,91,93,94,95,107,109,110,111,115,117,118,119,121,122,124,125,126,127}, % 123 {60,62,64,92,94,96,108,110,112,116,118,119,120,122,123,126,127,128}, % 124 {61,63,93,95,109,111,117,119,121,122,123,126,127}, % 125 {62,63,64,94,95,96,110,111,112,118,119,120,122,123,124,125,127,128}, % 126 {63,64,95,96,111,112,119,120,123,124,125,126,128}, % 127 {64,96,112,120,124,126,127} % 128 }.