Детерминированный способ генерировать массив символов

Question

Я хочу, чтобы сгенерировать случайный массив символов 20 символов со следующим свойством

SUM(a[i] * (i+1)) = GOAL 

я в настоящее время с помощью такой грубой силы подход, как показано ниже, но это занимает слишком много времени:

int LENGTH = 20; 
int GOAL = 14895; 

char allowed_chars[] = {48,49,50,51,52,53,54,55,56,57,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90}; 
char finalarray[LENGTH];  

srand(time(NULL)); 

while(1) 
{ 
    int sum = 0; 
    int i = 0; 
    for (i = 0; i < LENGTH; i++) 
    { 
     finalarray[i] = allowed_chars[rand() % (strlen(allowed_chars) + 1)]; 
     sum += (int)finalarray[i] * (i+1); 
    } 
    if (sum == GOAL) 
    { 
     printf("Found: %s", finalarray); 
     break; 
    } 
} 

это порождает выход, но есть ли детерминированный способ сделать это без грубой силы или ударить и попробовать?

Answer 1

Если ваша целевая сумма всегда одна и та же, вы можете найти одну строку, которая суммируется до вашей цели, а затем перетасовать ее так, чтобы взвешенная сумма не меняется.

Строка 20 Гс (ASCII 71) даст:

asc('G') · N · (N + 1)/2 = 14910 

Это превышает ваши цели на 15 и сокращение пятое письмо на 3 дает правильную строку "GGGGDGGGGGGGGGGGGGGG".

Теперь мы выполняем повторяющиеся изменения, каждый из которых поддерживает взвешенную сумму. Выберите две буквы по индексам (один) a и b. Мы можем сохранить взвешенную сумму, добавив кратное b в a и вычитая кратное a от b. Однако мы должны позаботиться о том, чтобы полученные значения были допустимыми. Если пару букв нельзя изменить, выберите новую.

#include <stdlib.h> 
#include <stdio.h> 
#include <time.h> 

#define GOAL 14895 

int isum(const char *str) 
{ 
    int i = 1; 
    int sum = 0; 

    while (*str) sum += i++ * *str++; 

    return sum; 
} 

int valid(int c) 
{ 
    if ('A' <= c && c <= 'Z') return 1; 
    if ('0' <= c && c <= '9') return 1; 
    return 0; 
} 

void scramble(char str[], int n, int m) 
{ 
    static const int delta[8] = {1, -1, 2, -2, 3, -3, 4, -4}; 

    while (m) { 
     int a = rand() % n; 
     int b = rand() % n; 
     int i; 

     int poss[8]; 
     int nposs = 0; 

     if (a == b) continue; 

     for (i = 0; i < 8; i++) { 
      int d = delta[i]; 
      int aa = str[a] + (b + 1)*d; 
      int bb = str[b] - (a + 1)*d; 

      if (valid(aa) && valid(bb)) { 
       poss[nposs++] = d; 
      } 
     } 

     if (nposs) { 
      int d = poss[rand() % nposs]; 

      str[a] += (b + 1)*d; 
      str[b] -= (a + 1)*d; 

      m--; 
     } 
    } 
} 

int main() 
{ 
    int l = 10; 

    srand(time(NULL)); 

    while (l--) { 
     char str[] = "GGGGDGGGGGGGGGGGGGGG"; 

     scramble(str, 20, 100); 
     printf("%s %d %d\n", str, isum(str), GOAL); 
    } 

    return 0; 
} 

Этот подход не очень чист, потому что он просто выполняет определенное количество изменений, а затем решает, что этого достаточно. Пробный запуск дает следующие строки, которые выглядят достаточно случайным образом, на первый взгляд:

SM1V52JF0VRIVVHT9B1Q 14895 14895 
LC478LEIF2YOV5E3MUQD 14895 14895 
R0AEHKDUPSGRIB27CCSM 14895 14895 
RL2IGA09N5WJZFY447VY 14895 14895 
EI43PYAEKUMVAADE2MPC 14895 14895 
1DP4ENJ6CLE3M1WUC2VW 14895 14895 
1042WA9TTJTVXRO20X3F 14895 14895 
MI4FDKO76SB59D9RWJLS 14895 14895 
SLK428RCBZ0YIDV6OJEF 14895 14895 
3IJ2TKJ9K4WVQBBYFGG4 14895 14895 

Answer 2

но есть ли какой-либо детерминированный способ сделать это без грубой силы или ударить и попробовать?

Если цель состоит в том, чтобы выбрать 20 из этих чисел, дающих сумму 14895, один способ сделать это было бы backtracking.

В основном вы начинаете добавлять значения, пока не находитесь выше цели или не используете более 20 чисел. В этом случае вычтите последнее значение и возьмите следующий. Сделайте это рекурсивно, пока вы не достигнете цели или не исчерпали все возможности.

Выбор случайных чисел, генерируемых неизвестным PRNG, является плохим подходом, поскольку он не может проверять все возможности и, следовательно, не может найти решение.

PS: Что вы хотите сделать? Это немного похоже на поиск хеш-коллизий для простой хэш-функции ...