Combinatorial Algorithm Program
A. First Edition
This is the assignment3 of comp6661 and they are a bunch of small programs. Some are from theory question and I feel
comfortable to solve these kind of questions by program, even in exam, if allowed, which is the very first experience for
me in Concordia.
1) post-order-rank
I feel like using function pointer arrays to make code look like complicated so that I can show off a little bit. However,
they indeed make code look nice and neat. It also reveals that some operations are similar that you can use template or
interface to encapsulate them.
The only useful, stupid and painful tip I got is that in windows VC++ long is not __int64 and it is only meaningful in java.
In VC++, long is similar to int and the counterpart of __int64 in Linux is long long.
So, this is what I wrote in previous version.
E.Further improvement
F.File listing
1. post.cpp (rank and unrank for post order of binomial tree)
2. subset.cpp (subset rank and successor in lexico, colex, revolving door order)
3. gensubset.cpp(generate all subset in textbook, Knuth successor and unrank function)
(In order to run in windows, you need to comment out the typedef for __int64 and size_t)
file name: post.cpp
#include <iostream> #include <cmath> using namespace std; const size_t mask= 0x80000000; size_t baseUnRankTable[4]={3,0,2,1}; size_t baseRankTable[4]={1, 3, 2, 0}; int findLeftMost(size_t rank) { size_t mask= 0x80000000; for (int i=0; i<32; i++) { if (rank & (mask>>i)) { return i; } } return -1; } void display(size_t number) { cout<<"["; for (size_t i=0; i<32; i++) { if (number& (mask>>i)) { cout<<"1"; } else { cout<<"0"; } } cout<<"]\n"; } size_t postUnRank(size_t node) { int pos; size_t result=0, source=node; while (source>3) { if ((pos=findLeftMost(source))==-1) { cout<<"error"; exit(1); } result+=(mask>>pos); result--; source^=(mask>>pos); } result+=baseUnRankTable[source]; return result; } size_t postRank(size_t r) { int pos; size_t result=0, source=r; while (source>3) { if ((pos=findLeftMost(source))==-1) { cout<<"error"; exit(1); } result+=(mask>>pos); source^=(mask>>pos); source+=1; } result+=baseRankTable[source]; return result; } int main() { size_t node=12; size_t rank=199999; cout<<"The rank in post order of node "; display(node); cout<<" is:"<<postUnRank(node)<<endl; cout<<"The 200,000th node in post order is in binary form:\n"; display(postRank(rank)); return 0; }
file name: subset.cpp
#include <iostream> using namespace std; int combineNumber(size_t n, size_t k) { int result =1; for (size_t i=0; i<k; i++) { result=result*(n-i)/(i+1); } return result; } int revolveRank(size_t n, size_t k, size_t* array) { int r, s; //size_t* temp=array-1;//this is highly risky!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! //but I am lazy and running out of time, if (k%2==0) { r=0; } else { r=-1; } s=1; for (int i=k; i>=1; i--) { //because knuth's version is starting from 0 r+=s*combineNumber(array[i]+1, i); s*=-1; } return r; } void revolveSuccessor(size_t n, size_t k, size_t* array) { size_t j; if (k%2==1) { if (array[1]+1<array[2]) { array[1]++; return; //goto R2; } else { j=2; goto R4; } } else { if (array[1]>0) { array[1]--; return; //goto R2; } else { j=2; goto R5; } } R4: if (array[j]>=j) { array[j]=array[j-1]; array[j-1]=j-2; return; //goto R2; } else { j++; } R5: if (array[j]+1<array[j+1]) { array[j-1]=array[j]; array[j]++; return; //goto R2; } else { j++; if (j<=k) { goto R4; } } } void revolveUnRank(size_t rank, size_t n, size_t k, size_t*array) { int last=-1, curr=-1, r=rank; int i; size_t x=n; for (i=k; i>=1; i--) { do { last=curr; curr=combineNumber(x, i); if (curr>r) { x--; } else { break; } }while (true); if (last==r) { array[i-1]=x-1; } else { array[i-1]=x; } r=last-r-1; } } //assume array contains k elements, index starts from 0 int lexRank(size_t n, size_t k, size_t* array) { size_t result=0, i,j, start, end; for (i=0; i<k; i++) { if (i==0) { start=0; end=array[0]; } else { start=array[i-1]+1; end=array[i]; } for (j=start; j<end; j++) { result+=combineNumber(n-j-1, k-i-1); } } return result; } void lexSuccessor(size_t n, size_t k, size_t* array) { //if i is possible to be negative, don't use size_t!!!!!!!!!! int result=0, i,j; j=0; i=k-1; for (i=k-1; i>=0; i--) { if (array[i]< n-(k-1)+i-1) { break; } } if (i<0) { cout<<"undefined"; exit(1); } else { result=array[i]; for (j=i; j<k; j++) { array[j]=result+1+j-i; } } } int colexRank(size_t n, size_t k, size_t* array) { int r=0; for (int i=0; i<k; i++) { r+=combineNumber(array[i], k-i); } return r; } //starting from index 0 with element starts from 0 void colexSuccessor(size_t n, size_t k, size_t* array) { int result=0, i=0, j=0; for (i=k-1; i>0; i--) { if (array[i]<array[i-1]-1) { break; } } if (i==0&&array[i]==n-1) { cout<<"undefined\n"; exit(1); } else { array[i]++; for (j=k-1; j>i; j--) { array[j]=k-1-j; } } } typedef void (*SuccessorFuncType)(size_t, size_t, size_t*); typedef int (*RankFuncType)(size_t, size_t, size_t*); RankFuncType rankArray[3]={lexRank, colexRank, revolveRank}; SuccessorFuncType successorArray[3]={lexSuccessor, colexSuccessor, revolveSuccessor}; char* rankNames[3]={"lexRank", "colexRank", "revolveRank"}; char* successorNames[3]={"lexSuccessor", "colexSuccessor", "revolveSuccessor"}; void copyArray(size_t* src, size_t* tgt, size_t size) { for (int i=0; i<size; i++) { tgt[i]=src[i]; } } void displayArray(size_t* array, size_t start, size_t size) { cout<<"["; for (int i=start; i<start+size; i++) { cout<<array[i]; if (i!=start+size-1) { cout<<","; } } cout<<"]\n"; } void reverseArray(size_t* array, size_t size) { size_t temp; if (size==1) { return; } for (int i=0; i<size/2; i++) { temp=array[i]; array[i]=array[size-i-1]; array[size-i-1]=temp; } } void doTest1(size_t n, size_t k, size_t* array) { size_t* old=new size_t[n]; size_t i; void copyArray(size_t* src, size_t* tgt, size_t size); void displayArray(size_t* array, size_t start, size_t size); void reverseArray(size_t* array, size_t size); cout<<"first let's compare rank\n"; for (i=0; i<3; i++) { cout<<"the rank of function "<<rankNames[i]<<" is "; copyArray(array, old, n); if (i==1) { reverseArray(array, k); } cout<<rankArray[i](n, k, array)<<endl; copyArray(old, array, k); } cout<<"now let's compare successor\n"; for (i=0; i<3; i++) { cout<<"the successor of function "<<successorNames[i]<<" is "; copyArray(array, old, n); if (i==1) { reverseArray(array, k); } successorArray[i](n, k, array); if (i<2) { displayArray(array, 0, k); } else { displayArray(array, 1, k); } copyArray(old, array, n); } delete[]old; } void initialize(size_t n, size_t k, size_t* array, size_t kind) { size_t i; switch(kind) { case 0: //lexco for (i=0; i<k+1; i++) { array[i]=i; } break; case 1: //colex for (i=0; i<k; i++) { array[i]=k-i-1; } break; case 2: //lexco array[0]=0; for (i=1; i<k+1; i++) { array[i]=i-1; } array[k+1]=n; break; } } void doTest2(size_t n, size_t k, size_t* array) { size_t* old=new size_t[n]; size_t i, j, total; total=combineNumber(n, k); for (i=0; i<3; i++) { initialize(n,k,array, i); cout<<"now generate by function "<<successorNames[i]<<endl; if (i<2) { displayArray(array, 0, k); } else { displayArray(array, 1, k); } cout<<"current rank=0\n"; for (j=0; j<total-1; j++) { cout<<"current rank="<<j+1<<endl; successorArray[i](n, k, array); if (i<2) { displayArray(array, 0, k); } else { displayArray(array, 1, k); } } } } int main() { size_t array[14]={0,3,6,7,9 ,0,0,0,0, 0,0,0,0, 0}; size_t backup[14]; size_t n=13, k=4; //displayArray(array, k); //doTest1(n, k, array); cout<<"so our subset is:\n"; displayArray(array+1, 0, k); copyArray(array, backup, 14); cout<<"lex rank: "<<lexRank(n, k, array+1)<<endl; lexSuccessor(n, k, array+1); cout<<"lex successor\n"; displayArray(array+1, 0, k); //backup copyArray(backup, array, 14); reverseArray(array+1, k); cout<<"colex rank: "<<colexRank(n, k, array+1)<<endl; colexSuccessor(n, k, array+1); cout<<"colex successor\n"; displayArray(array+1, 0, k); copyArray(backup, array, 14); cout<<"revolve rank: "<<revolveRank(n, k, array)<<endl; cout<<"revolve successor\n"; revolveSuccessor(n, k, array); displayArray(array+1, 0, k); //now let's do question 3-a //cout<<"now let's do assignment 3 question3-a\n"; //doTest2(n, k, array); return 0; }
file name: gensubset.cpp
#include <iostream> #include <time.h> using namespace std; typedef unsigned int size_t; typedef long long __int64; size_t* array=NULL; void initialize(size_t n, size_t k) { if (array==NULL) { array=new size_t[n+1];//make it one more } for (size_t i=0; i<n+1; i++) { array[i]=i; } } __int64 combineNumber(size_t n, size_t k) { __int64 result =1; for (size_t i=0; i<k; i++) { result=result*(n-i)/(i+1); } return result; } void displayArray(size_t* myArray, size_t start, size_t size) { cout<<"["; for (size_t i=start; i<start+size; i++) { cout<<myArray[i]; if (i!=start+size-1) { cout<<","; } } cout<<"]\n"; } void revolveUnRank(__int64 theRank, size_t n, size_t k, size_t* myArray) { __int64 last=-1, curr=-1, r=theRank; int i; size_t x=n; for (i=k; i>=1; i--) { do { last=curr; curr=combineNumber(x, i); if (curr>r) { x--; } else { break; } }while (true); if (last==r) { myArray[i-1]=x-1; } else { myArray[i-1]=x; } r=last-r-1; } } void unRankWrapper(size_t* myArray, size_t n, size_t k) { __int64 total=combineNumber(n, k); for (__int64 i=0; i<total; i++) { revolveUnRank(i,n, k, myArray); displayArray(myArray,0, k); } } void algoR(size_t*myArray, size_t n, size_t k) { size_t j; myArray[0]=0; for (j=1; j<=k; j++) { myArray[j]=j-1; } myArray[k+1]=n; R2: displayArray(myArray, 1, k); if (k%2==1) { if (myArray[1]+1<myArray[2]) { myArray[1]++; goto R2; } else { j=2; goto R4; } } else { if (myArray[1]>0) { myArray[1]--; goto R2; } else { j=2; goto R5; } } R4: if (myArray[j]>=j) { myArray[j]=myArray[j-1]; myArray[j-1]=j-2; goto R2; } else { j++; } R5: if (myArray[j]+1<myArray[j+1]) { myArray[j-1]=myArray[j]; myArray[j]++; goto R2; } else { j++; if (j<=k) { goto R4; } } } void successor(size_t* myArray, size_t n, size_t k) { size_t j; myArray[k+1]=n+1; j=1; while (j<=k&&myArray[j]==j) { j++; } if ((k-j)%2==1) //this means that k and j is NOT congruent to modulo of 2 { if (j==1) { myArray[1]--; } else { myArray[j-1]=j; myArray[j-2]=j-1; } } else { if (myArray[j+1]!=myArray[j]+1) { myArray[j-1]=myArray[j]; myArray[j]++; } else { myArray[j+1]=myArray[j]; myArray[j]=j; } } } void textbook(size_t* myArray, size_t n, size_t k) { __int64 total=combineNumber(n, k); for (__int64 i=0; i<total; i++) { displayArray(myArray, 1, k); successor(myArray, n, k); } } typedef void (* FuncType)(size_t*, size_t, size_t); FuncType funcArray[3]={unRankWrapper, algoR, textbook}; char* funcNames[3]={"unRankWrapper", "algoR", "textbook"}; void doTest(int loopNumber) { time_t start, total=0; int n, k; cout<<"please input both groundset size and subset size:\n"; cout<<"n="; cin>>n; cout<<"k="; cin>>k; for (int i=0; i<3; i++) { cout<<"now test function "<<funcNames[i]<<endl; total=0; for (int j=0; j<loopNumber; j++) { initialize(n, k); start=time(0); funcArray[i](array, n, k); total+= time(0)-start; } cout<<"total time for loop number of "<<loopNumber<<" is "<<total<<endl; } } int main() { const int LoopNumber=1; doTest(LoopNumber); return 0; }
Result:
1. post
The rank in post order of node [00000000000000000000000000001100]
is:13
The 200,000th node in post order is in binary form:
[00000000000000110000110101000110]
Press any key to continue
2. subset:
so our subset is:
[3,6,7,9]
lex rank: 555
lex successor
[3,6,7,10]
colex rank: 179
colex successor
[9,7,6,4]
revolve rank: 171
revolve successor
[2,6,7,9]
Press any key to continue
3. gensubset
please input both groundset size and subset size:
n=5
k=3
now test function unRankWrapper
[0,1,2]
[0,2,3]
[1,2,3]
[0,1,3]
[0,3,4]
[1,3,4]
[2,3,4]
[0,2,4]
[1,2,4]
[0,1,4]
total time for loop number of 1 is 0
now test function algoR
[0,1,2]
[0,2,3]
[1,2,3]
[0,1,3]
[0,3,4]
[1,3,4]
[2,3,4]
[0,2,4]
[1,2,4]
[0,1,4]
total time for loop number of 1 is 0
now test function textbook
[1,2,3]
[1,3,4]
[2,3,4]
[1,2,4]
[1,4,5]
[2,4,5]
[3,4,5]
[1,3,5]
[2,3,5]
[1,2,5]
total time for loop number of 1 is 0
Press any key to continue
please input both groundset size and subset size:
n=10 k=4 now test function unRankWrapper
[0,1,2,3]
[0,1,3,4]
[1,2,3,4]
[0,2,3,4]
[0,1,2,4]
[0,1,4,5]
[1,2,4,5]
[0,2,4,5]
[2,3,4,5]
[1,3,4,5]
[0,3,4,5]
[0,1,3,5]
[1,2,3,5]
[0,2,3,5]
[0,1,2,5]
[0,1,5,6]
[1,2,5,6]
[0,2,5,6]
[2,3,5,6]
[1,3,5,6]
[0,3,5,6]
[3,4,5,6]
[2,4,5,6]
[1,4,5,6]
[0,4,5,6]
[0,1,4,6]
[1,2,4,6]
[0,2,4,6]
[2,3,4,6]
[1,3,4,6]
[0,3,4,6]
[0,1,3,6]
[1,2,3,6]
[0,2,3,6]
[0,1,2,6]
[0,1,6,7]
[1,2,6,7]
[0,2,6,7]
[2,3,6,7]
[1,3,6,7]
[0,3,6,7]
[3,4,6,7]
[2,4,6,7]
[1,4,6,7]
[0,4,6,7]
[4,5,6,7]
[3,5,6,7]
[2,5,6,7]
[1,5,6,7]
[0,5,6,7]
[0,1,5,7]
[1,2,5,7]
[0,2,5,7]
[2,3,5,7]
[1,3,5,7]
[0,3,5,7]
[3,4,5,7]
[2,4,5,7]
[1,4,5,7]
[0,4,5,7]
[0,1,4,7]
[1,2,4,7]
[0,2,4,7]
[2,3,4,7]
[1,3,4,7]
[0,3,4,7]
[0,1,3,7]
[1,2,3,7]
[0,2,3,7]
[0,1,2,7]
[0,1,7,8]
[1,2,7,8]
[0,2,7,8]
[2,3,7,8]
[1,3,7,8]
[0,3,7,8]
[3,4,7,8]
[2,4,7,8]
[1,4,7,8]
[0,4,7,8]
[4,5,7,8]
[3,5,7,8]
[2,5,7,8]
[1,5,7,8]
[0,5,7,8]
[5,6,7,8]
[4,6,7,8]
[3,6,7,8]
[2,6,7,8]
[1,6,7,8]
[0,6,7,8]
[0,1,6,8]
[1,2,6,8]
[0,2,6,8]
[2,3,6,8]
[1,3,6,8]
[0,3,6,8]
[3,4,6,8]
[2,4,6,8]
[1,4,6,8]
[0,4,6,8]
[4,5,6,8]
[3,5,6,8]
[2,5,6,8]
[1,5,6,8]
[0,5,6,8]
[0,1,5,8]
[1,2,5,8]
[0,2,5,8]
[2,3,5,8]
[1,3,5,8]
[0,3,5,8]
[3,4,5,8]
[2,4,5,8]
[1,4,5,8]
[0,4,5,8]
[0,1,4,8]
[1,2,4,8]
[0,2,4,8]
[2,3,4,8]
[1,3,4,8]
[0,3,4,8]
[0,1,3,8]
[1,2,3,8]
[0,2,3,8]
[0,1,2,8]
[0,1,8,9]
[1,2,8,9]
[0,2,8,9]
[2,3,8,9]
[1,3,8,9]
[0,3,8,9]
[3,4,8,9]
[2,4,8,9]
[1,4,8,9]
[0,4,8,9]
[4,5,8,9]
[3,5,8,9]
[2,5,8,9]
[1,5,8,9]
[0,5,8,9]
[5,6,8,9]
[4,6,8,9]
[3,6,8,9]
[2,6,8,9]
[1,6,8,9]
[0,6,8,9]
[6,7,8,9]
[5,7,8,9]
[4,7,8,9]
[3,7,8,9]
[2,7,8,9]
[1,7,8,9]
[0,7,8,9]
[0,1,7,9]
[1,2,7,9]
[0,2,7,9]
[2,3,7,9]
[1,3,7,9]
[0,3,7,9]
[3,4,7,9]
[2,4,7,9]
[1,4,7,9]
[0,4,7,9]
[4,5,7,9]
[3,5,7,9]
[2,5,7,9]
[1,5,7,9]
[0,5,7,9]
[5,6,7,9]
[4,6,7,9]
[3,6,7,9]
[2,6,7,9]
[1,6,7,9]
[0,6,7,9]
[0,1,6,9]
[1,2,6,9]
[0,2,6,9]
[2,3,6,9]
[1,3,6,9]
[0,3,6,9]
[3,4,6,9]
[2,4,6,9]
[1,4,6,9]
[0,4,6,9]
[4,5,6,9]
[3,5,6,9]
[2,5,6,9]
[1,5,6,9]
[0,5,6,9]
[0,1,5,9]
[1,2,5,9]
[0,2,5,9]
[2,3,5,9]
[1,3,5,9]
[0,3,5,9]
[3,4,5,9]
[2,4,5,9]
[1,4,5,9]
[0,4,5,9]
[0,1,4,9]
[1,2,4,9]
[0,2,4,9]
[2,3,4,9]
[1,3,4,9]
[0,3,4,9]
[0,1,3,9]
[1,2,3,9]
[0,2,3,9]
[0,1,2,9]
total time for loop number of 1 is 0
now test function algoR
[0,1,2,3]
[0,1,3,4]
[1,2,3,4]
[0,2,3,4]
[0,1,2,4]
[0,1,4,5]
[1,2,4,5]
[0,2,4,5]
[2,3,4,5]
[1,3,4,5]
[0,3,4,5]
[0,1,3,5]
[1,2,3,5]
[0,2,3,5]
[0,1,2,5]
[0,1,5,6]
[1,2,5,6]
[0,2,5,6]
[2,3,5,6]
[1,3,5,6]
[0,3,5,6]
[3,4,5,6]
[2,4,5,6]
[1,4,5,6]
[0,4,5,6]
[0,1,4,6]
[1,2,4,6]
[0,2,4,6]
[2,3,4,6]
[1,3,4,6]
[0,3,4,6]
[0,1,3,6]
[1,2,3,6]
[0,2,3,6]
[0,1,2,6]
[0,1,6,7]
[1,2,6,7]
[0,2,6,7]
[2,3,6,7]
[1,3,6,7]
[0,3,6,7]
[3,4,6,7]
[2,4,6,7]
[1,4,6,7]
[0,4,6,7]
[4,5,6,7]
[3,5,6,7]
[2,5,6,7]
[1,5,6,7]
[0,5,6,7]
[0,1,5,7]
[1,2,5,7]
[0,2,5,7]
[2,3,5,7]
[1,3,5,7]
[0,3,5,7]
[3,4,5,7]
[2,4,5,7]
[1,4,5,7]
[0,4,5,7]
[0,1,4,7]
[1,2,4,7]
[0,2,4,7]
[2,3,4,7]
[1,3,4,7]
[0,3,4,7]
[0,1,3,7]
[1,2,3,7]
[0,2,3,7]
[0,1,2,7]
[0,1,7,8]
[1,2,7,8]
[0,2,7,8]
[2,3,7,8]
[1,3,7,8]
[0,3,7,8]
[3,4,7,8]
[2,4,7,8]
[1,4,7,8]
[0,4,7,8]
[4,5,7,8]
[3,5,7,8]
[2,5,7,8]
[1,5,7,8]
[0,5,7,8]
[5,6,7,8]
[4,6,7,8]
[3,6,7,8]
[2,6,7,8]
[1,6,7,8]
[0,6,7,8]
[0,1,6,8]
[1,2,6,8]
[0,2,6,8]
[2,3,6,8]
[1,3,6,8]
[0,3,6,8]
[3,4,6,8]
[2,4,6,8]
[1,4,6,8]
[0,4,6,8]
[4,5,6,8]
[3,5,6,8]
[2,5,6,8]
[1,5,6,8]
[0,5,6,8]
[0,1,5,8]
[1,2,5,8]
[0,2,5,8]
[2,3,5,8]
[1,3,5,8]
[0,3,5,8]
[3,4,5,8]
[2,4,5,8]
[1,4,5,8]
[0,4,5,8]
[0,1,4,8]
[1,2,4,8]
[0,2,4,8]
[2,3,4,8]
[1,3,4,8]
[0,3,4,8]
[0,1,3,8]
[1,2,3,8]
[0,2,3,8]
[0,1,2,8]
[0,1,8,9]
[1,2,8,9]
[0,2,8,9]
[2,3,8,9]
[1,3,8,9]
[0,3,8,9]
[3,4,8,9]
[2,4,8,9]
[1,4,8,9]
[0,4,8,9]
[4,5,8,9]
[3,5,8,9]
[2,5,8,9]
[1,5,8,9]
[0,5,8,9]
[5,6,8,9]
[4,6,8,9]
[3,6,8,9]
[2,6,8,9]
[1,6,8,9]
[0,6,8,9]
[6,7,8,9]
[5,7,8,9]
[4,7,8,9]
[3,7,8,9]
[2,7,8,9]
[1,7,8,9]
[0,7,8,9]
[0,1,7,9]
[1,2,7,9]
[0,2,7,9]
[2,3,7,9]
[1,3,7,9]
[0,3,7,9]
[3,4,7,9]
[2,4,7,9]
[1,4,7,9]
[0,4,7,9]
[4,5,7,9]
[3,5,7,9]
[2,5,7,9]
[1,5,7,9]
[0,5,7,9]
[5,6,7,9]
[4,6,7,9]
[3,6,7,9]
[2,6,7,9]
[1,6,7,9]
[0,6,7,9]
[0,1,6,9]
[1,2,6,9]
[0,2,6,9]
[2,3,6,9]
[1,3,6,9]
[0,3,6,9]
[3,4,6,9]
[2,4,6,9]
[1,4,6,9]
[0,4,6,9]
[4,5,6,9]
[3,5,6,9]
[2,5,6,9]
[1,5,6,9]
[0,5,6,9]
[0,1,5,9]
[1,2,5,9]
[0,2,5,9]
[2,3,5,9]
[1,3,5,9]
[0,3,5,9]
[3,4,5,9]
[2,4,5,9]
[1,4,5,9]
[0,4,5,9]
[0,1,4,9]
[1,2,4,9]
[0,2,4,9]
[2,3,4,9]
[1,3,4,9]
[0,3,4,9]
[0,1,3,9]
[1,2,3,9]
[0,2,3,9]
[0,1,2,9]
total time for loop number of 1 is 0
now test function textbook
[1,2,3,4]
[1,2,4,5]
[2,3,4,5]
[1,3,4,5]
[1,2,3,5]
[1,2,5,6]
[2,3,5,6]
[1,3,5,6]
[3,4,5,6]
[2,4,5,6]
[1,4,5,6]
[1,2,4,6]
[2,3,4,6]
[1,3,4,6]
[1,2,3,6]
[1,2,6,7]
[2,3,6,7]
[1,3,6,7]
[3,4,6,7]
[2,4,6,7]
[1,4,6,7]
[4,5,6,7]
[3,5,6,7]
[2,5,6,7]
[1,5,6,7]
[1,2,5,7]
[2,3,5,7]
[1,3,5,7]
[3,4,5,7]
[2,4,5,7]
[1,4,5,7]
[1,2,4,7]
[2,3,4,7]
[1,3,4,7]
[1,2,3,7]
[1,2,7,8]
[2,3,7,8]
[1,3,7,8]
[3,4,7,8]
[2,4,7,8]
[1,4,7,8]
[4,5,7,8]
[3,5,7,8]
[2,5,7,8]
[1,5,7,8]
[5,6,7,8]
[4,6,7,8]
[3,6,7,8]
[2,6,7,8]
[1,6,7,8]
[1,2,6,8]
[2,3,6,8]
[1,3,6,8]
[3,4,6,8]
[2,4,6,8]
[1,4,6,8]
[4,5,6,8]
[3,5,6,8]
[2,5,6,8]
[1,5,6,8]
[1,2,5,8]
[2,3,5,8]
[1,3,5,8]
[3,4,5,8]
[2,4,5,8]
[1,4,5,8]
[1,2,4,8]
[2,3,4,8]
[1,3,4,8]
[1,2,3,8]
[1,2,8,9]
[2,3,8,9]
[1,3,8,9]
[3,4,8,9]
[2,4,8,9]
[1,4,8,9]
[4,5,8,9]
[3,5,8,9]
[2,5,8,9]
[1,5,8,9]
[5,6,8,9]
[4,6,8,9]
[3,6,8,9]
[2,6,8,9]
[1,6,8,9]
[6,7,8,9]
[5,7,8,9]
[4,7,8,9]
[3,7,8,9]
[2,7,8,9]
[1,7,8,9]
[1,2,7,9]
[2,3,7,9]
[1,3,7,9]
[3,4,7,9]
[2,4,7,9]
[1,4,7,9]
[4,5,7,9]
[3,5,7,9]
[2,5,7,9]
[1,5,7,9]
[5,6,7,9]
[4,6,7,9]
[3,6,7,9]
[2,6,7,9]
[1,6,7,9]
[1,2,6,9]
[2,3,6,9]
[1,3,6,9]
[3,4,6,9]
[2,4,6,9]
[1,4,6,9]
[4,5,6,9]
[3,5,6,9]
[2,5,6,9]
[1,5,6,9]
[1,2,5,9]
[2,3,5,9]
[1,3,5,9]
[3,4,5,9]
[2,4,5,9]
[1,4,5,9]
[1,2,4,9]
[2,3,4,9]
[1,3,4,9]
[1,2,3,9]
[1,2,9,10]
[2,3,9,10]
[1,3,9,10]
[3,4,9,10]
[2,4,9,10]
[1,4,9,10]
[4,5,9,10]
[3,5,9,10]
[2,5,9,10]
[1,5,9,10]
[5,6,9,10]
[4,6,9,10]
[3,6,9,10]
[2,6,9,10]
[1,6,9,10]
[6,7,9,10]
[5,7,9,10]
[4,7,9,10]
[3,7,9,10]
[2,7,9,10]
[1,7,9,10]
[7,8,9,10]
[6,8,9,10]
[5,8,9,10]
[4,8,9,10]
[3,8,9,10]
[2,8,9,10]
[1,8,9,10]
[1,2,8,10]
[2,3,8,10]
[1,3,8,10]
[3,4,8,10]
[2,4,8,10]
[1,4,8,10]
[4,5,8,10]
[3,5,8,10]
[2,5,8,10]
[1,5,8,10]
[5,6,8,10]
[4,6,8,10]
[3,6,8,10]
[2,6,8,10]
[1,6,8,10]
[6,7,8,10]
[5,7,8,10]
[4,7,8,10]
[3,7,8,10]
[2,7,8,10]
[1,7,8,10]
[1,2,7,10]
[2,3,7,10]
[1,3,7,10]
[3,4,7,10]
[2,4,7,10]
[1,4,7,10]
[4,5,7,10]
[3,5,7,10]
[2,5,7,10]
[1,5,7,10]
[5,6,7,10]
[4,6,7,10]
[3,6,7,10]
[2,6,7,10]
[1,6,7,10]
[1,2,6,10]
[2,3,6,10]
[1,3,6,10]
[3,4,6,10]
[2,4,6,10]
[1,4,6,10]
[4,5,6,10]
[3,5,6,10]
[2,5,6,10]
[1,5,6,10]
[1,2,5,10]
[2,3,5,10]
[1,3,5,10]
[3,4,5,10]
[2,4,5,10]
[1,4,5,10]
[1,2,4,10]
[2,3,4,10]
[1,3,4,10]
[1,2,3,10]
total time for loop number of 1 is 0