combinatorial algorithm programs

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.

    B.The problem

    1) post-order-rank

1. (5 marks total) Consider Question 19 on page 27 of Knuth¡¯s Fascicle 3A.
(a) (1 mark) Does Knuth start counting his nodes from 0 or does he start counting
from 1? Why?
(b) (1 mark) In this question, Knuth uses the term postorder. How would a postorder
traversal of this tree be defined?
(c) (1 mark) Given your answers to (a) and (b), what is the ¡°rank¡± of the node
labelled 1100.
(d) (2 marks) What is the 200,000-th node visited in postorder?
Hint: Read Knuth¡¯s solution to his Question 19 on page 39.
¡¡
¡¡
This question is not what it seems to be trivial. It cost me some time to realize my mistakes. When you are given a node in
binary form or 1100, you are expected to get its rank in post order because the binary integer is the rank of its preorder.
However, Knuth's solution is not completely correct in the sense that there is a couple of base case to handle. See below:
¡¡
It is post(1000000), where post(n)=pow(2,k)+post(n-pow(2,k)+1) if n>=pow(2,k)&&n<pow(2,k+1) and post(0)=0. So,
post(1000000)=11110100001001000100
¡¡
My professor and classmates and I myself all discovered that there are some cases that makes the recursion infinite loop.
And how do you find each "k"? By a loop? That is what I thought and probably what you are thinking about. However, there is
clever method discovered by my classmate. See below the "post". Hint: using binary knowledge of integer.
¡¡
2) subset rank and successor
¡¡
What is the rank of {3,6,7,9} considered as a 4-subset of {0,1,2,...12} in lexicographic, co-lex, and revolving door order? What is its successor in each of these orders?
¡¡
Is this question trivial?
I don't quite think so in the sense that when I program to solve them, the annoying thing is that both textbook, Knuth and I cannot agree on what position the index array starts and what number the value of index array starts.
The textbook follows usual pseudocode style that array starts by number 1 at position 1 instead of 0. I insist on c/c++ style that array starts at position 0 with number 0. While Knuth makes a compromise by starting at position 1 with number 0.
Then the question is can you combine three algorithm together because we have a common input data [3,6,7,9]. And I haven't
mentioned that for co-lex, the input array must be reversed. So, this is a quite simple question with complicated setup.
See my awkward solution below of "subset".
¡¡
3) subset generation
¡¡
question: Write a program to generate combinations in the revolving door order.
Provide printouts to demonstrate that your program is working.
¡¡
Is this a hard question? This question has almost exact problem like subset rank and successor that I kept messed with them.
See my awkward solution of "gensubset".
¡¡
C.The idea of program
¡¡

    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.

    D.The major functions

    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