Количество комбинаций чисел при данных условиях

Question

Как найти количество комбинаций чисел из строки от 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

Рекурсивный подсчёт. n - длина строки, k - количество частей, m - максимум между точками.

Сначала уменьшаем размерность задачи, вычтя 1 из m и всех частей (т.о. пустые части возможны).

Потом подставляем возможные размеры очередной части и рекурсивно решаем для оставшихся частей

Код (спасибо CbIPoK2513 за перевод с Python) выдаёт 19 - проверяем:
6 перестановок 3 3 2 2
12 перестановок 3 2 2 1
1 вариант 2 2 2 2

function cp(n, k, m) {
  if (k == 0)
    if (n == 0) return 1;
    else return 0;
  res = 0;
  for (let i = 0; i < Math.min(n + 1, m + 1); i++)
    res += cp(n - i, k - 1, m);
  return res;
}

function countparts(n, k, m) {
  return cp(n - k, k, m - 1);
}

console.info(countparts(8, 4, 3));

Answer 2

Самый простой способ - алгоритм перебора с возвратом.

Фишка в том, чтобы перебрать все состояния и отобрать из них те, которые подходят под условия задачи. Состояние здесь - массив вида [1,1,0,1,...], где 1 - точка стоит, и 0 - точка не стоит для каждого "паза" между символами.

const data = "0123456789";
const points_number = 3;
const data_length = data.length - 1;

const max_state_index = 1;
// 2 states: 0 - there isn't a point, 1 - there is a point
const EMPTY_SPACE_STATE_INDEX = 0;
const POINT_STATE_INDEX = 1;

let results = [];

function loop(index, limitIndex, loopLimit, currentState, callback) {
    for (let j = 0; j <= loopLimit; ++j) {
        currentState[index] = j;
        if (index !== limitIndex - 1) {
            loop(index + 1, limitIndex, loopLimit, currentState, callback);
        } else {
            callback(currentState);
        }
    }
}

function startLoop(limitIndex, loopLimit, callback) {
    loop(0, limitIndex, loopLimit, [], callback);
}

function isCorrectState(state) {
    let point_counter = 0;
    let last_point_index = -1;
    for (let shard of state) {
        if (shard === POINT_STATE_INDEX) {
            ++point_counter;
        }
    }
    if (point_counter !== points_number) {
        return false;
    }

    for (let j = 0; j < state.length; ++j) {
        if (state[j] === POINT_STATE_INDEX) {
            if (last_point_index >= 0) {
                let distance = Math.abs(j - last_point_index);
                const metric = points_number;
                if (distance > metric) {
                    return false;
                }
            }
            last_point_index = j;
        }
    }

    return true;
}

function calculateNewState(state) {
    const isCorrect = isCorrectState(state);
    if (isCorrect) {
        results.push([...state]);
    }
}

function printString(data, state) {
    let res = "";
    for (let i = 0; i < data.length; ++i) {
        res += data[i] + (state[i] == POINT_STATE_INDEX ? "." : "");
    }
    console.log(res);
}


startLoop(data_length, max_state_index, calculateNewState);
for (let state of results) {
    printString(data, state);
}
console.log("Count: ", results.length);

Здесь константа data_length определяет длину входной строки. Её можно брать как stringData.length при вводе данных в виде строки.

Функция loop - цикл с переменной вложенностью.

Функция startLoop - функция для запуска цикла по переданным параметрам.

Функция isCorrectState - предикат определяющий, соответствует ли состояние условию задачи.

Функция calculateNewState - callback для переменного цикла, выбирает из новых состояний корректные и делает с ними что-нибудь (записывает в массив с результатами или считает.

Answer 3

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

Предлагаю такой порядок.

Представить комбинации в виде числа в бинарном представлении, где ноль будет представлять точку, а единица символ строки.
Получить всю последовательность чисел между минимальным вариантом (1_0_1_0_1_0_1) и максимальным (111_0_111_0_111_0_111).
Убрать из этой последовательности все неподходящие комбинации (где нулей больше трёх, где число единиц между нулями меньше 1 и больше 3, где нули не между единицами).
Распределить оставшуюся последовательность в группы по количеству единиц. Так мы получим объект массивов, где ключ — длина строки, а массив — все комбинации точек и символов в этой строке.
Для удобства добавить ещё один объект, где где ключ — длина строки, а значение — количество комбинаций.

'use strict';

const min = 0b1_0_1_0_1_0_1;
const max = 0b111_0_111_0_111_0_111;

const validation = /^1{1,3}01{1,3}01{1,3}01{1,3}$/u;

const validCombinations =
  Array.from(
    Array(max - min + 1),
    (_, i) => (min + i).toString(2)
  )
  .filter(
    combination => validation.test(combination)
  )
  .reduce((acc, combination) => {
    const { length } = combination.replace(/0/ug, '');
    if (!acc[length]) acc[length] = [];
    acc[length].push(combination.replace(/0/ug, '.'));
    return acc;
  }, {});

const stringLengthToCombinationCount = Object.fromEntries(
  Object.entries(validCombinations).map(([key, value]) => [key, value.length])
);

console.log(stringLengthToCombinationCount);
console.log(validCombinations);

БЛОГ НА HUSL

Количество комбинаций чисел при данных условиях

Ответы (3 шт):