Skip to content

Instantly share code, notes, and snippets.

Created December 6, 2015 21:28
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save anonymous/8fa8f3164dd7ab91293a to your computer and use it in GitHub Desktop.
Save anonymous/8fa8f3164dd7ab91293a to your computer and use it in GitHub Desktop.
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
int dim = 4, ntrials=100000000;
/* The program counts the number of hamiltonian cycles in the graph that
* has the vertices of the hypercube of dimension <dim> as its vertices and all
* the possible diagonals as its edges.
* The vertices are represented by the numbers from 0 to 2^dim - 1. The <dim>
* bits in such a number are to be interpreted as the <dim> coordinates. */
/* power(a, b) computes a to the bth power*/
int
power(a, b)
{
if(b == 0)
return 1;
else
return a * power(a, b-1);
}
/* checks if the binary expansion of k has exactly one bit with value 1*/
int
is_power_of_two(int k)
{
if(k != 0) {
while(k % 2 == 0)
k /= 2;
}
if(k == 1)
return 1;
else
return 0;
}
/* computes c = <a> XOR <b>. c has exactly one bit with value 1, if and only if
* a and b are neighbours.
* neighbours*/
int
is_neighbour(int a, int b)
{
return is_power_of_two(a ^ b);
}
/* The function nwalks counts the number of permutations of the elements of
* <pool> that ...
* ... start with pool[0]
* ... do not end with a neighbour of 0
* ... do not contain two consecutive elements that are neighbours
*/
long
nwalks(int *pool, int lpool)
{
int i, tmp;
long s = 0;
if(lpool == 1) {
if(is_neighbour(pool[0], 0))
return 0;
else
return 1;
}
for(i = 1; i < lpool; i++) {
if(!is_neighbour(pool[i], pool[0])) {
tmp = pool[1]; pool[1] = pool[i]; pool[i] = tmp;
s += nwalks(pool + 1, lpool - 1);
pool[i] = pool[1]; pool[1] = tmp;
}
}
return s;
}
/* shuffles the elements of <pool> */
void
randperm(int *pool, int lpool)
{
int i, tmp;
if(lpool <= 1)
return;
i = rand() % lpool;
tmp = pool[0]; pool[0] = pool[i]; pool[i] = tmp;
randperm(pool+1, lpool-1);
}
/* checks whether the elements of pool in this order are a cycle*/
int
is_good(int *pool, int lpool)
{
int i;
for(i = 0; i < lpool; i++) {
if(is_neighbour(pool[i], pool[(i + 1) % lpool]))
return 0;
}
return 1;
}
int
main()
{
int *pool, npoints;
int i, ngood;
npoints = power(2, dim);
pool = malloc(sizeof(int) * npoints);
for(i = 0; i < npoints; i++)
pool[i] = i;
/* (Number of cycles) = <npoints> * (Number of cycles that start with 0)
*/
printf("%ld\n", ((long) npoints) * nwalks(pool, npoints));
/* Uncomment the following block to compute a Monte Carlo approximation
* of the probability. It simply looks at <ntrials> random permutations
* of the pool and counts how many are good.
*/
/* srand(time(NULL));
for(i = 0, ngood = 0; i < ntrials; i++) {
randperm(pool, npoints);
if(is_good(pool, npoints))
ngood++;
}
printf("%f\n", ((float) ngood)/ ((float) ntrials));*/
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment