Code:
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <limits.h> /* for CHAR_BIT */
#include <combination.h>
#define MAX 18
#define LOWER 4
#define UPPER (MAX*(MAX-1)/2)
#define BITMASK(b) (1 << ((b) % CHAR_BIT))
#define BITSLOT(b) ((b) / CHAR_BIT)
#define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
#define BITCLEAR(a, b) ((a)[BITSLOT(b)] &= ~BITMASK(b))
#define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))
#define BITNSLOTS(nb) ((nb + CHAR_BIT - 1) / CHAR_BIT)
void increment(char* bitarray, int n);
int test_all_zero(char* bitarray, int n);
void make_matrix(char [][BITNSLOTS(MAX)], char* U_array, int n);
void invert(char* bitarray);
void display(char [][BITNSLOTS(MAX)], int n);
int check_sum(char* bitarray, int n);
main(){
char matrix_array[MAX][BITNSLOTS(MAX)];
int i,j;
int combination[LOWER];
int solution_found = 0;
for (i=0; i<MAX; i++){
memset(matrix_array[i], 0, BITNSLOTS(MAX));
}
char U_array[BITNSLOTS(UPPER)];
memset(U_array, 0, BITNSLOTS(UPPER));
while ((check_sum(U_array, UPPER) < LOWER) ||
(check_sum(U_array, UPPER) > (UPPER - LOWER))){
increment(U_array, UPPER);
}
make_matrix(matrix_array, U_array, MAX);
for (i=0; i<LOWER; i++){
combination[i] = i;
}
char test_array[LOWER][BITNSLOTS(MAX)];
char intersection[BITNSLOTS(MAX)];
for (i=0; i<LOWER; i++){
for (j=0; j<UPPER; j++){
test_array[i][j] = matrix_array[combination[i]][j];
}
}
/* THIS SECTION HAS TO BE HARD-CODED. FOR DIFFERENT VALUES
OF "LOWER," PLEASE CHANGE THE CODE IN THIS SECTION. */
for (i=0; i<BITNSLOTS(MAX); i++){
intersection[i] = (test_array[0][i] & test_array[1][i]
& test_array[2][i] & test_array[3][i]);
}
if (BITTEST(intersection, combination[0]) &&
BITTEST(intersection, combination[1]) &&
BITTEST(intersection, combination[2]) &&
BITTEST(intersection, combination[3])){
solution_found++;
}
else{
invert(U_array);
make_matrix(matrix_array, U_array, MAX);
for (i=0; i<LOWER; i++){
for (j=0; j<UPPER; j++){
test_array[i][j] = matrix_array[combination[i]][j];
}
}
for (i=0; i<BITNSLOTS(MAX); i++){
intersection[i] = (test_array[0][i] & test_array[1][i]
& test_array[2][i] & test_array[3][i]);
}
if (BITTEST(intersection, combination[0]) &&
BITTEST(intersection, combination[1]) &&
BITTEST(intersection, combination[2]) &&
BITTEST(intersection, combination[3])){
solution_found++;
}
}
while ((solution_found == 0) && (next_comb(combination, LOWER, MAX))){
while ((check_sum(U_array, UPPER) < LOWER) ||
(check_sum(U_array, UPPER) > (UPPER - LOWER))){
increment(U_array, UPPER);
}
make_matrix(matrix_array, U_array, MAX);
for (i=0; i<LOWER; i++){
for (j=0; j<UPPER; j++){
test_array[i][j] = matrix_array[combination[i]][j];
}
}
for (i=0; i<BITNSLOTS(MAX); i++){
intersection[i] = (test_array[0][i] & test_array[1][i]
& test_array[2][i] & test_array[3][i]);
}
if (BITTEST(intersection, combination[0]) &&
BITTEST(intersection, combination[1]) &&
BITTEST(intersection, combination[2]) &&
BITTEST(intersection, combination[3])){
solution_found++;
}
else{
invert(U_array);
make_matrix(matrix_array, U_array, MAX);
for (i=0; i<LOWER; i++){
for (j=0; j<UPPER; j++){
test_array[i][j] = matrix_array[combination[i]][j];
}
}
for (i=0; i<BITNSLOTS(MAX); i++){
intersection[i] = (test_array[0][i] & test_array[1][i]
& test_array[2][i] & test_array[3][i]);
}
if (BITTEST(intersection, combination[0]) &&
BITTEST(intersection, combination[1]) &&
BITTEST(intersection, combination[2]) &&
BITTEST(intersection, combination[3])){
solution_found++;
}
}
}
/* END OF HARD-CODE */
if (solution_found > 0){
make_matrix(matrix_array, U_array, MAX);
display(matrix_array, MAX);
printf("Solution found.");
}
else{
printf("No solution found.");
}
getch();
}
void increment(char* bitarray, int n){
int i = 0;
while (i < n){
if (!BITTEST(bitarray, i)){
BITSET(bitarray, i);
i = n;
}
else{
BITCLEAR(bitarray, i);
i++;
}
}
}
int test_all_zero(char* bitarray, int n){
int i;
for (i=0; i<n; i++){
if (BITTEST(bitarray, i)){
return 0;
}
else{
return 1;
}
}
}
void invert(char* bitarray){
int i;
for (i=0; i<(UPPER/CHAR_BIT)+1; i++){
bitarray[i] ^= 0xFF;
}
}
void make_matrix(char bitarray[][BITNSLOTS(MAX)], char* U_array, int n){
int i,j,k;
for (i=0, j=0; i<n; i++, j++){
BITSET(bitarray[i], j);
}
for (i=0,j=i+1,k=0; k<((n*(n-1))/2); j++,k++){
if (j >= n){
i++;
j = i+1;
}
if (BITTEST(U_array, k)){
BITSET(bitarray[i], j);
BITSET(bitarray[j], i);
}
else{
BITCLEAR(bitarray[i], j);
BITCLEAR(bitarray[j], i);
}
}
}
void display(char bitarray[][BITNSLOTS(MAX)], int n){
int i, j;
for (i=0; i<n; i++){
for (j=0; j<n; j++){
if (BITTEST(bitarray[i], j)){
printf("1");
}
else{
printf("0");
}
}
printf("\n");
}
printf("\n");
}
int check_sum(char* bitarray, int n){
int i;
int sum = 0;
for (i=0; i<n; i++){
if (BITTEST(bitarray, i)){
sum++;
}
}
return sum;
}
And here's <combination.h>, since I know someone's going to ask for it:
Code:
/* Prints out a combination like {1, 2} */
void printc(int comb[], int k) {
printf("{");
int i;
for (i = 0; i < k; ++i)
printf("%d, ", comb[i] + 1);
printf("\b\b}\n");
}
/*
next_comb(int comb[], int k, int n)
Generates the next combination of n elements as k after comb
comb => the previous combination ( use (0, 1, 2, ..., k) for first)
k => the size of the subsets to generate
n => the size of the original set
Returns: 1 if a valid combination was found
0, otherwise
*/
int next_comb(int comb[], int k, int n) {
int i = k - 1;
++comb[i];
while ((i >= 0) && (comb[i] >= n - k + 1 + i)) {
--i;
++comb[i];
}
if (comb[0] > n - k) /* Combination (n-k, n-k+1, ..., n) reached */
return 0; /* No more combinations can be generated */
/* comb now looks like (..., x, n, n, n, ..., n).
Turn it into (..., x, x + 1, x + 2, ...) */
for (i = i + 1; i < k; ++i)
comb[i] = comb[i - 1] + 1;
return 1;
}