Revision as of 18:01, 22 April 2011 (view source) rosettacode>Kernigh (→‎{{header\|Ursala}}: Omit bc, dc.) ← Older edit		Revision as of 18:18, 22 April 2011 (view source) 95.246.199.78 (talk) (Removed some casts from C version) Newer edit →
Line 126: #define DEBUG void best_shuffle(const ~~unsigned~~ char* txt, ~~unsigned~~ char* result) { const ~~int~~size_t len = ~~(int)~~strlen(~~(char)~~txt); if (len == 0) return; Line 133: #ifdef DEBUG // txt and result must have the same length assert(len == ~~(int)~~strlen(~~(char)~~result)); #endif // how many of each character? ~~int~~size_t counts[UCHAR_MAX]; memset(counts, '\0', UCHAR_MAX * sizeof(int)); ~~int~~size_t fmax = 0; for (~~int~~size_t i = 0; i < len; i++) { counts[(unsigned char)txt[i]]++; const ~~int~~size_t fnew = counts[(unsigned char)txt[i]]; if (fmax < fnew) fmax = fnew; } assert(fmax > 0 && fmax <= len); // how long can our cyclic groups be?▼ const int grp = 1 + (len - 1) / fmax;▼ // how many of them are full length?▼ const int lng = 1 + (len - 1) % fmax;▼ // all character positions, grouped by character ~~int~~size_t ndx1 = malloc(~~(unsigned int)~~len sizeof(~~int~~size_t)); if (ndx1 == NULL) exit(EXIT_FAILURE); for (~~int~~size_t ch = 0, i = 0; ch < UCHAR_MAX; ch++) if (counts[ch]) for (~~int~~size_t j = 0; j < len; j++) if (ch == (unsigned char)txt[j]) { ndx1[i] = j; i++; Line 167 ⟶ 161: // regroup them for cycles ~~int~~size_t ndx2 = malloc(~~(unsigned int)~~len sizeof(~~int~~size_t)); if (ndx2 == NULL) exit(EXIT_FAILURE); for (~~int~~size_t i = 0, n = 0, m = 0; i < len; i++) { ndx2[i] = ndx1[n]; n += fmax; Line 178 ⟶ 172: } } ▲ // how long can our cyclic groups be? ▲ const ~~int~~size_t grp = 1 + (len - 1) / fmax; assert(grp > 0 && grp <= len); ▲ // how many of them are full length? ▲ const ~~int~~size_t lng = 1 + (len - 1) % fmax; assert(lng > 0 && lng <= len); // rotate each group for (~~int~~size_t i = 0, j = 0; i < fmax; i++) { ~~int~~const size_t first = ndx2[j]; ~~int~~const size_t glen = grp - (i < lng ? 0 : 1); for (~~int~~size_t k = 1; k < glen; k++) ndx1[j + k - 1] = ndx2[j + k]; ndx1[j + glen - 1] = first; Line 191 ⟶ 193: // result is original permuted according to our cyclic groups result[len] = '\0'; for (~~int~~size_t i = 0; i < len; i++) result[ndx2[i]] = txt[ndx1[i]]; Line 198 ⟶ 200: } void display(const char* txt1, const char* txt2) { ~~int~~const size_t len = ~~(int)~~strlen(txt1); assert(len == ~~(int)~~strlen(txt2)); int score = 0; for (~~int~~size_t i = 0; i < len; i++) if (txt1[i] == txt2[i]) score++; (void)printf("%s, %s, (%du)\n", txt1, txt2, score); } Line 211 ⟶ 213: char* data[] = {"abracadabra", "seesaw", "elk", "grrrrrr", "up", "a", "aabbbbaa", "", "xxxxx"}; const ~~int~~size_t data_len = sizeof(data) / sizeof(data[0]); for (~~int~~size_t i = 0; i < data_len; i++) { const ~~unsigned int~~size_t shuf_len = strlen(data[i]) + 1; ~~unsigned~~ char shuf[shuf_len]; #ifdef DEBUG memset(shuf, 0xFF, shuf_len * sizeof(~~unsigned~~ char)); shuf[shuf_len - 1] = '\0'; #endif best_shuffle(~~(unsigned char)~~data[i], shuf); display(data[i], ~~(char)~~shuf); }

Best shuffle: Difference between revisions

Best shuffle (view source)

Revision as of 18:18, 22 April 2011