This code was written by Yixuan (Alice) Huang when she was my research student through the Wake Forest Research Fellowship.
/* Name: Yixuan Huang; Robert Won; Michael Tait
* Project: Sidon sets and 2-caps in F_3^n
* Contact Info: huany16@wfu.edu
* This is a C++ program which recursively outputs
* the largest complete 2-caps starting with any given
* (possibly empty) subset of F_3^n.
*/
#include <iostream>
#include <vector>
#include <cmath>
#include <fstream>
using namespace std;
int DIM = 5; //Dimension n of F_3^n.
ofstream outfile ("/Complete2Caps.txt"); //The output file will list all complete 2-caps.
int maxCapSize = 1; // "maxCapSize" records the size of the largest 2-cap encountered so far. The program only prints 2-caps that are at least as big as maxCapSize.
//We will sometimes regard a point of F_3^n simply as a ternary string, which we can then regard as a natural number. The next two functions convert between natural numbers and points of F_3^n.
//This function takes a natural number, "temp", regards it as a ternary string, and returns the corresponding point of F_3^n.
void NumToPts(int temp, vector<int> &result){
result.clear();
int index = 0;
int num = temp;
int a;
while(index < DIM-1){
result.push_back(num/pow(3,DIM-1-index));
a = pow(3,DIM-1-index);
num = num % a;
index++;
}
result.push_back(num);
return;
}
//This function takes a point, "Pts", of F_3^n, converts it to a ternary string, and returns the corresponding natural number.
int PtsToNum(const vector<int> Pts){
int result = 0;
for(int i = 0; i < Pts.size(); i++){
result = result + Pts.at(i)*pow(3,DIM-1-i);
}
return result;
}
//This function takes as a inputs two vectors, "temp1" and "temp2", and returns their sum (as elements of F_3^n).
void sumOfTwoPtDec(const vector<int> temp1, const vector<int> temp2,vector<int> &result){
result.clear();
for(int i = 0; i < temp1.size(); i++){
result.push_back((temp1.at(i) + temp2.at(i)) % 3);
}
}
//This function takes as input a 2-cap, "cap". The function will alter the vector "possibleChoices" so that it includes only those points of F_3^n which are not coplanar with any triple of points in "cap". Each of these points can be added to "cap" while still remaining a 2-cap.
void possibleChoices(vector <int> cap, vector<int> &possibleChoices){
vector<bool> checkMatrix;
int numPts = pow(3,DIM);
for(int i = 0; i < numPts; i++){
//The boolean vector checkMatrix records whether a point of F_3^n is coplanar with a triple of points in cap. We initialize it with all entries as false.
checkMatrix.push_back(false);
}
vector<int> tempA,tempB,tempC;
vector<int> temp2A_2B,temp2A_B_C,tempA_2B_C,temp2A_2C,tempA_B_2C,temp2B_2C;
//This nested for loop iterates over all possible triples of points in cap. For each triple, it determines the remaining six points which are coplanar with the triple, and marks these points true in checkMatrix.
for(int index0 = 0; index0 < cap.size(); index0++){
for(int index1 = 0; index1 < cap.size(); index1++){
for(int index2 = 0; index2 < cap.size(); index2++){
NumToPts(cap.at(index0),tempA);
NumToPts(cap.at(index1),tempB);
NumToPts(cap.at(index2),tempC);
//2a+2b
sumOfTwoPtDec(tempA,tempB,temp2A_2B);
sumOfTwoPtDec(temp2A_2B,temp2A_2B,temp2A_2B);
checkMatrix.at(PtsToNum(temp2A_2B)) = true;
//2a+2c
sumOfTwoPtDec(tempA,tempC,temp2A_2C);
sumOfTwoPtDec(temp2A_2C,temp2A_2C,temp2A_2C);
checkMatrix.at(PtsToNum(temp2A_2C)) = true;
//2b+2c
sumOfTwoPtDec(tempB,tempC,temp2B_2C);
sumOfTwoPtDec(temp2B_2C,temp2B_2C,temp2B_2C);
checkMatrix.at(PtsToNum(temp2B_2C)) = true;
//2a+b+c
sumOfTwoPtDec(tempA,tempB,temp2A_B_C);
sumOfTwoPtDec(temp2A_B_C,tempA,temp2A_B_C);
sumOfTwoPtDec(temp2A_B_C,tempC,temp2A_B_C);
checkMatrix.at(PtsToNum(temp2A_B_C)) = true;
//a+2b+c
sumOfTwoPtDec(tempA,tempB,tempA_2B_C);
sumOfTwoPtDec(tempA_2B_C,tempB,tempA_2B_C);
sumOfTwoPtDec(tempA_2B_C,tempC,tempA_2B_C);
checkMatrix.at(PtsToNum(tempA_2B_C)) = true;
//a+b+2c
sumOfTwoPtDec(tempA,tempB,tempA_B_2C);
sumOfTwoPtDec(tempA_B_2C,tempC,tempA_B_2C);
sumOfTwoPtDec(tempA_B_2C,tempC,tempA_B_2C);
checkMatrix.at(PtsToNum(tempA_B_2C)) = true;
}
}
}
possibleChoices.clear(); //This vector records the remaining possible choices.
for(int i = 0; i < checkMatrix.size(); i++) {
if (checkMatrix.at(i) == false) {
possibleChoices.push_back(i);
}
}
}
//This function is similar to the function "possibleChoices" but takes two inputs: a 2-cap "cap" and a vector which is some subset of F_3^n, "possibleChoices". It then removes from "possibleChoices" all points which are coplanar with any triple from "cap". It returns these points as the vector "newPossibleChoices". Importantly, this function will also only return points in "newPossibleChoices" that are lexicographically later than every point in "cap". Hence, in calling this function, we are assuming that we are building "cap" in order, lexicographically.
void possibleChoices2(vector <int> cap, vector<int> possibleChoices,vector<int> &newPossibleChoices) {
vector<bool> checkMatrix;
vector<int> tempA, tempB, tempC;
int numPts = pow(3, DIM);
for (int i = 0; i < numPts; i++) {
// If an entry in checkMatrix is "true", this means the point is coplanar with some triple of points in "cap". We initialize checkMatrix as all fales.
checkMatrix.push_back(false);
}
vector<vector<int>> ptsMatrixs; // This matrix merely records the points in "cap" as points, rather than as numbers.
vector<int> tempVec;
//
for (int i = 0; i < cap.size(); i++) {
NumToPts(cap.at(i), tempVec);
ptsMatrixs.push_back(tempVec);
tempVec.clear();
}
NumToPts(cap.at(cap.size() - 1), tempC); // The last element in "cap", which we are assuming is lexicographically latest.
// This nested for loop iterates over every triple of points cap, and determines all points which are coplanar with each triple. It then marks these points as "true" in "checkMatrix".
vector<int> temp2A_2B, temp2A_B_C, tempA_2B_C, temp2A_2C, tempA_B_2C, temp2B_2C;
for (int index0 = 0; index0 < ptsMatrixs.size(); index0++) {
for (int index1 = 0; index1 < ptsMatrixs.size(); index1++) {
tempA = ptsMatrixs.at(index0);
tempB = ptsMatrixs.at(index1);
//2a+2b
sumOfTwoPtDec(tempA, tempB, temp2A_2B);
sumOfTwoPtDec(temp2A_2B, temp2A_2B, temp2A_2B);
checkMatrix.at(PtsToNum(temp2A_2B)) = true;
//2a+2c
sumOfTwoPtDec(tempA, tempC, temp2A_2C);
sumOfTwoPtDec(temp2A_2C, temp2A_2C, temp2A_2C);
checkMatrix.at(PtsToNum(temp2A_2C)) = true;
//2b+2c
sumOfTwoPtDec(tempB, tempC, temp2B_2C);
sumOfTwoPtDec(temp2B_2C, temp2B_2C, temp2B_2C);
checkMatrix.at(PtsToNum(temp2B_2C)) = true;
//2a+b+c
sumOfTwoPtDec(tempA, tempB, temp2A_B_C);
sumOfTwoPtDec(temp2A_B_C, tempA, temp2A_B_C);
sumOfTwoPtDec(temp2A_B_C, tempC, temp2A_B_C);
checkMatrix.at(PtsToNum(temp2A_B_C)) = true;
//a+2b+c
sumOfTwoPtDec(tempA, tempB, tempA_2B_C);
sumOfTwoPtDec(tempA_2B_C, tempB, tempA_2B_C);
sumOfTwoPtDec(tempA_2B_C, tempC, tempA_2B_C);
checkMatrix.at(PtsToNum(tempA_2B_C)) = true;
//a+b+2c
sumOfTwoPtDec(tempA, tempB, tempA_B_2C);
sumOfTwoPtDec(tempA_B_2C, tempC, tempA_B_2C);
sumOfTwoPtDec(tempA_B_2C, tempC, tempA_B_2C);
checkMatrix.at(PtsToNum(tempA_B_2C)) = true;
tempA.clear();
tempB.clear();
}
}
vector<int> record; // The vector "record" contains all of the points to remove from the "possibleChoices" vector.
// Since we are assuming that we are building 2-caps in order lexicographically, any points that are lexicographically earlier than the last point in "cap" should be removed from "possibleChoices".
for(int i = 0; i < cap.at(cap.size()-1);i++){
record.push_back(i);
}
// Any points which are coplanar with a triple of points in "cap" should be removed from "possibleChoices".
for (int i = cap.at(cap.size()-1); i < checkMatrix.size(); i++) {
if (checkMatrix.at(i) == true) {
record.push_back(i);
}
}
// We then remove all of the points in "record" from "possibleChoices" and record them in a new vector, "newPossibleChoices".
for(int i = 0; i < record.size(); i++){
for(int j = 0; j< possibleChoices.size(); j++){
if(record.at(i) == possibleChoices.at(j)){
possibleChoices.erase(possibleChoices.begin()+j);
break;
}
}
}
newPossibleChoices.clear();
newPossibleChoices = possibleChoices;
}
//This function prints points of F_3^n when given as a number (representing a ternary string).
void printVec(int temp){
vector<int> result;
NumToPts(temp,result);
cout << "(";
outfile << "(";
fflush(stdout);
for(int i = 0; i < result.size()-1; i++){
cout<< result.at(i) << " ";
outfile << result.at(i) << " ";
fflush(stdout);
}
cout << result.at(result.size()-1);
outfile << result.at(result.size()-1);
fflush(stdout);
cout << ")";
outfile << ")";
fflush(stdout);
}
//This function takes as an input a 2-cap "cap". It will return true if cap is a complete 2-cap which is at least as big as "maxCapSize" and returns false otherwise.
bool isComplete(vector <int> cap){
//If "cap" is smaller than maxCapSize, return false.
if(cap.size()<maxCapSize){
return false;
}
vector<bool> checkMatrix;
int numPts = pow(3,DIM);
for(int i = 0; i < numPts; i++){
//true means the point is coplanar with some triple of points in "cap".
checkMatrix.push_back(false);
}
vector<int> tempA,tempB,tempC;
vector<int> temp2A_2B,temp2A_B_C,tempA_2B_C,temp2A_2C,tempA_B_2C,temp2B_2C;
//Iterates over every triple of points from "cap" and computes all points which are coplanar with the triple. Marks these points as "true" in "checkMatrix".
for(int index0 = 0; index0 < cap.size(); index0++){
for(int index1 = 0; index1 < cap.size(); index1++){
for(int index2 = 0; index2 < cap.size(); index2++){
NumToPts(cap.at(index0),tempA);
NumToPts(cap.at(index1),tempB);
NumToPts(cap.at(index2),tempC);
//2a+2b
sumOfTwoPtDec(tempA,tempB,temp2A_2B);
sumOfTwoPtDec(temp2A_2B,temp2A_2B,temp2A_2B);
checkMatrix.at(PtsToNum(temp2A_2B)) = true;
//2a+2c
sumOfTwoPtDec(tempA,tempC,temp2A_2C);
sumOfTwoPtDec(temp2A_2C,temp2A_2C,temp2A_2C);
checkMatrix.at(PtsToNum(temp2A_2C)) = true;
//2b+2c
sumOfTwoPtDec(tempB,tempC,temp2B_2C);
sumOfTwoPtDec(temp2B_2C,temp2B_2C,temp2B_2C);
checkMatrix.at(PtsToNum(temp2B_2C)) = true;
//2a+b+c
sumOfTwoPtDec(tempA,tempB,temp2A_B_C); //a+b
sumOfTwoPtDec(temp2A_B_C,tempA,temp2A_B_C); //2a+b
sumOfTwoPtDec(temp2A_B_C,tempC,temp2A_B_C); //2a+b+c
checkMatrix.at(PtsToNum(temp2A_B_C)) = true;
//a+2b+c
sumOfTwoPtDec(tempA,tempB,tempA_2B_C); //a+b
sumOfTwoPtDec(tempA_2B_C,tempB,tempA_2B_C); //a+2b
sumOfTwoPtDec(tempA_2B_C,tempC,tempA_2B_C); //a+2b+c
checkMatrix.at(PtsToNum(tempA_2B_C)) = true;
//a+b+2c
sumOfTwoPtDec(tempA,tempB,tempA_B_2C); //a+b
sumOfTwoPtDec(tempA_B_2C,tempC,tempA_B_2C); //a+b+c
sumOfTwoPtDec(tempA_B_2C,tempC,tempA_B_2C); //a+b+2c
checkMatrix.at(PtsToNum(tempA_B_2C)) = true;
}
}
}
//If any entry of "checkMatrix" is false, this means that "cap" is not complete.
for(int i = 0; i < checkMatrix.size();i++){
if(checkMatrix.at(i) == false){
return false;
}
}
return true;
}
//This function takes two inputs: a 2-cap "cap" and a list "possibleChoice" of points in F_3^n which are not coplanar with any triple of points in "cap". This function recursively prints 2-caps whose lexicographically earliest points are the points in "cap" and which are larger than "maxCapSize", an integer which updates to the largest 2-cap which has been printed so far.
void buildCap(vector<int> cap,vector<int> possibleChoice) {
//Base Case: When "cap" is already complete and at least as big as "maxCapSize", we simply return cap.
if (possibleChoice.size() == 0) {
if(isComplete(cap)) {
if(cap.size() > maxCapSize){
maxCapSize = cap.size();
}
for (auto temp:cap) {
printVec(temp);
}
cout << endl;
outfile << endl;
return;
}
}
//Recursion: If "cap" is not complete, we add a possible point to "cap" and call "buildCap" again.
else {
for (int i = 0; i < possibleChoice.size(); ++i) {
vector<int> newChoices;
vector<int> newCap;
vector<int> tempNewChoice;
newCap = cap;
newChoices = possibleChoice;
newCap.push_back(newChoices.at(i));
possibleChoices2(newCap, newChoices, tempNewChoice);
buildCap(newCap, tempNewChoice);
}
}
}
int main() {
if (outfile.is_open()) {
outfile << "Print " << DIM <<"D 2-Cap" << endl;
//The vector "Cap" will record a 2-cap.
vector<int> Cap;
//Manually add the lexicographically earliest points in the desired 2-caps. In this case, all 2-caps that are returned will begin with the points 0, e_1, e_2, e_3, and e_4.
Cap.push_back(0);
Cap.push_back(1);
Cap.push_back(3);
Cap.push_back(9);
Cap.push_back(27);
//"Possible" records which points of F_3^n are not coplanar with any triple of points in "Cap". These are the points which can be added to "Cap" so that it remains a 2-cap.
vector<int> Possible;
possibleChoices(Cap,Possible);
//Setting the "maxCapSize", an integer which records the size of the largest 2-cap so far.
maxCapSize = Cap.size();
//Call the function "buildCap", wihch recursively enumerates all caps starting with the points manually added above which are at least as big as "maxCapSize".
buildCap(Cap,Possible);
fflush(stdout);
//Print out the 2-caps.
cout << "Summary: "<<endl
<< "Dimension: " << DIM << endl
<< "Max Cap Size: " << maxCapSize << endl;
outfile << "Summary: "<<endl
<< "Dimension: " << DIM << endl
<< "Max Cap Size: " << maxCapSize << endl;
fflush(stdout);
outfile.close();
}
else cout << "Unable to open file";
return 0;
}
