Best shuffle: Difference between revisions

===Version with random result===

<lang C>#include <stdio.h>

#include <stdlib.h>

#include <string.h>

typedef struct letter_group_t {

char c;

int count;

} *letter_p;

struct letter_group_t all_letters[26];

letter_p letters[26];

int count_letters(char *s)

{

int i, c;

for (i = 0; i < 26; i++) {

all_letters[i].count = 0;

all_letters[i].c = i + 'a';

}

while (*s != '\0') {

i = *(s++);

/* don't want to deal with bad inputs */

if (i < 'a' || i > 'z') {

fprintf(stderr, "Abort: Bad string %s\n", s);

exit(1);

}

all_letters[i - 'a'].count++;

}

for (i = 0, c = 0; i < 26; i++)

if (all_letters[i].count)

letters[c++] = all_letters + i;

return c;

}

int least_overlap, seq_no;

char out[100], orig[100], best[100];

void permutate(int n_letters, int pos, int overlap)

{

int i, ol;

if (pos < 0) {

// printf("%s: %d\n", out, overlap);

if (overlap < least_overlap) {

least_overlap = overlap;

seq_no = 0;

}

if ( (double)rand() / (RAND_MAX + 1.0) * ++seq_no <= 1)

strcpy(best, out);

return;

}

for (i = 0; i < n_letters; i++) {

if (!letters[i]->count) continue;

out[pos] = letters[i]->c;

letters[i]->count --;

ol = (letters[i]->c == orig[pos]) ? overlap + 1 : overlap;

if (ol <= least_overlap)

permutate(n_letters, pos - 1, ol);

letters[i]->count ++;

}

return;

}

void do_string(char *str)

{

least_overlap = strlen(str);

strcpy(orig, str);

seq_no = 0;

out[least_overlap] = '\0';

least_overlap ++;

permutate(count_letters(str), least_overlap - 2, 0);

printf("%s -> %s, overlap %d\n", str, best, least_overlap);

}

int main()

{

srand(time(0));

do_string("abracadebra");

do_string("grrrrrr");

do_string("elk");

do_string("seesaw");

do_string("");

return 0;

}</lang>Output<lang>abracadebra -> edbcarabaar, overlap 0

grrrrrr -> rrgrrrr, overlap 5

elk -> kel, overlap 0

seesaw -> ewsesa, overlap 0

-> , overlap 0</lang>