Вопрос, заданный для случайной строки в эксклюзивном диапазоне.Решение ниже дает случайную строку в включающем диапазоне.Решение для широкого диапазона оказалось намного проще.Если нам нужен исключительный диапазон, мы просто отклоняем сгенерированную строку, если она попадает на границу диапазона, и генерируем другую случайную строку, пока она не окажется на границе диапазона.Для этого я добавил функцию randstrx().
Чтобы проиллюстрировать мое решение, мы рассмотрим строки десятичных цифр, то есть символы которых находятся в диапазоне C = [0 9].Например, 00127, 66501, 23, 1 и т. Д. Произвольной длины.Рассмотрим все строки заданной длины, например 4.Ясно, что порядок в этих строках существует.Например, для наших строк десятичных цифр строки длиной 4 упорядочены следующим образом: 0000, 0001, 0002, ..., 9999.
Для любой строкис заданной длиной легко вычислить строку той же длины, которая находится сразу после или до в порядке следования строк (мы игнорируем два граничных случая, когда нет строки после или до, поскольку они нам не понадобятся).Для наших строк десятичных цифр мы просто добавляем или вычитаем 1.Сложение и вычитание хорошо определены в любой основе, и числа могут состоять из любых символов, они не должны быть десятичными цифрами.Таким образом, это определяет, как добавить или вычесть 1 (или одну единицу) к любой строке заданной длины.Мы будем использовать это ниже.
Пусть S1 и S2 будут соответственно включающими нижнюю и верхнюю границы диапазона строк.У нас S1 <= S2;порядок определяется strcmp().L1 - это длина S1, а L2 - это длина S2.Мы хотим сгенерировать случайную строку S в диапазоне [S1 S2].S может иметь любую длину L <= M, где M - заданная константа.Все строки содержат символы в диапазоне C = [C1 C2].
[Шаг 1] Первый шаг состоит из генерации случайной длины L для S.В зависимости от значений S1 и S2 возможны не все длины.Действительно, S1 и S2 могут начинаться с одинаковой последовательности символов, например, в [123555 1237], S1 и S2 оба начинаются с 123.Предположим, что Sk длины K >= 0 является последовательностью равных символов в начале S1 и S2.Пусть S1 = Sk + T1 и S2 = Sk + T2, где T1 и T2 - последовательности символов, следующие за Sk в S1 и S2 соответственно, а + - оператор конкатенации строк.Пусть N1 >= 0 и N2 >= 0 будут длинами T1 и T2 соответственно.Мы рассматриваем 4 случая:
N1 = 0 и N2 = 0. В этом случае S1 = S2 = Sk, поэтому диапазон [S1 S2] содержит одну строку Skдлиной K.Таким образом, L = K является единственно возможным значением для L. N1 > 0 и N2 = 0. Этот случай невозможен, поскольку мы предполагаем, что S1 <= S2. N1 = 0 и N2 > 0. Очевидно, что L должно быть не менее K длины общей последовательности символов S1 и S2.Чтобы определить верхнюю границу L, нам нужно рассмотреть T2.Если T2 можно уменьшить, это означает, что мы можем генерировать строки произвольной длины, которые меньше S2.Например, если S1 = 123 и S2 = 123001, 12300099...9 меньше S2 (и > S1).Единственный случай, когда T2 не может быть уменьшен, это когда T2 = C1 + C1 + ... + C1.Например, если S1 = 123 и S2 = 123000, T2 не может быть уменьшено.Невозможно сгенерировать строку меньше S2 и длина которой больше L2.Таким образом, в этом случае L должен находиться в диапазоне [K L2]. N1 > 0 и N2 > 0. Рассмотрим верхнюю границу L.Мы знаем, что T1 < T2 и что первые символы T1 и T2 не равны, если бы они были такими, что первый общий символ был бы в общей стартовой последовательности Sk.Это означает, что T1 может быть увеличено или что T2 может быть уменьшено.Действительно, например, в наших строках десятичных цифр, единственное T1, которое не может быть увеличено, это 99...9.Если бы T1 было равно этому значению, это также должно было бы быть значением T2, но тогда T1 было бы равно T2, а T1 и T2 должно быть в Sk противоречие.Аналогичные рассуждения можно сделать для T2.Единственное T2, которое не может быть уменьшено, это T2 = 00...0, и поэтому T1 также должно быть 00...0, что поставило бы T1 и T2 в Sk, противоречие.Поскольку T1 можно увеличивать, а T2 можно уменьшать, мы можем генерировать случайные строки или произвольную длину больше T1 и меньше T2.Например, если S1 = 1231 и S2 = 1234, строки 12311...1 и 123399...9 попадают в диапазон [S1 S2].Рассмотрим нижнюю границу L.Любая строка длины K должна быть равна Sk, но, поскольку N1 > 0, Sk меньше S1.Таким образом, случайная строка не может иметь длину K.Однако легко показать, что он может иметь длину K + 1.Мы знаем, что первый символ T1[0] из T1 меньше, чем первый символ T2, и что его можно увеличивать.Итак, строка Sk с добавлением символа T1[0] + 1 является строкой длиной K + 1, которая больше S1.Это также меньше или равно S2.Действительно, если T2[0] = T1[0] + 1 и N2 = 1, то случайная строка равна S2.Добавление большего числа символов в S2 только увеличивает S2 случайной строки.Итак, L должно быть больше или равно K + 1.
Подводя итог, мы имеем:
- Для
N1 = 0 и N2 = 0, L = K. - Для
N1 > 0 и N2 > 0, L > K. - Для
N1 = 0 и N2 > 0, L = [K L2], если T2 = 00...0, в противном случае L >= K.
Учитывая вышеизложенное, мы генерируем случайное значение L для S.
[Шаг 2] Мы вычисляем наименьшую строку S1Lдлиной L, которая больше или равна S1.Если L >= L1, тогда к S1L добавляется S1 с достаточным количеством символов C1, чтобы его длина равнялась L.Например, если S1 равно 23906 и L равно 8, S1L = 23906000.С другой стороны, если L < L1, мы усекаем S1 до длины L и добавляем 1, как объяснено выше.Например, если S1 равно 23906, а L равно 3, S1L = 240.
[Шаг 3] Мы вычисляем наибольшую строку S2L длиныL, что меньше или равно S2.Если L > L2, то S2L равно S2 минус 1 (как описано выше) с добавлением достаточного количества символов C2, чтобы его длина равнялась L.Например, если S2 равно 23906 и L равно 8, S2L = 23905999.С другой стороны, если L < L2, мы усекаем S2 до длины L.Например, если S2 равно 23906 и L равно 3, S2L = 239.
[Шаг 4] Теперь у нас есть как самые маленькие, так и самые большие строкидлиной L, попадающими в диапазон [S1 S2], легко создать случайную строку длиной L в том же диапазоне.Мы просто устанавливаем S[i] на случайное значение символа в диапазоне [S1L[i] S2L[i]] для каждого i от 0 до L – 1.
Вот код C, который реализует решение.
#include "stdlib.h"
#include "string.h"
#include "assert.h"
#include "time.h"
/* Generate a random string in inclusive range [S1 S2] of maximum length M. */
/* S1, S2, and the returned random string have their characters in the range [C1 C2]. */
/* Returns NULL if no string of maximum length M exists in [S1 S2]. */
char * randstr(char * S1, char * S2, int M, int C1, int C2)
{
/* Validate inputs. */
if (S1 == NULL || S2 == NULL || *S1 == 0 || *S2 == 0) return NULL;
if (strcmp(S1, S2) > 0) return NULL;
if (C1 > C2) return NULL;
/* Lengths of input strings. */
int L1 = strlen(S1);
int L2 = strlen(S2);
/* Length of longest common starting sequence of S1 and S2. */
int K = 0;
for (; K < L1 && K < L2 && S1[K] == S2[K]; K++);
/* Generate length of random string S. */
int L;
int N1 = L1 - K;
int N2 = L2 - K;
if (N1 == 0 && N2 == 0)
{
/* L = K */
if (M < K) return NULL;
L = K;
}
else if (N1 > 0 && N2 > 0)
{
/* L = [K + 1 M] */
if (M < K + 1) return NULL;
L = (rand() % (M - (K + 1) + 1)) + K + 1;
}
else if (N1 == 0 && N2 > 0)
{
char * T2 = S2 + K;
while (*T2 > 0 && *T2 == C1)
T2++;
if (*T2 == 0) /* T2 = C1 + C1 + ... + C1 */
{
/* L = [K L2] */
if (M < K) return NULL;
if (M < L2)
L = (rand() % (M - K + 1)) + K;
else
L = (rand() % (L2 - K + 1)) + K;
}
else
{
/* L >= K */
if (M < K) return NULL;
L = (rand() % (M - K + 1)) + K;
}
}
/* Compute smallest string S1L of length L that is greater than S1. */
char * S1L = (char*)malloc(sizeof(char) * (L + 1));
S1L[L] = 0;
if (L >= L1)
{
for (int i = 0; i < L1; S1L[i] = S1[i++]); /* Copy S1 into S1L. */
for (int i = L1; i < L; S1L[i++] = C1); /* Append C1 characters. */
}
else /* L < L1 */
{
for (int i = 0; i < L; S1L[i] = S1[i++]); /* Set S1L to S1 truncated to length L. */
for (int i = L - 1; i >= 0; i--) /* Increment S1L. */
{
if (S1L[i] < C2)
{
S1L[i]++;
break;
}
else
S1L[i] = C1;
}
}
/* Compute largest string S2L of length L that is less than S2. */
char * S2L = (char*)malloc(sizeof(char) * (L + 1));
S2L[L] = 0;
if (L > L2)
{
for (int i = 0; i < L2; S2L[i] = S2[i++]); /* Copy S2 into S2L. */
for (int i = L2; i < L; S2L[i++] = C2); /* Append C2 characters. */
for (int i = L2 - 1; i >= 0; i--) /* Decrement copy of S2. */
{
if (S2L[i] > C1)
{
S2L[i]--;
break;
}
else
S2L[i] = C2;
}
}
else /* L < L2 */
{
for (int i = 0; i < L; S2L[i] = S2[i++]); /* Set S2L to S2 truncated to length L. */
}
/* Generate random string S of length L in range [S1L S2L]. */
char * S = (char*)malloc(sizeof(char) * (L + 1));
S[L] = 0;
for(int i = 0; i < L; i++)
S[i] = (rand() % (S2L[i] - S1L[i] + 1)) + S1L[i];
free(S1L);
free(S2L);
return S;
}
/* Generate a random string in exclusive range (S1 S2) of maximum length M. */
/* S1, S2, and the returned random string have their characters in the range [C1 C2]. */
/* Returns NULL if no string of maximum length M exists in (S1 S2). */
char * randstrx(char * S1, char * S2, int M, int C1, int C2)
{
/* If S1 + 1 >= S2, then no random string exists in (S1 S2). */
int L1 = strlen(S1);
char * S = (char*)malloc(sizeof(char) * (L1 + 1));
strcpy(S, S1);
for (int i = L1 - 1; i >= 0; i--)
{
if (S[i] < C2)
{
S[i] += 1;
break;
}
}
if (strcmp(S, S2) >= 0)
{
free(S);
return NULL;
}
do
{
free(S);
S = randstr(S1, S2, M, C1, C2);
}
while (strcmp(S, S1) == 0 || strcmp(S, S2) == 0);
return S;
}
int main()
{
srand((unsigned int)time(NULL)); // initialisation de rand
char * s;
/* N1 == 0, N2 == 0, K == 1 */
s = randstr("0", "0", 10, '0', '9');
assert(strcmp(s, "0") == 0);
/* N1 == 0, N2 == 0, K == 4 */
s = randstr("1210", "1210", 10, '0', '9');
assert(strcmp(s, "1210") == 0);
/* N1 == 0, N2 == 1, K == 3, T2 == 0 */
s = randstr("121", "1210", 3, '0', '9');
assert(strcmp(s, "121") == 0);
/* N1 == 0, N2 == 1, K == 3, T2 == 0 */
s = randstr("121", "1210", 4, '0', '9');
assert(strcmp(s, "121") == 0 || strcmp(s, "1210") == 0);
/* N1 == 1, N2 == 1, K == 3, T2 != 0 */
s = randstr("1210", "1211", 4, '0', '9');
assert(strcmp(s, "1210") == 0 || strcmp(s, "1211") == 0);
/* N1 == 1, N2 == 1, K == 3, T2 != 0 */
s = randstr("1210", "1211", 5, '0', '9');
assert(strcmp(s, "1210") >= 0 || strcmp(s, "1211") <= 0);
/* N1 == 4, N2 == 1, K == 0, T2 != 0 */
s = randstr("0004", "1", 25, '0', '9');
assert(strcmp(s, "0004") >= 0 || strcmp(s, "1") <= 0);
return 0;
}