While thinking about sorting chars by radix 2 I realized you can get a very simple algorithm for putting the characters in Hamming order rather than ascending order. This was so appealing that I coded it up and it works very nicely.
It makes 8 passes (for w=8 bit chars) over a string to put it in order. It needs a buffer of length equal to the string. #include <stdio.h> #include <stdlib.h> void hamming_order(char *str, int len) { char *tmp = malloc(len); char *s = str, *d = tmp, *t; int bit, is, id0, id1; for (bit = 1; bit & 0xFF; bit <<= 1, t = s, s = d, d = t) for (is = id0 = 0, id1 = len; is < len; ++is) if (s[is] & bit) d[--id1] = s[is]; else d[id0++] = s[is]; free(tmp); } int main(void) { char org[] = "No man is an island, entire of itself;" "every man is a piece of the continent, a part of the main;" "if a clod be washed away by the sea, Europe is the less," "as well as if a promontory were, " "as well as if a manor of thy friends or of thine own were; " "any man's death diminishes me, because I am involved in mankind, " "and therefore never send to know for whom the bell tolls; " "it tolls for thee."; char prm[] = "rffe sd ns b soo,tno err r sraie,ehfnin a,senm tfp " "a nsomyateidhmt eomnnswnrnierho cedlmdlnrlnoi nld y ,E s rt " "mopm wah ln y in i aheiioa tallcshaw vflao ldevmheb r nreseho " "tabpr snn nmn weew ,o.se,ynfst raolhnceeneed is dleik o ;urdh " "a elfa;eesoffetnukf rah wt f os lietito f earas osemepio'eeaIw " "t,d; e e aonit c a tea it abhyteef ehte eoitNoo;lwaaai aamsve " "ssiwt yiilv o"; hamming_order(org, sizeof org - 1); hamming_order(prm, sizeof prm - 1); printf("original:%s\n\npermutation:%s\nthey are %s", org, prm, strcmp(org, prm) ? "different" : "the same"); return 0; } --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---