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 [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
