Remove duplicates that come from multiple copies or translations from each function generation.

1 files changed, 34 insertions, 16 deletions

diff --git a/charf.c b/charf.c
index 4ffbb54..27d4a4a 100644
--- a/charf.c
+++ b/charf.c
@@ -155,24 +155,42 @@ void compute_maximalfunction(VALUETYPE* f, VALUETYPE* Mf, int D){
 /*Generates all characteristic functions of length up N.*/
 int generate_each_charf(VALUETYPE* f, int i){
 	int s=0;
-	int d=0;
-	while(d+2 <= N){
-		/*number of strings of length d that are not all 0s or all 1s*/
-		int powd = 1<<d;
-		if(i-s >= powd){
-			s += powd;
-			d++;
-		}
-		else {
-			int t = i-s;
-			/*Set f to the values encoded in bit string t which is a value between 1 and powd = (1<<d)-2.*/
-			f[0] = int_to_valuetype(1);
-			f[1] = int_to_valuetype(0);
-			for(int n=0; n<d; n++) f[2+n] = int_to_valuetype((t >> n) & 1);
-			return d+2;
+	int d=2;
+	/*number of strings of length d that begin with 1 but are not all 1*/
+	for(s=0; i-s >= (1<<(d-1))-1; d++) s += (1<<(d-1))-1;
+
+	if(d>N) return -1;
+
+	/*t starts with 1 and then comes i-s.*/
+	int t = (1 << d-1) + i-s;
+
+	/*Indicates if we want to consider this t.*/
+	bool is_representative = true;
+
+	/*Check if t encodes a function that is made up of translations of a shorter function.*/
+	for(int r = 1; r < d; r++){
+		if(d % r == 0){
+			bool is_r_copy = true;
+			int ones = 0;
+			for(int o = 0; o<r; o++) ones += 1<<o;
+			int tail = t & ones;
+			for(int n = 1; n < d/r; n++) if( ( (t>>n*r) & ones ) != tail ) is_r_copy = false;
+			if(is_r_copy) is_representative = false;
 		}
 	}
-	return -1;
+
+	/*Check if t encodes the strictly largest of its equivalent translates.*/
+	/*Such t which may equal its translates have already been filtered out by the previous step because they are copies of at least two shorter functions.*/
+	int ones = 0;
+	for(int o = 0; o<d; o++) ones += 1<<o;
+	if(is_representative) for(int n=1; n<d; n++) if( t <= ( (t<<n) & ones ) + ((t>>(d-n)) & ones) ) is_representative = false;
+
+	/*Set f to the values encoded in bit string t which is a value between 1 and powd = (1<<d)-2.*/
+	if(is_representative){
+		for(int n=0; n<d; n++) f[n] = int_to_valuetype((t >> (d-n-1)) & 1);
+		return d;
+	}
+	else return 0;
 }
 
 int generate_triangle(VALUETYPE* f, int i){