0

Поставлена такая задача.

Есть метод Collection getStringsForHashCode(int hashCode, int length) На входе hashCode и length - кол-во символов в получаемой строке.

Метод должен найти все комбинации char-ов у которых сумма hashCode равна параметру метода и кол-во этих char-ов должно быть равно параметру length у метода.

Пример:

getStringsForHashCode(18,3) = {“dad”, “bbc”, “maa”, …. }

Подскажите как такое сделать? я вообще в тупике.

Небольшие условия:

  • hashCode считается так: hashCode(s) = sum (s[i] * (i+1)) где s строка, а i чар строки.
  • дан метод int getInt(char c);
  • дан метод char getChar(int c);
  • значение int у char равно от 1 до 26. То бишь getInt('a') = 1 и т.д.

Я честно хз как лучше решить. надо случайным образом брать чар и пытаться склеивать с другими. Или же идти от обратного: найти сумму цифр и потом по полученным цифрам найти char.

Буду очень благодарен помощи)

4
  • решение в лоб перебор с отсечением если сумма становится больше хэша
    – Grundy
    25 сен 2018 в 18:57
  • @Grundy два чара собрать не проблема. Но вот если уже 3? то тут уже проблема. Рандомно собирать строку? Проблема не в подсчете хеша и его сравнении, а как собрать чары.
    – Tsyklop
    25 сен 2018 в 18:59
  • Не надо собирать строку, надо перебирать числа в уравнении. Количество переменных = length, значения переменных в интервале 1..26
    – Grundy
    25 сен 2018 в 19:02
  • @Grundy Интересно. мысли на счет самой реализации есть?
    – Tsyklop
    25 сен 2018 в 19:10

2 ответа 2

1

Как уже сказал Grundy это задача поиска целочисленных решений уравнения, лежащих в диапазоне 1..26.

1 * x1 + 2 * x2 + 3 * x3 + ... + n * xn = hash 

Можно считать её разновидностью задачи о наборе суммы - какие наборы из n монет с достоинством 1..26 дадут нужную сумму. Пример на Python.

По пределам отсечения: минимальное значение, которое можно набрать из n-1 первых символов, есть 1+2+3+4+..+n-1 = n*(n-1)/2, а максимальное - 26 умножить на это значение.

def getstr(hash, n, s):
    if (n==0):
        if (hash == 0):
            print(s)
        return

    for i in range(max(1, hash // n - 13 * (n-1)), min(26, (hash - (n * (n-1) //2))) // n + 1):
        getstr(hash - i * n, n - 1, chr(ord('a') + i - 1) + s)    

getstr(18, 3, "")

>>
maa
kba
ica
gda
eea
cfa
aga
jab
hbb
fcb
ddb
beb
gac
ebc
ccc
adc
dad
bbd
aae

Java code

class Ideone
{   
    public static void findStrs(int hash, int n, String s) {
    if (n==0) {
        System.out.println(s);
        return;
    }   

    int from = hash / n - 13 * (n-1);
    from = (from < 1)? 1: from;
    int to = (hash - (n * (n-1) / 2)) / n;
    to = (to > 26)? 26: to;

    for (int i = from; i<= to; i++){
        //System.out.println(i);
        findStrs(hash - i * n, n - 1, (char)(97 + i - 1) + s);   
    }
   return;
 } 
    public static void main (String[] args) throws java.lang.Exception
    {
       findStrs(18, 3, ""); // your code goes here
    }
}
9
  • а зачем на входе строка даётся?
    – Tsyklop
    26 сен 2018 в 5:46
  • Пустая строка как начальный параметр рекурсивной функции. На каждом уровне рекурсии к ней добавляется один символ, пока не соберётся полная валидная строка длиной n. Можно сделать отдельную функцию без этого аргумента, которая уже будет вызывать рекурсивную
    – MBo
    26 сен 2018 в 5:53
  • @Tsyklop Модифицировал пределы цикла, чтобы избавиться от лишних итераций.
    – MBo
    26 сен 2018 в 7:51
  • На "пиджин" Джаву перевёл
    – MBo
    26 сен 2018 в 8:49
  • откуда 13? это 26/2? что такое 97?
    – Tsyklop
    26 сен 2018 в 9:08
0

Для оптимизации перебора можно ограничить максимальное значение элемента строки. Строка "ааа" уже генерирует hash = 1+2+3 = 6. И для третьего элемента нет смысла добавлять что то больше (18-1-2)/3 = 5 т.е. "е". Перебор для больших lenght и малых hash будет существенно сокращен.
Например getStringsForHashCode(175, 18) даст следующую маску максимальных значений элементов, шестьдесят возможных вариантов и всего пять решений:

[5, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
eaaaaaaaaaaaaaaaaa
cbaaaaaaaaaaaaaaaa
acaaaaaaaaaaaaaaaa
babaaaaaaaaaaaaaaa
aaabaaaaaaaaaaaaaa
6
  • Один момент - хеш вычисляется не просто 1+2+3 а по формуле sum (s[i] * (i+1)) где s строка, а i чар строки.
    – Tsyklop
    26 сен 2018 в 5:44
  • конечно, это пример для строки "aaa" (a=1)*1 + (a=1)*2 + (a=1)*3 = 6, соответственно (a=1)*1 + (a=1)*2 + (е=5)*3 = 18, или я неверно понял как вычислять hash?
    – Mark
    26 сен 2018 в 5:57
  • Так поняли. (18-1-2)/3 = 5 что из этого 1, 2 и 3?
    – Tsyklop
    26 сен 2018 в 6:04
  • 1 и 2 это минимальные значения слогаемых от первого и второго элемента строки, а 3 - коэффициент для третьего. Т.е. максимальное значение для n-ого элемента можно вычислить как целую часть от выражения (hash - (минимальная сумма в хэше всех элементов строки кроме n)) / n
    – Mark
    26 сен 2018 в 6:15
  • так то хорошо, но вот как их вычислять?
    – Tsyklop
    26 сен 2018 в 6:27

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.