MPI etc

Minimal Weight

A. First(Second, Third) 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.

B.The problem

3. (9 marks total)
(a) (5 marks) Write a program to generate combinations in the revolving door order.
Provide printouts to demonstrate that your program is working.
(b) (4 marks) Next, you use the combinations generated in part (a) in an application
involving error-correcting codes.
A (n, k) binary linear error correcting code is a k-dimensional vector space of
length n over the finite field with 2 elements, namely, 0 and 1. Given a basis,
which is a set of k linearly independent vectors r1, r2, . . . , rn, all the vectors in
the vector space can be expressed as a linear combinations
　

for (i=1 to n) summation(ci * ri)

where the coefficients ci’s are in {0, 1}.
A generator matrix G, where row i is the vector ri, is a convenient way of representing
a basis. A linear combination with coefficents ci’s is just an xor of the
subset of rows ri where the corresponding coefficient ci = 1.
For simplicity, we shall shorten the term binary linear error-correcting code to
just code. The vectors in such a code are usually called codewords or even words.
1
The weight of a word is the number of 1’s in the word. The minimum weight of
a code is the minimum weight of its non-zero codewords. The minimum weight
of a code is important because it determines the number of errors that the code
can correct.
You will be using the combination generation you developed in part (a) to find the
minimum weight of a code, in the special case where the leftmost k×k submatrix
of the generator matrix is an identity matrix. If the generator matrix is in this
form, you can show that the minimum weight is d by showing that there exists
a linear combination with weight d, and that all the linear combinations defined
by the r-subsets of rows, with r d, have weights at least d.
For this part of the program, you should use the bit array data structure you
developed in assignment 1 to represent the rows of the generator matrix. You
should also use the setorder routine to find the weight of a word.
You should use the (7, 4) Hamming code to debug your program. A few test cases
will also be provided in the course web page. For each test case, the first line
contains the values of n, k, d, and it is followed by k lines each containing a length
n vector of 0’s and 1’s. The 0’s and 1’s are separated by blanks. Your program
should establish whether the code has minimum weight d. You may assume that
n is at most 96.
2

C.The idea of program

[first version]
1. Using revolve-door unrank function in textbook to generate index array for subset combination. So, by incrementing rank
one by one, we can iterate all subset. This method is comparatively a bit slow than other "successor" function.
However, I am using it with purpose to make a distributed program.

[improved version]
1. 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, oddArray and evenArray, and use a pointer to point to
them alternatively depending whether the current rank is odd or even.

[MPI version]
1. 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.
2. Root node read from data file and broadcast n,k,d and vector to all other nodes.
3. 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.
4. 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.

[platform]
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".

D.The major functions

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.

E.Further improvement

F.File listing

MPI-version:

1. mpi.cpp

2. myset.h

3. myset.cpp

4. revolve.h

5. revolve.cpp

to compile:
mpic++ mpi.cpp myset.cpp revolve.cpp -o mpimyset.exe

to run:
>time mpirun -np 9 mpimyset.exe test5.txt >result5.txt &

file name: mpi.cpp

#include "myset.h"
#include "revolve.h"
#include <iostream>
#include <mpi.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[])
{

    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)
    {
        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);
        }
    }

    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 revolveUnRank(long theRank, size_t subSize);
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 t);

　

file name: revolve.cpp

#include "revolve.h"
#include "myset.h"

#include <iostream>
#include <fstream>

using namespace std;

extern long lastResult;

size_t groundsetSize, subsetSize;

size_t n, k, d;
size_t* buffer;
size_t bufferSize;
MySet* sets;

MySet current;

size_t* oddArray=NULL;
size_t* evenArray=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);
    }

    lastResult=result;
    return result;
}

void revolveUnRank(__int64 theRank, size_t subSize)
{
    __int64 last=-1, curr=-1, r=theRank;
    int i;
    size_t x=groundsetSize;
    subsetSize=subSize;
    size_t* c;
    if (theRank%2==0)
    {
        c=evenArray;
    }
    else
    {
        c=oddArray;
    }

    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-1]=x-1;
        }
        else
        {
            c[i-1]=x;
        }
        r=last-r-1;
    }
    /*
    cout<<"now show rank="<<theRank<<endl;
    for ( i=0; i<subsetSize; i++)
    {
        cout<<revolveArray[i]+1<<",";
    }
    cout<<"\n";
    */

}

int findSmallest(int& oddIndex, int& evenIndex)
{
    while (oddIndex<subsetSize&&evenIndex<subsetSize)
    {
        if (oddArray[oddIndex]==evenArray[evenIndex])
        {
            oddIndex++;
            evenIndex++;
        }
        else
        {
            if (oddArray[oddIndex]<evenArray[evenIndex])
            {
                //must make easy for next
                return oddArray[oddIndex++];
            }
            else
            {
                return evenArray[evenIndex++];
            }
        }
    }

    if (oddIndex==evenIndex&&oddIndex==subsetSize)
    {
        cout<<"find smallest failed, check array!\n";
        exit(1);
    }
    else
    {
        if (oddIndex<evenIndex)
        {
            return oddArray[oddIndex];
        }
        else
        {
            return evenArray[evenIndex];
        }
    }
}


void findChangedVectorIndex(int& first, int& second)
{
    int oddIndex=0, evenIndex=0;
    first=findSmallest(oddIndex, evenIndex);
    second=findSmallest(oddIndex, evenIndex);
}

bool weightTest(__int64 startRank, __int64 count, int subSize)
{
    subsetSize=subSize;
    int left, right;
    for (__int64 i=0; i<count; i++)
    {
        revolveUnRank(startRank+i, subSize);
        if ((startRank+i)%2==0)
        {
            c=evenArray;
        }
        else
        {
            c=oddArray;
        }
        if (i==0)
        {
            current=sets[c[0]];
            for (int j=1; j<subSize; j++)
            {
                current^(sets[c[j]]);
            }
        }
        else
        {
            findChangedVectorIndex(left, right);//not the index of array
            current^(sets[left]);
            current^(sets[right]);
        }

        if (current.SetOrder()<d)
        {
            cout<<"this is for test:\n";
            for (int m=0; m<subSize; m++)
            {
                cout<<c[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);
        sets[i]=array+(i*sets[i].getDigitCount());
    }
    current.initialize(n);
    oddArray=new size_t[n+1];
    evenArray=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 j;
    size_t* c=revolveArray;
    c[0]=0;
    for (j=1; j<=t; j++)
    {
        c[j]=j-1;
    }
    c[t+1]=n;

R2:
    for (size_t i=0; i<t+1; i++)
    {
        cout<<c[i]<<",";
    }
    cout<<"\n";

    if (t%2==1)
    {
        if (c[1]+1<c[2])
        {
            c[1]++;
            goto R2;
        }
        else
        {
            j=2;
            goto R4;
        }
    }
    else
    {
        if (c[1]>0)
        {
            c[1]--;
            goto R2;
        }
        else
        {
            j=2;
            goto R5;
        }
    }

R4:
    if (c[j]>=j)
    {
        c[j]=c[j-1];
        c[j-1]=c[j-2];
        goto R2;
    }
    else
    {
        j++;
    }
R5:
    if (c[j]+1<c[j+1])
    {
        c[j-1]=c[j];
        c[j]++;
        goto R2;
    }
    else
    {
        j++;
        if (j<=t)
        {
            goto R4;
        }
    }
}

*/

improved-version: (the only difference from mpi-version is the "main.cpp" and all other are same.)

1. main.cpp

2. myset.h

3. myset.cpp

4. revolve.h

5. revolve.cpp

6. makefile

file name: main.cpp

#include "myset.h"
#include "revolve.h"
#include <iostream>
#include <cmath>

using namespace std;

extern size_t n, k, d;
extern size_t* buffer;
extern MySet* sets;
extern MySet current;

int main(int argc, char* argv[])
{

    int i, subset;
    __int64 total;
    if (argc<2)
    {
        cout<<"usage: myset.exe filename\n";
        exit(1);
    }
    readFromFile(argv[1]);
    initialize(n, k, d, buffer);

    for ( i=0; i<k; i++)
    {
        sets[i].display();
    }

    for (subset=1; subset<=k; subset++)
    {
        total=combineNumber(k, subset);
        cout<<"now try subset of "<<subset<<endl;

        if (!weightTest(0, total, subset))
        {
            cout<<"current is:";
            current.display();
            break;
        }

    }
    return 0;
}

　

file name: makefile

　

myset : main.cpp myset.o revolve.o
    g++ main.cpp myset.o revolve.o -o myset.exe

myset.o : myset.h myset.cpp
    g++ -c myset.cpp -o myset.o

revolve.o : revolve.h revolve.cpp
    g++ -c revolve.cpp -o revolve.o

first-version:

1. main.cpp

2. myset.h

3. myset.cpp

4. revolve.h

5. revolve.cpp

6. makefile (same as improved version)

file name: main.cpp

#include "myset.h"
#include "revolve.h"
#include <iostream>
#include <cmath>

using namespace std;

extern size_t n, k, d;
extern size_t* buffer;
extern MySet* sets;
extern MySet current;

int main(int argc, char* argv[])
{

    int i, subset;
    __int64 total;
    if (argc<2)
    {
        cout<<"usage: myset.exe filename\n";
        exit(1);
    }
    readFromFile(argv[1]);
    initialize(n, k, d, buffer);

    for ( i=0; i<k; i++)
    {
        sets[i].display();
    }

    for (subset=1; subset<=k; subset++)
    {
        total=combineNumber(k, subset);
        cout<<"now try subset of "<<subset<<endl;

        if (!weightTest(0, total, subset))
        {
            cout<<"current is:";
            current.display();
            break;
        }

    }
    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 revolveUnRank(long theRank, size_t subSize);
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 t);

file name: revolve.cpp

#include "revolve.h"
#include "myset.h"

#include <iostream>
#include <fstream>


using namespace std;

extern long lastResult;

size_t groundsetSize, subsetSize;

size_t n, k, d;
size_t* buffer;
size_t bufferSize;
MySet* sets;




MySet current;


size_t* oddArray=NULL;
size_t* evenArray=NULL;


__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);
	}

	lastResult=result;
	return result;
}


void revolveUnRank(__int64 theRank, size_t subSize)
{
	__int64 last=-1, curr=-1, r=theRank;
	int i;
	size_t x=groundsetSize;
	subsetSize=subSize;
	size_t* c;
	if (theRank%2==0)
	{
		c=evenArray;
	}
	else
	{
		c=oddArray;
	}

	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-1]=x-1;	
		}
		else
		{
			c[i-1]=x;	
		}
		r=last-r-1;
	}
	/*
	cout<<"now show rank="<<theRank<<endl;
	for ( i=0; i<subsetSize; i++)
	{
		cout<<revolveArray[i]+1<<",";
	}
	cout<<"\n";
	*/

}

int findSmallest(int& oddIndex, int& evenIndex)
{
	while (oddIndex<subsetSize&&evenIndex<subsetSize)
	{
		if (oddArray[oddIndex]==evenArray[evenIndex])
		{
			oddIndex++;
			evenIndex++;
		}
		else
		{
			if (oddArray[oddIndex]<evenArray[evenIndex])
			{
				//must make easy for next 
				return oddArray[oddIndex++];
			}
			else
			{				
				return evenArray[evenIndex++];
			}
		}
	}
	
	if (oddIndex==evenIndex&&oddIndex==subsetSize)
	{
		cout<<"find smallest failed, check array!\n";
		exit(1);
	}
	else
	{
		if (oddIndex<evenIndex)
		{
			return oddArray[oddIndex];
		}
		else
		{
			return evenArray[evenIndex];
		}
	}
}
					

void findChangedVectorIndex(int& first, int& second)
{
	int oddIndex=0, evenIndex=0;
	first=findSmallest(oddIndex, evenIndex);
	second=findSmallest(oddIndex, evenIndex);
}

bool weightTest(__int64 startRank, __int64 count,  int subSize)
{
	subsetSize=subSize;
	int left, right;
	size_t* c;
	for (__int64 i=0; i<count; i++)
	{
		revolveUnRank(startRank+i, subSize);
		if ((startRank+i)%2==0)
		{
			c=evenArray;
		}
		else
		{
			c=oddArray;
		}
		if (i==0)
		{
			current=sets[c[0]];
			for (int j=1; j<subSize; j++)
			{
				current^(sets[c[j]]);
			}
		}
		else
		{
			findChangedVectorIndex(left, right);//not the index of array
			current^(sets[left]);
			current^(sets[right]);
		}
			
		if (current.SetOrder()<d)
		{
			cout<<"this is for test:\n";
			for (int m=0; m<subSize; m++)
			{
				cout<<c[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);
		sets[i]=array+(i*sets[i].getDigitCount());
	}
	current.initialize(n);
	oddArray=new size_t[n+1];
	evenArray=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 j;
	size_t* c=revolveArray;
	c[0]=0;
	for (j=1; j<=t; j++)
	{
		c[j]=j-1;
	}
	c[t+1]=n;

R2:
	for (size_t i=0; i<t+1; i++)
	{
		cout<<c[i]<<",";
	}
	cout<<"\n";



	if (t%2==1)
	{
		if (c[1]+1<c[2])
		{
			c[1]++;
			goto R2;
		}
		else
		{
			j=2;
			goto R4;	
		}
	}
	else
	{
		if (c[1]>0)
		{
			c[1]--;
			goto R2;
		}
		else
		{
			j=2;
			goto R5;
		}
	}

R4:
	if (c[j]>=j)
	{
		c[j]=c[j-1];
		c[j-1]=c[j-2];
		goto R2;
	}
	else
	{
		j++;
	}
R5:
	if (c[j]+1<c[j+1])
	{
		c[j-1]=c[j];
		c[j]++;
		goto R2;
	}
	else
	{
		j++;
		if (j<=t)
		{
			goto R4;
		}
	}
}
		
*/

test files:

1. test0.txt

2. test1.txt

3. test2.txt

4. test3.txt

5. test4.txt

6. test5.txt

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>