Количество способов выбрать элементы массива?

Question

Как сформулировать эту проблему в коде?

Постановка задачи:

ОБНОВЛЕНО:

Найдите количество способов выбрать элемент из массива, который не был посещен.

Мы начинаем с 1,2, ....., n с некоторого (1 < = x <= n) количество элементов, выбранных / посещенных случайным образом, что указывается во входных данных </p>

Теперь нам нужно найти количество способов, которыми мы можем выбрать остаток (n - x) количества элементов, присутствующих в массиве, и способ, которым мы выбираем элемент, определяется как:

На каждом ходу мы можем выбрать только элемент, который находится рядом (слева или справа) с каким-либо посещаемым элементом, то есть в массиве элементов:

1,2,3,4,5,6 скажем, мы посетили 3 & 6 , теперь мы можем выбрать 2 или 4 или 5 , так как они не посещены и смежно с посещенными узлами, теперь скажем, что мы выбрали 2, поэтому теперь мы можем выбрать 1 или 4 или 5 и продолжить.

пример:

input: N = 6(number of elements: 1, 2, 3, 4, 5, 6)
M = 2(number of visited elements) 
visited elements are = 1, 5

Output: 16(number of ways we can pick the unvisited elements)

ways: 4, 6, 2, 3 
      4, 6, 3, 2
      4, 2, 3, 6
      4, 2, 6, 3
      4, 3, 2, 6
      4, 3, 6, 2
      6, 4, 2, 3
      6, 4, 2, 3
      6, 2, 3, 4
      6, 2, 4, 3 
      2, 6, 4, 3
      2, 6, 3, 4
      2, 4, 6, 3
      2, 4, 3, 6
      2, 3, 4, 6 
      2, 3, 6, 4.

Answer 1

Некоторый анализ проблемы:

• Фактические значения во входном массиве предполагаются равными 1 ... n, но эти значения на самом деле не играют роли. Эти значения просто представляют индексы, на которые ссылается другой входной массив, в котором перечислены посещенные индексы (на основе 1)
• Список посещенных индексов фактически разделяет основной массив на подмассивы с меньшими размерами. Так, например, когда n=6 и visited=[1,5], то исходный массив [1,2,3,4,5,6] разрезается на [2,3,4] и [6]. Таким образом, он разделяет его на размеры 3 и 1. На этом этапе нумерация индексов теряет свое предназначение, поэтому проблема действительно полностью описана с этими двумя размерами: 3 и 1. Для иллюстрации, решение для (n=6, visited=[1,5]) обязательно такое же, как для (n=7, visited[1,2,6]): размеры, на которые вырезан исходный массив, одинаковы в обоих случаях (в другом порядке, но это не влияет на результат).

Алгоритм, основанный на список размеров подмассивов (см. выше):

• Количество способов, которыми один такой подмассив может быть посещен, не так уж сложно: если размер подмассива равен 1, есть только один путь. Если оно больше, то при каждом пике есть две возможности: либо выбрать с левой стороны, либо с правой стороны. Таким образом, вы получаете 2 * 2 * .. * 2 * 1 возможностей для выбора. Это 2 ^size-1 возможностей.
• Два внешних подмассива являются исключением из этого, так как вы можете выбирать предметы только изнутри, поэтому для тех количество посещений такого подмассива составляет всего 1.
• Количество способов выбора элементов из двух подмассивов может быть определено следующим образом: подсчитать количество способов выбрать только один из этих подмассивов и количество способы выбрать из другого. Затем учтите, что вы можете выбирать, когда выбирать из одного подмассива или из другого. Это сводится к переплетению двух суб-массивов. Скажем, у большего из двух подмассивов есть j элементов, а у меньшего k , а затем рассмотрим, что есть j + 1 позиций, где элемент из меньшего вложенный массив может быть введен (объединен) в больший массив. Существует "k multichoose j + 1" способов для вставки всех элементов из меньшего подмассива.
• Когда вы посчитали количество способов слияния двух подмассивов, у вас фактически есть массив с размером, который является суммой этих двух размеров. Приведенный выше лог c может быть применен к этому массиву и следующему подмассиву в спецификации проблемы. Количество способов просто увеличивается, когда вы объединяете больше подмассивов в этот растущий массив. Конечно, вы на самом деле не имеете дело с массивами, только с размерами.

Вот реализация в JavaScript, которая применяет приведенный выше алгоритм:

function getSubArraySizes(n, visited) {
    // Translate the problem into a set of sizes (of subarrays)
    let j = 0;
    let sizes = [];
    for (let i of visited) {
        let size = i - j - 1;
        if (size > 0) sizes.push(size);
        j = i;
    }
    let size = n - j;
    if (size > 0) sizes.push(size);
    return sizes;
}

function Combi(n, k) {
    // Count combinations: "from n, take k"
    // See Wikipedia on "Combination"
    let c = 1;
    let end = Math.min(k, n - k);
    for (let i = 0; i < end; i++) {
        c = c * (n-i) / (end-i); // This is floating point
    }
    return c; // ... but result is integer
}

function getPickCount(sizes) {
    // Main function, based on a list of sizes of subarrays
    let count = 0;
    let result = 1;
    for (let i = 0; i < sizes.length; i++) {
        let size = sizes[i];
        // Number of ways to take items from this chunk: 
        // - when items can only be taken from one side: 1
        // - otherwise: every time we have a choice between 2, except for the last remaining item
        let pickCount = i == 0 || i == sizes.length-1 ? 1 : 2 ** (size-1);
        // Number of ways to merge/weave two arrays, where relative order of elements is not changed
        // = a "k multichoice from n". See 
        // https://en.wikipedia.org/wiki/Combination#Number_of_combinations_with_repetition
        let weaveCount = count == 0 ? 1 // First time only
            : Combi(size+count, Math.min(count, size));
        // Number of possibilities:
        result *= pickCount * weaveCount;
        // Update the size to be the size of the merged/woven array
        count += size;
    }
    return result;
}

// Demo with the example input (n = 6, visited = 1 and 5)
let result = getPickCount(getSubArraySizes(6, [1, 5]));

console.log(result);