Minimal Weight (MPI Improved)
A. Fourth Edition
This is the programming assignment of comp6661 and we are requested to use "revolving door algorithm" to find minimal
weight for an error-correcting-code. I struggled for a whole day and finally finished as planned even though a little bit
more time than expected. And after I found out that my MPI first version ran for more than a whole day, I began to do a
testing to compare efficiency between "unrank" and "successor". Quite to my surprise, "unrank" is almost 200 times slower
than "successor" function. This made me finally decide to implement my MPI in "successor" manner.
1. Using revolve-door unrank function in textbook to generate index array for
subset combination. So, we can generate arbitary subset by
given its rank. This is used for partition our searching job. This method is comparatively a bit slow
than other "successor" function. (And this is only
my original estimation. After I made a program to compare the three algorithm I
found out that "unrank" is extremely slow, about 200 times slower than
"successor".
2. Improved on basis of first version so that two consecutive subset combination
don't need calculate repeated xor. Instead
I compare the difference in two subsets and use previous result to xor with two
changed vector. In order to keep both
current and previous subset combination, I use two integer array, oldArray and
newArray.
instead of using a pointer to point to them alternatively
in my previous version, I
have to backup newArray into oldArray because Knuth's "successor" is depending
on previous results and modifies them directly.
3. Based on second version and use MPI to distribute computation to other nodes.
My idea is straight forward. If we can
start any computation by giving a rank, then we can divide the total computation
job with different range of rank. That's
why I implement my algorithm by using "unrank" function.
4. Root node read from data file and broadcast n,k,d and vector to all other
nodes.
5. Then all slave nodes start computation by iterate all subset size from 1 to
k. And each node knows its part of range
because of its MPI_Rank. For example, for n=32,k=16,d=7 the total number of
combination of subset 5 is (16,5)=11440. If
MPI_Size=9 which means 8 slave nodes, then each node will be given a range of
11440/8 and they don't need further instruction
from root node and can start working as soon as they receive all setup
information.
5. I choose to let root node be specializing in listening to simplify
programming because we don't know when and which node
will report discovery. So, we have to use non-blocking "recv" method in MPI. If
I give computation job to root node, I have
to use multi-thread for listening which is too complicated and has only
suspicious performance gain. Therefore, the root
node will "post" a recieve request to all slave nodes and then "test" requests
in a loop. The slave nodes will first answer
"yes" or "no" to discovery. If "yes", it will send combination of vector which
has smaller weight than d seperately. If "no",
no further informatio is sent. By counting "no" replies or receiving "yes"
reply, root node can decide if we find or not.
6. Originally I write my program in windows and in order to run and test in Linux,
I have to change some data type. For example,
in windows, "size_t" is one of primitive type while in Linux, I have to typedef
it to "unsigned int". And in windows, I am
using VC++ special type __int64 which is 64 bit integer while in Linux, I have
to type define it to "long long". So, if you need to run them in windows, comment out those typedef's in "myset.h".
In both text book and Knuth's notes, there are generating algorithms for subset of order of minimal change. However, I
choose unusual "unrank" function to implement it which is not efficient. There is another simple reason apart from that MPI
mentioned above. It is the only thing I can work out!. I even tried both algorithms and repeatedly got error. Then I suspected
both of them. And time is ticking. I only got one whole day for this program because I must leave some time for theory and
possible testing, documenting. So, I have to give it up. And you can find the commented Knuth's code. Efficient and
terrible with no offence. You see, his style is typical assembly language like and I both envy and hate.
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
Minimal weight searching. (don't be confused by two main file, one is for MPI, the other is just
usual main. They should be compiled seperately.)
1. mpi.cpp (main for MPI, compiled by make mpi)
2. main.cpp (main for local single node, compiled by make myset)
3. myset.h
4. myset.cpp
5. revolve.h
6. revolve.cpp
7. makefile
to compile:
mpic++ mpi.cpp myset.cpp revolve.cpp -o mpimyset.exe
to run:
>time mpirun -np 9 mpimyset.exe test5.txt >result5.txt &
And here is the data file you need to feed when running
file name: mpi.cpp
#include "myset.h" #include "revolve.h" #include <iostream> #include <mpi.h> #include <time.h> using namespace std; extern size_t n, k, d; extern size_t* buffer; extern MySet* sets; extern MySet current; extern size_t bufferSize; extern size_t* c;//the pointer int mpi_rank, mpi_size; int hasSmaller=0; size_t context[3]; //n,k,d int main(int argc, char* argv[]) { time_t start; MPI_Init(&argc, &argv); /* Initialize MPI */ MPI_Comm_rank(MPI_COMM_WORLD, &mpi_rank); /* Get my rank */ MPI_Comm_size(MPI_COMM_WORLD, &mpi_size); if (mpi_rank==0) { start=time(0); int i, counter=0; int* flags=new int[mpi_size-1]; int *results=new int[mpi_size-1]; MPI_Status status; MPI_Request* requests=new MPI_Request[mpi_size-1]; if (argc<2) { cout<<"usage: myset.exe filename\n"; MPI_Finalize(); return 1; } readFromFile(argv[1]); initialize(n, k, d, buffer); context[0]=n; context[1]=k; context[2]=d; MPI_Bcast(context, 3, MPI_INT, 0, MPI_COMM_WORLD); MPI_Bcast(buffer, bufferSize, MPI_INT, 0, MPI_COMM_WORLD); for (i=1; i<mpi_size; i++) { flags[i-1]=0; MPI_Irecv(results+i-1, 1, MPI_INT, i, 0, MPI_COMM_WORLD, requests+ i-1); } while (counter<mpi_size-1&&!hasSmaller) { for (i=1; i<mpi_size; i++) { if (!flags[i-1]) { MPI_Test(requests+i-1, flags+i-1, &status); if (flags[i-1]) { counter++; if (results[i-1]) { //means we find smaller than d hasSmaller=results[i-1]; cout<<"has smaller weight found in node "<<i<<endl; int* dataBuf=new int[k]; MPI_Recv(dataBuf, results[i-1], MPI_INT, i, 0, MPI_COMM_WORLD, &status); for (int j=0; j<results[i-1]; j++) { cout<<dataBuf[j]<<","; } cout<<" is the linear combination\n"; break; } } } } if (counter==mpi_size-1) { cout<<"no small weight found in any node\n"; break; } } } else { long long start, total, mySize; int size; size_t subset; MPI_Bcast(context, 3, MPI_INT, 0, MPI_COMM_WORLD); n=context[0]; k=context[1]; d=context[2]; size=n/32; if (n%32!=0) { size++; } bufferSize=size*k; buffer=new size_t[bufferSize]; MPI_Bcast(buffer, bufferSize, MPI_INT, 0, MPI_COMM_WORLD); initialize(n,k,d, buffer); for(subset=1; subset<=k;subset++) { total=combineNumber(k, subset); mySize= total/(mpi_size-1); start=mySize*(mpi_rank-1); //if I am the last one, I have to take care all of rest part if (mpi_rank==mpi_size-1) { mySize=total-mySize*(mpi_size-2); } if (!weightTest(start, mySize, subset)) { hasSmaller=subset;//true break; } } MPI_Send(&hasSmaller, 1, MPI_INT, 0, 0, MPI_COMM_WORLD); if (hasSmaller) { MPI_Send(c, hasSmaller, MPI_INT, 0, 0, MPI_COMM_WORLD); } } if (mpi_rank==0) { cout<<"the total time in seconds is "<<time(0)-start<<endl; } MPI_Finalize(); return 0; }
file name: myset.h
#ifndef MYSET_H #define MYSET_H typedef unsigned char HashTableType; typedef long long __int64; typedef unsigned int size_t; const size_t DefaultGroundSetSize=32;//4*8=32 const size_t DigitBitCount=sizeof(size_t)*8;//one byte const size_t DefaultBitState=0; const size_t HashTableSize=256; const size_t DeleteMask=0xFFFFFFFF; const size_t ComplementMask=DeleteMask; const size_t SetOrderMask=0xFF; const size_t SetOrderMaskCount=sizeof(size_t)/sizeof(HashTableType); const size_t MaxGroundSetSize=1024; const size_t MaxDigitCount=MaxGroundSetSize/8/sizeof(size_t); size_t fact(size_t size); size_t combine(size_t n, size_t k); class MySet { public: //constructor MySet(size_t size=DefaultGroundSetSize); ~MySet(); //copy constructor MySet(const MySet& copy); //basic set operations //unary operations bool MemberOfSet(size_t index) const; void SetInsert(size_t index); void SetDelete(size_t index); size_t SetOrder(); MySet Complement(); //binary operations MySet Union(const MySet& other); MySet Intersection(const MySet& other); MySet Difference(const MySet& other); //operator overloading //set assignment MySet& operator=(const MySet& other); MySet& operator=(const size_t* array); //xor operation MySet& operator^(const MySet& other); bool operator==(const MySet& other); bool operator[](size_t index); //utility operations void display() const; void initialize(size_t size); void randomSet(); size_t getSize(){ return groundSetSize;} void flip(size_t index); void createByArray(size_t array[], size_t arraySize); //special set utility operations size_t LexRank(); void LexUnrank(size_t number); //subset utility //lexico size_t SubsetLexRank(size_t subsetSize); void SubsetLexUnRank(size_t subsetSize, size_t rank); void SubsetLexSuccessor(size_t subsetSize); //colex void SubsetColexSuccessor(size_t subsetSize); int getDigitCount()const {return digitCount;} protected: static HashTableType hashTable[HashTableSize]; static bool need2hash; int groundSetSize; size_t digitCount; size_t* digits; //int lastDigitSize; void initHashTable(); void checkSize(size_t index)const; void checkSize(const MySet& other) const; void setSize(size_t size);//this should not be called by user!!!! try initialize(i); void clear(); }; #endif
file name: myset.cpp
#include "myset.h" #include <iostream> //typedef int* set ; using namespace std; //pure for testing long lastResult; HashTableType MySet::hashTable[256]; bool MySet::need2hash=true; MySet::MySet(size_t size) { groundSetSize=0; initialize(size); //because we only need to initialize hash table once for all set objects if (need2hash) { initHashTable(); need2hash=false; } } MySet::~MySet() { delete[]digits; } //a copy constructor MySet::MySet(const MySet& copy) { //set groundsetsize to 0 to indicate this is the first time creating set groundSetSize=0; initialize(copy.groundSetSize); for (size_t i=0; i<digitCount; i++) { digits[i]=copy.digits[i]; } } void MySet::initHashTable() { size_t i, j; //int lowIndex=0, highIndex=1; //initialize half byte first hashTable[0]=0; hashTable[1]=1; hashTable[2]=1; hashTable[3]=2; hashTable[4]=1; hashTable[5]=2; hashTable[6]=2; hashTable[7]=3; for (i=0; i<8; i++) { hashTable[8+i]=hashTable[i]+1; } //initialize one byte and use it as a pattern in following for (i=1; i<16; i++) { for (j=0; j<16; j++) { hashTable[i*16+j]=hashTable[i]+hashTable[j]; } } } void MySet::display() const { cout<<"\n["; for (int i=0; i<groundSetSize; i++) { if (MemberOfSet(i)) { cout<<"1"; } else { cout<<"0"; } } cout<<"]\n"; } void MySet::checkSize(size_t index) const { if (index>=groundSetSize) { cout<<"error exceeding boundary"; exit(1); } } //difference=A intersection complement(B) MySet MySet::Difference(const MySet& other) { checkSize(other); MySet result=other; result.Complement(); return Intersection(result); } MySet MySet::Complement() { for (size_t i=0; i<digitCount; i++) { digits[i] ^= ComplementMask; } return *this; } //element starts from 1 instead of 0 bool MySet::MemberOfSet(size_t index) const { size_t i,j; checkSize(index); i=index/DigitBitCount; j=index%DigitBitCount; return (digits[i]>>j)&1==1; } //assume element is starting from 1 instead of 0 void MySet::SetInsert(size_t index) { size_t i,j; checkSize(index); i=index/DigitBitCount; j=index%DigitBitCount; digits[i]|=(((size_t)1)<<j); } //assume element starts from 1 instead of 0 void MySet::SetDelete(size_t index) { size_t i,j; size_t mask=DeleteMask; checkSize(index); i=index/DigitBitCount; j=index%DigitBitCount; mask^=(1<<j); digits[i]&=mask; } void MySet::checkSize(const MySet& other) const { if (groundSetSize!=other.groundSetSize) { cout<<"two set has different ground set size!\n"; exit(1); } } //return value instead of dynamic new memory MySet MySet::Union(const MySet& other) { checkSize(other); //choose the bigger groundsetsize of two MySet result(groundSetSize); for (size_t i=0; i<digitCount; i++) { result.digits[i]=digits[i] | other.digits[i]; } return result; } //set assignment maybe use set variable with old data MySet& MySet::operator =(const MySet& other) { //initialize(other.groundSetSize); for (size_t i=0; i<digitCount; i++) { digits[i]=other.digits[i]; } return *this; } MySet& MySet::operator =(const size_t* array) { for (size_t i=0; i<digitCount; i++) { digits[i]=array[i]; } return *this; } MySet& MySet::operator ^(const MySet& other) { for (size_t i=0; i<digitCount; i++) { digits[i]^=other.digits[i]; } return *this; } //set is equal only when the ground set size is equal and all element equal bool MySet::operator ==(const MySet& other) { if (groundSetSize!=other.groundSetSize) { return false; } for (size_t i=0; i<digitCount; i++) { if (digits[i]!=other.digits[i]) { return false; } } return true; } //set intersection MySet MySet::Intersection(const MySet& other) { checkSize(other); MySet result(groundSetSize); for (size_t i=0; i<digitCount; i++) { result.digits[i]=digits[i]&other.digits[i]; } return result; } size_t MySet::SetOrder() { size_t result=0; size_t index; for (size_t i=0; i<digitCount; i++) { for (size_t j=0; j<SetOrderMaskCount; j++) { index=(digits[i]>>(j*8))&SetOrderMask; result+=hashTable[index]; } } return result; } void MySet::flip(size_t index) { size_t i,j; checkSize(index); i=index/DigitBitCount; j=index%DigitBitCount; digits[i]^=((size_t)1<<j); } void MySet::setSize(size_t size) { groundSetSize=size; //DigitBitCount=ByteSize=8 digitCount=groundSetSize/DigitBitCount; //last digit size is stored so that calculation will only be //done once for all //if modulo 8==0, we don't need extra digit if (groundSetSize%DigitBitCount!=0) { digitCount++; } } void MySet::initialize(size_t size) { //DefaultBitState is 0 for unset; if (size>0) { if (groundSetSize>=size) { //we don't have to reallocate memory setSize(size); } else { if (groundSetSize!=0) { delete[]digits; } setSize(size); digits= new size_t[digitCount]; if (digits==NULL) { cout<<"unable allocate memory for ground set size of "<<groundSetSize<<endl; exit(1); } } //memset(digits, DefaultBitState, digitCount); for (size_t i=0; i<digitCount; i++) { digits[i]=0; } //memset(digits, 0, digitCount); } else { groundSetSize=digitCount=0; digits=NULL; } } //colex void MySet::SubsetColexSuccessor(size_t subsetSize) { size_t result=0, i,j; size_t* array; if (SetOrder()!=subsetSize) { cout<<"subset size is not what it should be!\n"; exit(1); } //first create an index array array=new size_t[subsetSize+1]; array[0]=0; j=0; //translate into index array for (i=groundSetSize; i>=1; i--) { if (MemberOfSet(i-1)) { array[j+1]=i; j++; } } i=1; while (i<=subsetSize&&array[i]==groundSetSize-i+1) { i++; } if (i==subsetSize+1) { cout<<"undefined"; } else { result=array[i]; for (j=i; j<=subsetSize; j++) { array[j]=result+1-(j-i); } j=subsetSize; for (i=0; i<groundSetSize; i++) { if (i+1==array[j]) { SetInsert(i); j--; } else { SetDelete(i); } } } delete[]array; } //this is limited within groundset size of 32 or less //the order is lexicographic order void MySet::SubsetLexUnRank(size_t subsetSize, size_t rank) { size_t x=1, temp; if (subsetSize>groundSetSize) { cout<<"wrong subset size!\n"; exit(1); } clear(); for (size_t i=1; i<=subsetSize; i++) { temp=combine(groundSetSize-x, subsetSize-i); while (temp<=rank) { rank-=temp; x++; temp=combine(groundSetSize-x, subsetSize-i); } SetInsert(x-1); x++; } } //this is limited within groundset size of 32 or less //the order is lexicographic order void MySet::SubsetLexSuccessor(size_t subsetSize) { size_t result=0, i,j; size_t* array; if (SetOrder()!=subsetSize) { cout<<"subset size is not what it should be!\n"; exit(1); } //first create an index array array=new size_t[subsetSize+1]; array[0]=0; j=0; //translate into index array for (i=0; i<groundSetSize; i++) { if (MemberOfSet(i)) { array[j+1]=i+1; j++; } } i=subsetSize; while (i>=1&&array[i]==(groundSetSize-subsetSize+i)) { i--; } if (i==0) { cout<<"undefined"; } else { result=array[i]; for (j=i; j<=subsetSize; j++) { array[j]=result+1+j-i; } j=1; for (i=0; i<groundSetSize; i++) { if (i+1==array[j]) { SetInsert(i); j++; } else { SetDelete(i); } } } delete[]array; } //this is limited within groundset size of 32 or less //the order is lexicographic order size_t MySet::SubsetLexRank(size_t subsetSize) { size_t result=0, i,j; size_t* array; if (SetOrder()!=subsetSize) { cout<<"subset size is not what it should be!\n"; exit(1); } //first create an index array array=new size_t[subsetSize+1]; array[0]=0; j=0; //translate into index array for (i=0; i<groundSetSize; i++) { if (MemberOfSet(i)) { array[j+1]=i+1; j++; } } for (i=1; i<=subsetSize; i++) { if (array[i-1]+1<array[i]) { for (j=array[i-1]+1; j<array[i]; j++) { result+=combine(groundSetSize-j, subsetSize-i); } } } delete []array; return result; } void MySet::createByArray(size_t array[], size_t arraySize) { //let's have a simple groundsetsize as for initialize(arraySize*sizeof(size_t)*8); for (size_t i=0; i<digitCount; i++) { digits[i]=array[i]; } } //I would leave big number problem to future size_t MySet::LexRank() { //temporarily I would assume there is only a small set return digits[0]; } //I would wait for future for big ground set problem void MySet::LexUnrank(size_t number) { initialize(sizeof(size_t)*8); digits[0]=number; } void MySet::randomSet() { for (size_t i=0; i<digitCount; i++) { digits[i]=rand(); } } bool MySet::operator [](size_t index) { return MemberOfSet(index); } void MySet::clear() { size_t mask=0; for (size_t i=0; i<digitCount; i++) { digits[i]=mask; } } size_t fact(size_t size) { size_t result=1; for (int i=2; i<=size; i++) { result*=i; } return result; } size_t combine(size_t n, size_t k) { size_t result=1; if (n<k) { cout<<"combine number is wrong!\n"; exit(1); } for (int i=0; i<k; i++) { result*=(n-i); } return result/fact(k); }
file name: revolve.h
#include <iostream> #include "myset.h" using namespace std; void displayArray(size_t* array, size_t start, size_t size); void revolveUnRank(long theRank, size_t subSize, size_t* array); void readFromFile(char* fileName); bool weightTest(__int64 startRank, __int64 count, int subSize); void initialize(size_t theN, size_t theK, size_t theD, size_t* array); __int64 combineNumber(size_t n, size_t k); void algoR(size_t k, size_t* array);
file name: revolve.cpp
#include "revolve.h" #include "myset.h" #include <iostream> #include <fstream> using namespace std; size_t groundsetSize, subsetSize; size_t n, k, d; size_t* buffer; size_t bufferSize; MySet* sets; MySet current; size_t* oldArray=NULL; size_t* newArray=NULL; size_t* c; __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 revolveUnRank(__int64 theRank, size_t subSize, size_t* c) { __int64 last=-1, curr=-1, r=theRank; int i; size_t x=groundsetSize; subsetSize=subSize; for (i=subsetSize; i>=1; i--) { do { last=curr; curr=combineNumber(x, i); if (curr>r) { x--; } else { break; } }while (true); if (last==r) { c[i]=x-1; } else { c[i]=x; } r=last-r-1; } } int findSmallest(int& oldIndex, int& newIndex) { while (oldIndex<=subsetSize&&newIndex<=subsetSize) { if (oldArray[oldIndex]==newArray[newIndex]) { oldIndex++; newIndex++; } else { if (oldArray[oldIndex]<newArray[newIndex]) { //must make easy for next return oldArray[oldIndex++]; } else { return newArray[newIndex++]; } } } if (oldIndex==newIndex&&oldIndex==subsetSize+2) { cout<<"find smallest failed, check array!\n"; exit(1); } else { if (oldIndex<newIndex) { return oldArray[oldIndex]; } else { return newArray[newIndex]; } } } void displayArray(size_t* array, size_t start, size_t size) { cout<<"["; for (size_t i=start; i<size; i++) { cout<<array[i]; if (i!=start+size-1) { cout<<","; } } cout<<"]\n"; } void findChangedVectorIndex(int& first, int& second) { int oldIndex=1, newIndex=1; first=findSmallest(oldIndex, newIndex); second=findSmallest(oldIndex, newIndex); } bool weightTest(__int64 startRank, __int64 count, int subSize) { subsetSize=subSize; int left, right; for (__int64 i=0; i<count; i++) { //I cannot use two arrays to alternatively, it is too complicated for (int j=0; j<subSize+1; j++) { oldArray[j]=newArray[j]; } //for the first time, we need this to initialize if (i==0) { revolveUnRank(startRank+i, subSize, newArray); //displayArray(newArray, 1, subSize); } else { algoR(subSize, newArray); //displayArray(newArray, 1, subSize); } if (i==0) { //things become more complicated because unrank starts from index 1 current=sets[newArray[1]]; for (int j=2; j<subSize+1; j++) { current^(sets[newArray[j]]); } } else { findChangedVectorIndex(left, right);//not the index of array current^(sets[left]); current^(sets[right]); } if (current.SetOrder()<d) { /* cout<<"this means we find the combination with weight smaller than d:\n"; for (int m=1; m<subSize+1; m++) { cout<<newArray[m]<<","; } */ return false; } } return true; } void initialize(size_t theN, size_t theK, size_t theD, size_t* array) { groundsetSize=theK; n=theN; k=theK; d=theD; sets=new MySet[k]; for (int i=0; i<k; i++) { sets[i].initialize(n); //this may seem to be odd, I overload the operator= for size_t* to copy array sets[i]=array+(i*sets[i].getDigitCount()); } current.initialize(n); oldArray=new size_t[n+1]; newArray=new size_t[n+1]; } void readFromFile(char* fileName) { //size_t* array; size_t temp, size, mask=1; int i, j; int number; ifstream in(fileName); in>>n; in>>k; in>>d; size=n/32; if (n%32!=0) { size++; } bufferSize=size*k; buffer=new size_t[bufferSize]; for (i=0; i<k; i++) { number=-1;//the number of int for (j=0; j<n; j++) { if (j%32==0) { number++; buffer[i*size+number]=0; } in>>temp; if (temp!=0) { buffer[i*size+number] |= (mask<<j); } } } } void algoR(size_t t, size_t* c) { size_t j; if (t%2==1) { if (c[1]+1<c[2]) { c[1]++; return; //goto R2; } else { j=2; goto R4; } } else { if (c[1]>0) { c[1]--; return; //goto R2; } else { j=2; goto R5; } } R4: if (c[j]>=j) { c[j]=c[j-1]; c[j-1]=j-2; return; //goto R2; } else { j++; } R5: if (c[j]+1<c[j+1]) { c[j-1]=c[j]; c[j]++; return; //goto R2; } else { j++; if (j<=t) { goto R4; } } } file name: makefile myset : main.cpp myset.cpp myset.h revolve.cpp revolve.h g++ -g main.cpp myset.cpp revolve.cpp -o myset.exe mpi : mpi.cpp myset.cpp myset.h revolve.cpp revolve.h mpic++ main.cpp myset.cpp revolve.cpp -o mpimyset.exe
1. test0.txt
2. test1.txt
3. test2.txt
4. test3.txt
5. test4.txt
6. test5.txt
Result:
result0.txt to result4.txt are all run by local program which is very fast. Currently I can only
finish MPI version running for case 5 which takes 22945 seconds. And then I decide to run both
case 6 and case 7 on "breca" and it is expected to run for very long because the complexity of
case 6 is almost ten times bigger than case 5. And case 7 is more than six thousand times bigger.
file name: test0.txt
7 4 4 1 0 0 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 0 0 1 1 1 1
file name: test1.txt 23 12 8 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 1 1 0 0 0
file name: test2.txt
24 12 8 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 1 1 0 0 0 1
file name: test3.txt
32 16 7 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 1 1 1 0 1 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 0 0 1 1
file name: test4.txt
48 24 12 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 1 1 0 0 0 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 1 1 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 1 1 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 0 1 1 1 1 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 1 0 0 1 1 1 0 1 0 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1 0 1 1 0 0 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1 0 1 1 0 0 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1 0 1 1 0 0 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 1 1 0 0 0 1 1 0 0 0 1 1
file name: test5.txt
72 36 12 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 0 0 1 0 1 0 1 0 1 0 0 0 0 1 1 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 0 0 1 0 1 0 1 0 1 0 0 0 0 1 1 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 0 0 1 0 1 0 0 1 1 0 0 1 0 0 1 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 0 0 1 0 1 0 0 1 1 0 0 1 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 1 1 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 1 1 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 1 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 1 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 1 1 1 0 1 1 1 0 0 0 0 1 0 1 1 1 0 1 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 1
(There are originally more test cases but I haven't even finished running test5!)
A snapshot of running automated testing:
[testing result] 1. The following is running result of those simple test cases. The data file "test*.txt" is ordered by course website except that "test0.txt" is hamming code with d=4 for testing. 2. All following test cases finishes very soon. Even the test4.txt D:\Program Files\Microsoft Visual Studio\MyProjects\MySet\Debug>myset test0.txt [1000110] [0100101] [0010011] [0001111] now try subset of 1 we find a weight smaller than d=4with such combination: 0,current is: [1000110] this means we cannot find a weight smaller than d=4 D:\Program Files\Microsoft Visual Studio\MyProjects\MySet\Debug>myset test1.txt [10000000000001111111111] [01000000000011101110001] [00100000000011011100010] [00010000000010111000101] [00001000000011110001011] [00000100000011100010110] [00000010000011000101101] [00000001000010001011011] [00000000100010010110111] [00000000010010101101110] [00000000001011011011100] [00000000000110110111000] now try subset of 1 we find a weight smaller than d=8with such combination: 2,current is: [00100000000011011100010] D:\Program Files\Microsoft Visual Studio\MyProjects\MySet\Debug>myset test3.txt [10000000000000001110001100001001] [01000000000000000111000110000101] [00100000000000000011100011000011] [00010000000000001111111101101000] [00001000000000000111111110110100] [00000100000000000011111111011010] [00000010000000001111110011100101] [00000001000000000111111001110011] [00000000100000001101110000110000] [00000000010000000110111000011000] [00000000001000000011011100001100] [00000000000100000001101110000110] [00000000000010001110111011001011] [00000000000001001001010001101100] [00000000000000100100101000110110] [00000000000000011100011000010011] now try subset of 1 now try subset of 2 now try subset of 3 now try subset of 4 now try subset of 5 now try subset of 6 now try subset of 7 now try subset of 8 now try subset of 9 now try subset of 10 now try subset of 11 now try subset of 12 now try subset of 13 now try subset of 14 now try subset of 15 now try subset of 16 this means we cannot find a weight smaller than d=7 D:\Program Files\Microsoft Visual Studio\MyProjects\MySet\Debug> D:\Program Files\Microsoft Visual Studio\MyProjects\MySet\Debug>myset test4.txt [100000000000000000000000111101110110111000110001] [010000000000000000000000011110111011011100011001] [001000000000000000000000001111011101101110001101] [000100000000000000000000000111101110110111000111] [000010000000000000000000111110000001100011010010] [000001000000000000000000100010110110001001011001] [000000100000000000000000010001011011000100101101] [000000010000000000000000001000101101100010010111] [000000001000000000000000111001100000001001111010] [000000000100000000000000100001000110111100001101] [000000000010000000000000010000100011011110000111] [000000000001000000000000110101100111010111110010] [000000000000100000000000100111000101010011001001] [000000000000010000000000010011100010101001100101] [000000000000001000000000001001110001010100110011] [000000000000000100000000111001001110010010101000] [000000000000000010000000011100100111001001010100] [000000000000000001000000001110010011100100101010] [000000000000000000100000111010111111001010100101] [000000000000000000010000011101011111100101010011] [000000000000000000001000110011011001001010011000] [000000000000000000000100011001101100100101001100] [000000000000000000000010001100110110010010100110] [000000000000000000000001111011101101110001100011] now try subset of 1 now try subset of 2 now try subset of 3 now try subset of 4 now try subset of 5 now try subset of 6 now try subset of 7 now try subset of 8 now try subset of 9 now try subset of 10 now try subset of 11 now try subset of 12 now try subset of 13 now try subset of 14 now try subset of 15 now try subset of 16 now try subset of 17 now try subset of 18 now try subset of 19 now try subset of 20 now try subset of 21 now try subset of 22 now try subset of 23 now try subset of 24 this means we cannot find a weight smaller than d=12 D:\Program Files\Microsoft Visual Studio\MyProjects\MySet\Debug>