Количество комбинаций чисел JavaScript?

Question

[gelix1267]

Как найти количество комбинаций чисел из строки от 4 до 12 символов. Условие: количество разделяющих точек - 3, символов между точками от 1 до 3, цифры местами не меняются. Например, Строка '1234'. Возможные комбинации: '1.2.3.4' Количество комбинаций = '1. Строка '12345'. Возможные комбинации: '1.2.3.45', '1.2.34.5', '1.23.4.5', '12.3.4.5' Количество комбинаций = '4'

Answer 1

[alekseyHunter]

1) Юзай формулу из теории вероятности, чтобы найти количество комбинаций.
2) Можешь рекурсией сделать. Выход из неё - количество вызовов равно количеству комбинаций. В хвост добавляй получившуюся строку.

Comments

[Griboks]

Юзай формулу из теории вероятности, чтобы найти количество комбинаций.

Из комбинаторики*

[Wataru]

Griboks, alekseyHunter,

Юзай формулу

А что, есть такая формула? Есть формула, если группы могут быть сколь угодно большими (ограничения снизу можно учесть). Формула, когда есть ограничения сверху мне неизвестна.

Answer 2

[Wataru]

В тупую можно подсчитать 2-мя вложенными циклами.

ans = 0;
for (i = 1; i <= 3; ++i) {
  for (j = 1; j <= 3; ++j) {
    mn = max(n - i - j - 3, 1);
    mx = n - i - j - 1;
    if (mn <= mx)
      ans += mx - mn + 1;
  }
}

Работает так - перебираем сколько символов в первом и втором блоке. После этого считаем, сколько минимально и максимально может быть символов в третьем блоке (оставляя на последний от 1 до 3 символов). Прибавляем к ответу количество возможных вариантов для длины третьего блока.

Но это если у вас параметры фиксированные (4 блока 1-3 символа). Если параметры могут меняться, то решение - динамическое программирование f(i,k) - сколько способов разбить первые i символов на k блоков.

База: f(0,0) = 1, f(0, k>0) = 0, f (i>0, 0) = 0;
Пересчет: f(i,k) = sum_{l=min_length...min(max_length, i)}(f(i-l,k-1)).
Ответ: f(n, num_blocks).

Answer 3

[Griboks]

Можно почитать учебник математики и составить на бумажке формулу, затем реализовать её не js.

Comments

[Wataru]

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

[Griboks]

wataru, просто это формула с несколькими параметрами.

[Wataru]

Griboks, Ну в студию же формулу! Хотя бы основную идею. Или хотя бы ключевые слова для поиска по мат.части.

[Griboks]

wataru, основаня идея: https://ru.wikipedia.org/wiki/Композиция_числа
Нам нужно найти композицию расположения точек в строке. Иными словами - найти композицию длины 3. Но композиция - немного не то, что нужно, но суть вы поняли.

[Wataru]

Griboks, Ну и? Я уже писал про разбиения числа. Композиция - обобщение разбиения, где порядок слагаемых важен.

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

[gelix1267]

Вот нашел схожее решение, но из другого языка. Как его преобразовать в JS?

public static void main(String[] args) {
    String input = "121212111";
    for (String ipAddress : generatePossibleIpAddresses(input, 3)) {
        System.out.println(ipAddress);
    }
}

public static ArrayList<String> generatePossibleIpAddresses(String ipAddress, int dot) {
    ArrayList<String> list = new ArrayList<String>();

    if (ipAddress == null || ipAddress.length() == 0) {
        return list;
    }

    if (dot == 0) {
        int i = Integer.parseInt(ipAddress);
        if (i < 256) {
            list.add(ipAddress);
        }
        return list;
    }

    for (int i = 1; i <= 3; i++) {
        int num = Integer.parseInt(ipAddress.substring(0, i));
        if (num < 256) {
            for (String str : generatePossibleIpAddresses(ipAddress.substring(i), dot - 1)) {
                list.add(num + "." + str);
            }
        }
    }
    return list;

[Griboks]

wataru, не могу сходу составить формулу, но это не означает, что это невозможно. Думаю как-то так:
1) найти количество комбинаций 4х групп символов.
2) разбить их по длине строки
3) таким образом получить формулу с параметром или несколько формул