Skip to content

Instantly share code, notes, and snippets.

@joriki
Created January 25, 2023 15:11
Show Gist options
  • Save joriki/8fc855870dd73d3c331db21539a25df3 to your computer and use it in GitHub Desktop.
Save joriki/8fc855870dd73d3c331db21539a25df3 to your computer and use it in GitHub Desktop.
Find bit strings with no pairwise XOR sums in common; see https://math.stackexchange.com/questions/4624075.
import java.util.Random;
public class Question4624075 {
final static int k = 34;
final static int n = 10;
final static int m = 1 << n;
final static int nvalues = (k * (k + 1)) / 2;
final static Random random = new Random();
static int sum;
static int min;
static int count;
static int [] counts = new int [m];
static boolean [] used = new boolean [m];
static int [] x = new int [k];
static double beta;
static void increment (int x) {
sum += 2 * counts [x] + 1;
if (++counts [x] == 2)
count++;
}
static void decrement (int x) {
sum -= 2 * counts [x] - 1;
if (counts [x]-- == 2)
count--;
}
static void clear (int i) {
used [x [i]] = false;
decrement (x [i]);
for (int j = 0;j < k;j++)
if (j != i)
decrement (x [i] ^ x [j]);
}
static void set (int i) {
used [x [i]] = true;
increment (x [i]);
for (int j = 0;j < k;j++)
if (j != i)
increment (x [i] ^ x [j]);
}
static void randomize (int i) {
do
x [i] = random.nextInt(m - 1) + 1;
while (used [x [i]] || counts [x [i]] != 0);
}
public static void main (String [] args) {
used [0] = true;
for (int i = 0;i < k;i++) {
randomize (i);
used [x [i]] = true;
increment (x [i]);
}
outer:
for (int a : x)
for (int b : x) {
if (b == a)
continue outer;
increment (a ^ b);
}
int l = 0;
min = count;
for (beta = 0;count > 0;beta += .00000008) {
for (int i = 0;i < k;i++) {
int oldSum = sum;
int oldX = x [i];
clear (i);
randomize (i);
set (i);
if (sum > oldSum && Math.random() > Math.exp(beta * (oldSum - sum))) {
clear (i);
x [i] = oldX;
set (i);
}
min = Math.min(min,count);
}
if ((++l & 0x7fff) == 0)
print();
}
print();
for (int i = 0;i < k;i++) {
System.out.print((i % 5) == 0 ? "\n" : " ");
System.out.print(String.format("%" + n + "s", Integer.toBinaryString(x [i])).replace(' ', '0'));
}
}
static void print() {
System.out.println(beta + " : " + min + " / " + count + " / " + sum + " / " + nvalues);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment