Created
December 6, 2015 21:28
-
-
Save anonymous/8fa8f3164dd7ab91293a to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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