The following code implements an exhaustive search using backtracking to compute the maximum size of a 3-uniform set system on [n] with VC-dimension at most 2.
In practice, this program only works for small values of n. For our purpose, we only need the result for n=6 and n=7. For example, on a typical personal computer, when n = 7, this C program takes only about 1 minute to verify that the size of the largest 3-uniform set system on [7] with the given VC-dimension is at most 16.
The detailed algorithm is provided in the Appendix.
The following code was written by Prof. Jian Wang (wangjian01@tyut.edu.cn).
/*A search using back-tracking*/
#include <iostream>
#include<fstream>
#include <algorithm>
#include<ctime>
#include <string>
#include <bitset>
#include <math.h>
using namespace std;
#define N 50
#define M 10000
#define L 7
#define K 3
int n, k, tmp,sum=1,pos;
int setNum[M]; //the set of all 0-1 sequences with k 1's
int traceList[M][N]; //traceList[i][j], j=1,2,...,2^k, list all possible traces of sequences setNum[i]
int traceList2[N][M][N]; //traceList2[q][i][j] gives whether the trace traceList[i][j] is shattered in run q of the backtracking
int current[M]; //the list in backtracking
int max = 1;
fstream file;
int number_of_1(int m) // return the number of 1's in binary m
{
int count = 0;
for (int i = 0; i < n; i++) {
if (((m >> i) & 1) == 1) {
count++;
}
}
return count;
}
string index_of_1(int m) //return the index of 1 in binary m
{
string set = "";
for (int i = 0; i < n; i++) {
if (((m >> i) & 1) == 1) {
set = set + to_string(i + 1);
}
}
if (set == "") set = "empty";
return set;
}
int generateSets()// generate all 0-1 sequences with k 1's as an integer
{
sum = 1;
for (int i = 0; i < pow(2, n); i++)
{
tmp = number_of_1(i);
if (tmp == k)
{
setNum[sum] = i;
// bitset<7> bit(i);
// cout << bit << endl;
sum++;
}
}
sum--;
return 0;
}
int generateTracelist()// generate all possible traces of sequences setNum[i]
{
for (int i = 1; i <= sum; i++)
{
bitset<L> bit1(setNum[i]);
tmp = setNum[i];
for (int j = 0; j < pow(2, k); j++)
{
bitset<K> bit2(j);
int count = 0;
for (int p = 0; p < n; p++) {
if (((tmp >> p) & 1) == 1) {
bit1[p] = bit2[count];
count++;
}
}
traceList[i][j+1] = bit1.to_ullong();
}
}
return 1;
}
int showList()
{
file.open("full.txt", ios::out);
if (!file) {
cerr << "Unable to open file!" << endl;
return 1; // fail
}
for (int i = 1; i <=sum; i++)
{
file <<i<<"->" << index_of_1(setNum[i]) << ":";
for (int j = 1; j <=pow(2, k); j++)
{
file << index_of_1(traceList[i][j]) << "|";
}
file << endl;
}
file.close();
return 0;
}
int checkList()
{
file.open("checkList.txt", ios::out);
if (!file) {
cerr << "Unable to open file!" << endl;
return 1; // fail
}
pos = 13;
current[1] = 4; current[2] = 6; current[3] = 8; current[4] = 9;
current[5] = 10; current[6] = 11; current[7] = 14; current[8] = 15;
current[9] = 16; current[10] = 17; current[11] = 18; current[12] = 19;
current[13] = 20;
int temlist[N];
for (int i = 1; i <= pos; i++)
{
for (int j = 1; j <= pow(2, k); j++)
{
temlist[j] = 0;
}
int x = current[i];//check the trace of x
for (int j = 1; j <= pos; j++)
{
int y = current[j];
int trace = setNum[x] & setNum[y];
for (int p = 1; p <= pow(2, k); p++)
{
if (temlist[p] == 0 && trace == traceList[x][p])
{
temlist[p] = 1;
}
}
}
file << index_of_1(setNum[x]) << ":missing->";
for (int j = 1; j <= pow(2, k); j++)
{
if (temlist[j] == 0)
{
file << index_of_1(traceList[x][j]) << "|";
}
}
file << "********trace->";
for (int j = 1; j <= pow(2, k); j++)
{
if (temlist[j] == 1)
{
file << index_of_1(traceList[x][j]) << "|";
}
}
file << "*********************************************************************" << endl;
}
file.close();
return 0;
}
int maxSetVcdim2() //the back-tracking
{
file.open("example.txt", ios::out);
if (!file) {
cerr << "Unable to open file!" << endl;
return 1; // fail
}
for (int i = 1; i <= sum; i++)
{
for (int j = 0; j <= pow(2, k); j++)
{
for (int p = 0; p <= pow(2, k); p++)
{
traceList2[p][i][j] = 0;
}
}
}
current[1] = 1;
traceList2[1][1][0] = 1;
traceList2[1][1][(int)pow(2, k)] = 1;
pos=2;
int max = 1;
current[pos] = current[pos - 1];
while (pos>1)
{
/*checking output data*/
/* for (int i = 1; i < pos; i++)
{
int y = current[i];
cout << index_of_1(setNum[y]) << ":missing->";
for (int j = 1; j <= pow(2, k); j++)
{
if (traceList2[pos - 1][y][j] == 0)
{
cout<< index_of_1(traceList[y][j]) << "|";
}
}
cout << index_of_1(setNum[y]) << "********trace->";
for (int j = 1; j <= pow(2, k); j++)
{
if (traceList2[pos - 1][y][j] == 1)
{
cout << index_of_1(traceList[y][j]) << "|";
}
}
cout << endl;
}
// getchar();
/*checking output data*/
current[pos]++;
if (current[pos] > sum)
{
pos--;
if (pos >=max) //If a larger family is found then output it.
{
max = pos;
file << max << "->";
for (int i = 1; i <=pos; i++)
{
file << index_of_1(setNum[current[i]]) << " ";
}
file << endl;
file << "*********************************************************************" << endl;
for (int i = 1; i <=pos; i++)
{
int y = current[i];
file << index_of_1(setNum[y]) << ":missing->";
for (int j = 1; j <= pow(2, k); j++)
{
if (traceList2[pos][y][j] == 0)
{
file << index_of_1(traceList[y][j]) << "|";
}
}
file <<"********trace->";
for (int j = 1; j <= pow(2, k); j++)
{
if (traceList2[pos][y][j] == 1)
{
file << index_of_1(traceList[y][j]) << "|";
}
}
file << endl;
}
file << "*********************************************************************" << endl;
}
continue;
}
int increaseVCdim = 0;
//if we add setNum[z] to the family, the variable used to check whether the Vc dimension is increased.
int z = current[pos];//index of the new set
for (int j = 1; j <= pow(2, k); j++)
{
traceList2[pos][z][j] = 0;
}
traceList2[pos][z][(int)pow(2, k)] = 1;
for (int i = 1; i <pos; i++)
{
int y = current[i];
int numx = setNum[y]&setNum[z];//the intersection of setNum[y] and setNum[z]
for (int j = 1; j <= pow(2, k) - 1; j++)
{
if (numx == traceList[z][j])//record the traces of z with sets already in the family
{
traceList2[pos][z][j] =1;
}
}
// cout << index_of_1(numx) << "------" << index_of_1(setNum[z]) << "cap" << index_of_1(setNum[y]) << traceList2[pos][z][4] << endl;
if (traceList2[pos-1][y][0] !=(int) pow(2, k) - 1) continue; //clearly y is not shattered in this case
for (int j = 1; j <= pow(2, k)-1; j++) //if traces of setNum[y] is 2^k-1 before adding z, consider the new trace created by setNum[y]&setNum[z]
{
if (numx == traceList[y][j]&& traceList2[pos-1][y][j] == 0)
{
increaseVCdim = 1;
break;
}
}
if (increaseVCdim == 1) break;
}
traceList2[pos][z][0] = 0; //update the trace of setNum[z]
for (int j = 1; j <= pow(2, k); j++)
{
traceList2[pos][z][0] += traceList2[pos][z][j];
}
if (traceList2[pos][z][0] == (int)pow(2, k)) increaseVCdim = 1;// if z is shattered
if (increaseVCdim == 0) //one can add z into the current family
{
for (int i = 1; i < pos; i++)
{
int y = current[i]; //copy the previous trace
for (int j = 0; j <= pow(2, k); j++)
{
traceList2[pos][y][j] = traceList2[pos-1][y][j];
}
}
for (int i = 1; i < pos; i++)//update the traces
{
int y = current[i];
int numx = setNum[y] & setNum[z];
for (int j = 1; j <= pow(2, k) - 1; j++)
{
if (numx == traceList[y][j]&& traceList2[pos][y][j]==0)
{
traceList2[pos][y][j] = 1;
traceList2[pos][y][0]++;
}
}
}
if (false&&pos == 3) {
for (int i = 1; i <= pos; i++)
{
int y = current[i];
cout << index_of_1(setNum[y]) << ":missing->";
for (int j = 1; j <= pow(2, k); j++)
{
if (traceList2[pos][y][j] == 0)
{
cout << index_of_1(traceList[y][j]) << "|";
}
}
cout << "********trace->";
for (int j = 1; j <= pow(2, k); j++)
{
if (traceList2[pos][y][j] == 1)
{
cout << index_of_1(traceList[y][j]) << "|";
}
}
cout << endl;
}
// getchar();
}
pos++;
current[pos] = current[pos - 1];
}
}
file.close();
return 1;
}
int main()
{
n = L;
k = K;
generateSets();
generateTracelist();
showList();
//checkList();
// getchar();
maxSetVcdim2();
return 0;
}
No Responses