Перемешать строку в C
Я пытаюсь сгенерировать случайные перестановки 80-символьной фиксированной строки в C. К моему большому разочарованию, в системе, над которой я работаю, отсутствует strfry (). Как мне лучше всего сгенерировать случайную перестановку этой строки? Так как это будет зациклено на прибл. 100000 раз производительность - это проблема.
Ответы 3
Просто используйте реализацию GLIBC с открытым исходным кодом, найденную Код Google.
char *
strfry (char *string)
{
static int init;
static struct random_data rdata;
size_t len, i;
if (!init)
{
static int state[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };
rdata.state = NULL;
__initstate_r (time ((time_t *) NULL), state, 8, &rdata);
init = 1;
}
len = strlen (string);
for (i = 0; i < len; ++i)
{
int32_t j;
char c;
__random_r (&rdata, &j);
j %= len;
c = string[i];
string[i] = string[j];
string[j] = c;
}
return string;
}
Возможно, вы захотите изменить конкретные типы данных GLIBC на что-то более общее.
Этот код использует Перемешивание Фишера-Йетса, который на самом деле довольно легко реализовать самостоятельно и очень эффективно.
Конрад, ты джентльмен и ученый! Я пробовал искать в Google Code, но искал такие вещи, как «рандомизировать строку в c», а не просто «strfry». Спасибо!
Неужели я единственный, кто думает, что создание и использование повторяющегося генератора случайных чисел требует красивого алгоритма и делает его уродливым?
Я хотел бы упомянуть, что strfry () - мое любимое имя для функции. Некоторое время это была floorf (), но потом я нашел strfry ().
void gcry_randomize (unsigned char * buffer, size_t length, enum gcry_random_level level)
Заполните буфер байтами случайной длины, используя случайное качество, определенное уровнем.
http://www.g10code.com/p-libgcrypt.html
Помимо того, что это проприетарная функция, которой, боюсь, я не указал, что я бы хотел избежать, это на самом деле не соответствует моей цели. Я пытаюсь создать случайную перестановку существующей строки, а не случайную строку. Частота символов важна.
создайте массив из 80 строк, поместите символ и случайное число в каждую строку массива, затем отсортируйте массив по случайным числам.
Восстановить строку из отсортированного массива.
Возможно, вы захотите изменить здесь собственное слово, иначе Столлман может достать вас со своей катаной. Подходящая замена может быть специфичной для GLIBC.