2011-03-21

Talking to my father this weekend, he asked me a question in a manner in which I'm unaccustomed to thinking.

Imagine you have an eight-variable system. In his case, it was combinations of ethical principles. How many possible combinations are there?

At first, I immediately jumped for the obvious Combination and Permuatation formulae, but upon further inspection I realized I should have been thinking discretely and put my Computer Science to good use!

I wrote this paper both because it was a fun brainteaser and also to showcase SVG and MathML capabilities in Firefox. And I always relish an excuse to write C ;)

This page is only tested in Mozilla Firefox. At time of writing, this page does not correctly render in Chrome or Internet Explorer.

Imagine you have an eight-variable system. In his case, it was combinations of ethical principles. How many possible combinations are there?

At first, I immediately jumped for the obvious Combination and Permuatation formulae, but upon further inspection I realized I should have been thinking discretely and put my Computer Science to good use!

I wrote this paper both because it was a fun brainteaser and also to showcase SVG and MathML capabilities in Firefox. And I always relish an excuse to write C ;)

This page is only tested in Mozilla Firefox. At time of writing, this page does not correctly render in Chrome or Internet Explorer.

Let's make things easier with triangles.

You have three vertices, we'll call them 1, 2, and 3. There are eight possible edge combinations:

These possibilities can be expressed in tabular format (think truth tables):

I've deliberately used '0' and '1' to demonstrate that these can be expressed as a series from 000 to 111 (binary 7).

You'll notice that there are 8 possible combinations for 3 vertices. Having noticed $${2}^{3}=8$$ I*postulate*, but will not *prove*, any given polygon of *v* vertices will have *C*(*v*)
potential vertex connections where
$$C(v)=\sum _{i=1}^{v-1}(i)=1+2+\mathrm{...}+v-1=p$$
Given *p* possible connections between *v* vertices, the possible outcomes, *O*(*p*), will be simply
$$O(p)={2}^{\mathrm{p}}$$

You have three vertices, we'll call them 1, 2, and 3. There are eight possible edge combinations:

These possibilities can be expressed in tabular format (think truth tables):

1&2 |
1&3 |
2&3 |

0 | 0 | 0 |

0 | 0 | 1 |

0 | 1 | 0 |

0 | 1 | 1 |

1 | 0 | 0 |

1 | 0 | 1 |

1 | 1 | 0 |

1 | 1 | 1 |

You'll notice that there are 8 possible combinations for 3 vertices. Having noticed $${2}^{3}=8$$ I

Ready for some C? This is the code I used to generate the above triangles. It isn't quite extensible enough to generate
Octagons in it's current form, but with a small (and I do mean small) amount of tweaking you could generate arbitrarily large numbers of SVG images
for whatever number of vertices you chose (source, 32-bit Windows EXE).
*O*(*C*(*v*)) possibile polygons.

#include <stdio.h> #include <math.h> #include <stdlib.h> const char * baseSvgFull = "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n\ <!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\" \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n\ <svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\" width=\"110px\" height=\"75px\">\n\ <circle cx=\"55\" cy=\"10\" r=\"5\" stroke=\"black\" stroke-width=\"2\" fill=\"black\" />\n\ <circle cx=\"10\" cy=\"65\" r=\"5\" stroke=\"black\" stroke-width=\"2\" fill=\"black\" />\n\ <circle cx=\"100\" cy=\"65\" r=\"5\" stroke=\"black\" stroke-width=\"2\" fill=\"black\" />"; const char * baseSvg = "<svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\" width=\"110px\" height=\"75px\">\n\ <circle cx=\"55\" cy=\"10\" r=\"5\" stroke=\"black\" stroke-width=\"2\" fill=\"black\" />\n\ <circle cx=\"10\" cy=\"65\" r=\"5\" stroke=\"black\" stroke-width=\"2\" fill=\"black\" />\n\ <circle cx=\"100\" cy=\"65\" r=\"5\" stroke=\"black\" stroke-width=\"2\" fill=\"black\" />"; const char * endSvg = "</svg>"; const char * lines[] = { " <line x1=\"55\" y1=\"10\" x2=\"10\" y2=\"65\" style=\"stroke:rgb(99,99,99);stroke-width:5\" />", " <line x1=\"55\" y1=\"10\" x2=\"100\" y2=\"65\" style=\"stroke:rgb(99,99,99);stroke-width:5\" />", " <line x1=\"100\" y1=\"65\" x2=\"10\" y2=\"65\" style=\"stroke:rgb(99,99,99);stroke-width:5\" />" }; const unsigned short VERTICES = 3; unsigned short CONNECTIONS; unsigned short POSSIBILITIES; unsigned short connections (unsigned short n); /* builds all possible triangles */ int main(int argc, char *argv[]) { unsigned short x, bitop, mask; CONNECTIONS = connections(VERTICES); POSSIBILITIES = (unsigned short) pow(2, CONNECTIONS); for (x = 0; x < POSSIBILITIES; x++) { printf("%s\n", baseSvg); for (bitop = 0; bitop < CONNECTIONS; bitop++) { mask = ((unsigned short) pow(2, bitop)) & x; if (mask > 0) { printf("%s\n", lines[bitop]); } } printf("%s\n\n", endSvg); } return(EXIT_SUCCESS); } unsigned short connections (unsigned short n) { unsigned short x = 0; while (n > 0) x += --n; return(x); }Notice the use of bitwise operations to detect if the bit in position relevant to line is turned on or not. I thought that was a pretty cool and very efficient means of handling this task. I don't really see a better way to accomplish this if you're going to build all

So to answer my fathers' original question, how many possible combinations are there in an eight-variable system, I calculate:
$$C(8)=\sum _{i=1}^{7}(i)=1+2+3+4+5+6+7=28$$
which means
$$O(\mathrm{28})={2}^{28}=\mathrm{268,435,456}$$
**268,435,456** figures can be drawn with eight vertices, where each vertex can touch any or every vertex, except itself!
If you were to make a video showing all these possibilities at 24 frames per second, where each *frame* shows
one possibility for just 1/24th of a second, that video would last over 129 *days*! Isn't math awesome?

Now, if you really, REALLY want to fill up your hard drive in a hurry, here is a Windows 32-bit executable and source code that will generate all these possible octagons. Even at <2 KB per SVG file you'll still need half a terabyte for all this stuff.

Now, if you really, REALLY want to fill up your hard drive in a hurry, here is a Windows 32-bit executable and source code that will generate all these possible octagons. Even at <2 KB per SVG file you'll still need half a terabyte for all this stuff.

The purpose of this paper was to:

MathML is really cool. I used Mozilla's MathML Torture Test suite to write most of the MathML shown on this paper. It serves as a nice quick reference guide for common operations you'll want. On the downside, it doesn't validate W3C and I'm not motivated enough to fix it. Here's good presentation on MathML.

SVG is really cool, really easy to script, and even easier to use in XHTML than I expected. Now that Firefox fully supports SVG I'm planning to use it a lot more.

The code itself isn't the most brilliant thing I've ever written, but it's concise, uses bitwise operations (which are always fun), and, to my knowledge, mathematically sound. Dijkstra himself wouldn't argue with that!

Syntax highlighting provided by Oleg Parashchenko.

- Answer my father's question.
- Learn some MathML.
- Play with SVG.
- Write something awesome in C.

MathML is really cool. I used Mozilla's MathML Torture Test suite to write most of the MathML shown on this paper. It serves as a nice quick reference guide for common operations you'll want. On the downside, it doesn't validate W3C and I'm not motivated enough to fix it. Here's good presentation on MathML.

SVG is really cool, really easy to script, and even easier to use in XHTML than I expected. Now that Firefox fully supports SVG I'm planning to use it a lot more.

The code itself isn't the most brilliant thing I've ever written, but it's concise, uses bitwise operations (which are always fun), and, to my knowledge, mathematically sound. Dijkstra himself wouldn't argue with that!

Syntax highlighting provided by Oleg Parashchenko.

There are doubters everywhere, so I produce an additional example.

Four vertices:

In case you're wondering, that's: $$C(4)=\sum _{i=1}^{3}(i)=1+2+3=6$$ Six possible connections between these points, meaning there are: $$O(6)={2}^{6}=64$$ 64 possible outcomes with four vertices (count them up, there really are 64 figures above). Here's the code I used to build these SVG's (source, Windows 32-bit EXE):## Feedback

## Generic Algorithm

Four vertices:

In case you're wondering, that's: $$C(4)=\sum _{i=1}^{3}(i)=1+2+3=6$$ Six possible connections between these points, meaning there are: $$O(6)={2}^{6}=64$$ 64 possible outcomes with four vertices (count them up, there really are 64 figures above). Here's the code I used to build these SVG's (source, Windows 32-bit EXE):

#include <stdio.h> #include <math.h> #include <stdlib.h> // If you want a standalone file that can render use this. I was surprised you can use the <svg></svg> tag in Firefox! const char * baseSvgFull = "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n\ <!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\" \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n\ <svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\" width=\"100px\" height=\"100px\">\n\ <circle cx=\"15\" cy=\"15\" r=\"5\" stroke=\"black\" stroke-width=\"2\" fill=\"black\" />\n\ <circle cx=\"85\" cy=\"15\" r=\"5\" stroke=\"black\" stroke-width=\"2\" fill=\"black\" />\n\ <circle cx=\"15\" cy=\"85\" r=\"5\" stroke=\"black\" stroke-width=\"2\" fill=\"black\" />\n\ <circle cx=\"85\" cy=\"85\" r=\"5\" stroke=\"black\" stroke-width=\"2\" fill=\"black\" />\n"; const char * baseSvg = "<svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\" width=\"100px\" height=\"100px\">\n\ <circle cx=\"15\" cy=\"15\" r=\"5\" stroke=\"black\" stroke-width=\"2\" fill=\"black\" />\n\ <circle cx=\"85\" cy=\"15\" r=\"5\" stroke=\"black\" stroke-width=\"2\" fill=\"black\" />\n\ <circle cx=\"15\" cy=\"85\" r=\"5\" stroke=\"black\" stroke-width=\"2\" fill=\"black\" />\n\ <circle cx=\"85\" cy=\"85\" r=\"5\" stroke=\"black\" stroke-width=\"2\" fill=\"black\" />\n"; const char * endSvg = "</svg>"; const char * lines[] = { " <line x1=\"15\" y1=\"15\" x2=\"15\" y2=\"85\" style=\"stroke:rgb(99,99,99);stroke-width:5\" />", " <line x1=\"15\" y1=\"15\" x2=\"85\" y2=\"15\" style=\"stroke:rgb(99,99,99);stroke-width:5\" />", " <line x1=\"15\" y1=\"15\" x2=\"85\" y2=\"85\" style=\"stroke:rgb(99,99,99);stroke-width:5\" />", " <line x1=\"85\" y1=\"15\" x2=\"15\" y2=\"85\" style=\"stroke:rgb(99,99,99);stroke-width:5\" />", " <line x1=\"85\" y1=\"15\" x2=\"85\" y2=\"85\" style=\"stroke:rgb(99,99,99);stroke-width:5\" />", " <line x1=\"15\" y1=\"85\" x2=\"85\" y2=\"85\" style=\"stroke:rgb(99,99,99);stroke-width:5\" />" }; const unsigned short VERTICES = 4; unsigned short CONNECTIONS; unsigned short POSSIBILITIES; unsigned short connections (unsigned short n); /* modified to build a square instead of a triangle */ int main(int argc, char *argv[]) { unsigned short x, bitop, mask; CONNECTIONS = connections(VERTICES); POSSIBILITIES = (unsigned short) pow(2, CONNECTIONS); for (x = 0; x < POSSIBILITIES; x++) { printf("%s\n", baseSvg); for (bitop = 0; bitop < CONNECTIONS; bitop++) { mask = ((unsigned short) pow(2, bitop)) & x; if (mask > 0) { printf("%s\n", lines[bitop]); } } printf("%s\n\n", endSvg); } return(EXIT_SUCCESS); } unsigned short connections (unsigned short n) { unsigned short x = 0; while (n > 0) x += --n; return(x); }

I was pleasantly surprised by feedback I've received from friends and family. Laura Stephens validated my mathematical logic,
Mac Mollison
validated my code (and even proposed improvements), and
Thomas Holden proposed an interactive
means of demonstration via animation in LÖVE with LUA programming. Thank you all for your support!

To write a generic algorithm capable of producing all possible polygons given arbitrary number of vertices at the command line, I had to come up with
yet another formula. This one is fairly straightfoward. To get coordinates for the polygon's vertices, given radius *R*, center point
(*C*_{x}, *C*_{y}), then all you need to do is iterate function *V*(*index*, *number of vertices*) where:
$$V(\mathrm{index},\mathrm{limit},R,{C}_{\mathrm{x}},{C}_{\mathrm{y}})=(Rcos\frac{2\pi \mathrm{index}}{\mathrm{limit}}+{C}_{\mathrm{x}},Rsin\frac{2\pi \mathrm{index}}{\mathrm{limit}}+{C}_{\mathrm{y}})$$
Again, I don't have a proof for this, but based on my trigonometric scribblings on scrap paper I'm sure it's good to go.

The software required a rethinking, and I'm not 100% satisfied with it because of some floating-point arithmetic-related rounding errors, but overall it handles fairly well. Source and 32-bit Windows EXE are available and I've also uploaded some test pages: Triangles, Squares, and Pentagons. A review of the XHTML source will reveal the rounding error that is taking place. I do not know an effective means of correcting this.

The software required a rethinking, and I'm not 100% satisfied with it because of some floating-point arithmetic-related rounding errors, but overall it handles fairly well. Source and 32-bit Windows EXE are available and I've also uploaded some test pages: Triangles, Squares, and Pentagons. A review of the XHTML source will reveal the rounding error that is taking place. I do not know an effective means of correcting this.

#define _USE_MATH_DEFINES #include <stdio.h> #include <math.h> #include <stdlib.h> #include <limits.h> #include <string.h> const char * baseSvgFull = "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"yes\"?>\n\ <!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\" \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n\ <svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\" width=\"100px\" height=\"100px\">\n"; const char * baseSvg = "<svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\" width=\"100px\" height=\"100px\">\n"; const char * endSvg = "</svg>"; const char * usage = "Usage: polygon.exe [decimal # of vertices, must be > 2]\n"; const unsigned short RADIUS = 35; // radius of the "circle" around which we build a polygon. const unsigned short CIRCLE_X = 50; // center of circle in +X,+Y cartesian plane. const unsigned short CIRCLE_Y = 50; // center of circle in +X,+Y cartesian plane. char ** printable_vertices; char ** printable_segments; unsigned long sum_connections (const unsigned long n); char * vertex (const unsigned long index, const unsigned long total, const unsigned short radius, const unsigned short cx, const unsigned short cy, unsigned short * vx, unsigned short * vy); char * segment (const unsigned short x1, const unsigned short y1, const unsigned short x2, const unsigned short y2); void build_strings(const unsigned long vertices, const unsigned long connections, const unsigned short radius, const unsigned short cx, const unsigned short cy); void onClose(void); /* modified to accept command line arguments for arbitrary number of sides */ int main(int argc, char *argv[]) { /* figure = sequential ID for the figure we're drawing edge = sequential ID for the edge of the figure, which we may or may not draw */ unsigned long figure, edge, vertices, connections, possibilities; atexit(onClose); if (argc > 1) { vertices = strtoul(argv[1], NULL, 10); } else { fprintf(stderr, "%s", usage); return(EXIT_SUCCESS); } if (vertices < 3) { fprintf(stderr, "%s", usage); return(EXIT_FAILURE); } /* overflow protection provided in method; 0 is a valid result */ connections = sum_connections(vertices); build_strings(vertices, connections, RADIUS, CIRCLE_X, CIRCLE_Y); /* calculate how many possible figures there are, but first check that this won't cause overflow */ if (log(ULONG_MAX) / log(2) < connections) { fprintf(stderr, "Fatal error: <possibilities> overflow detected.\n"); exit(EXIT_FAILURE); } possibilities = (unsigned long) pow(2, connections); #ifdef DEBUG fprintf(stderr, "vertices=%d\nconnections=%d\npossibilities=%d\n", vertices, connections, possibilities); #endif /* iterate over total possible figures */ for (figure = 0; figure < possibilities; figure++) { printf("%s", baseSvg); unsigned long print_vertices; for (print_vertices = 0; print_vertices < vertices; print_vertices++) { printf("%s", printable_vertices[print_vertices]); } /* in this figure, consider each potential edge */ for (edge = 0; edge < connections; edge++) { /* is the edge's bit a 1 in the figure ID? */ if ((unsigned short) (1 << edge) & figure) { /* if so, draw it. */ printf("%s", printable_segments[edge]); } } printf("%s\n\n", endSvg); } return(EXIT_SUCCESS); } /* Summation calculates how many connections are possible given polygon of vertices n. Terminates program if overflow unavoidable. */ unsigned long sum_connections (unsigned long n) { unsigned long x = 0; while (n > 0) { if (x > (x + --n)) { fprintf(stderr, "Fatal error: <connections> overflow detected.\n"); exit(EXIT_FAILURE); } else { x += n; } } return(x); } /* Calculates the vertex location given parameters. Saves x and y position in vx and vy. Returns string representation formatted for SVG. */ char * vertex (const unsigned long index, const unsigned long total, const unsigned short radius, const unsigned short cx, const unsigned short cy, unsigned short * vx, unsigned short * vy) { * vx = (unsigned short) (ceil(radius * cos(2.0f * M_PI * (double)index / (double)total)) + (double)cx); * vy = (unsigned short) (ceil(radius * sin(2.0f * M_PI * (double)index / (double)total)) + (double)cy); char * vertex = calloc(128, sizeof(char)); if (sprintf(vertex, " <circle cx=\"%d\" cy=\"%d\" r=\"5\" stroke=\"black\" stroke-width=\"2\" fill=\"black\" />\n", * vx, * vy) < 0) { fprintf(stderr, "Error creating string for vertex (%d, %d).\n", * vx, * vy); perror("sprintf"); return(NULL); } return(vertex); } /* Calculates the line segment given two vertices. Returns string representation formatted for SVG. */ char * segment (const unsigned short x1, const unsigned short y1, const unsigned short x2, const unsigned short y2) { char * segment = calloc(128, sizeof(char)); // 128 should be "good enough" for most applications. if (sprintf(segment, " <line x1=\"%d\" y1=\"%d\" x2=\"%d\" y2=\"%d\" style=\"stroke:rgb(99,99,99);stroke-width:5\" />\n", x1, y1, x2, y2) < 0) { fprintf(stderr, "Error creating string for segment (%d, %d)->(%d, %d).\n", x1, y1, x2, y2); perror("sprintf"); return(NULL); } return(segment); } /* Create the vertices, in both integer and string formats. Caching them like this should be considerably more efficient than creating a new formatted string with each pass. */ void build_strings(const unsigned long vertices, const unsigned long connections, const unsigned short radius, const unsigned short cx, const unsigned short cy) { unsigned short vertex_x[vertices]; unsigned short vertex_y[vertices]; char * vertex_s[vertices]; char * segment_s[connections]; unsigned short index_vertex, index_dst, index_segment; /* create a string representation of each vertex */ for (index_vertex = 0; index_vertex < vertices; index_vertex++) { vertex_s[index_vertex] = vertex(index_vertex, vertices, radius, cx, cy, (unsigned short *) &vertex_x[index_vertex], (unsigned short *) &vertex_y[index_vertex]); #ifdef DEBUG fprintf(stderr, "%s", vertex_s[index_vertex]); #endif } /* create a string representation of each possible edge */ index_segment = 0; for (index_vertex = 0; index_vertex < vertices - 1; index_vertex++) { for (index_dst = index_vertex + 1; index_dst < vertices; index_dst++) // ex: 1-2 1-3 2-3...the loop looks trickier than it is. { segment_s[index_segment++] = segment(vertex_x[index_vertex], vertex_y[index_vertex], vertex_x[index_dst], vertex_y[index_dst]); #ifdef DEBUG fprintf(stderr, "%s", segment_s[index_segment-1]); #endif } } printable_vertices = malloc(sizeof(vertex_s)); memcpy(printable_vertices, vertex_s, sizeof(vertex_s)); printable_segments = malloc(sizeof(segment_s)); memcpy(printable_segments, segment_s, sizeof(segment_s)); } /* free up the allocated strings when application closes */ void onClose(void) { free(printable_vertices); free(printable_segments); }