Количество подпоследовательностей в заданной последовательности

Ответ 1

Прежде всего, то, о чем вы говорите, называется set. Во-вторых, правильно, что количество различных подмножеств, которые могут быть сгенерированы из множества, равно 2 ^ m, где m - количество элементов в этом наборе. Мы можем прийти к такому результату, если взять пример из трех элементов:

S = {a, b, c}

Теперь для генерации каждого подмножества мы можем моделировать наличие элемента с использованием двоичной цифры:

xxx where x is either 0 or 1

Теперь давайте перечислим все возможности:

000 // empty sub-set
001
010
011
100
101
110
111 // the original set it self!

Давайте возьмем 011 в качестве примера. Первая цифра равна 0, тогда a не находится в этом подмножестве, но b и c существуют, потому что их соответствующие двоичные цифры равны 1. Теперь, учитывая m (например, 3 в приведенном выше примере) двоичные цифры, сколько двоичных чисел (подмножеств) может быть сгенерировано? Вы должны ответить на этот вопрос к настоящему времени;)

Ответ 2

Для тех, кто действительно ищет подстроку (поскольку заголовок или URL-адрес могут заставить вас поверить):

Subset: 2^n (Order doesn't matter in sets)
Subsequence: 2^n (Since we keep the original ordering, this is the same.)
Substring: n(n+1) * 1/2 (Elements must be consecutive)

Ответ 3

Значение x_i может быть либо в подпоследовательности, либо нет. Это как раз немного. Существуют комбинации 2^m для включения/выключения чисел m в последовательности.

Ответ 4

Откуда взялись 2? Каждый раз, когда вы добавляете еще один элемент, вы удваиваете количество возможностей.

Ответ 5

Для любой последовательности X = {x1, x2,.... xm} будут подпоследовательности (2 ^ m), так как вы можете "выбрать" подпоследовательности длины 0,1,2..., m, т.е. математически это

"C (m, 0) + C (m, 1) +... C (m, m)", что приводит к 2 ^ m.

Например, например, строка "abc", затем

C (3,0) = 1, ""

C (3,1) = 3, "a", "b", "c"

C (3,2) = 3, "ab", "bc", "ac"

C (3,3) = 1, "abc"

число подпоследовательностей равно 8, то есть 2 ^ 3.

Подробнее см. http://en.wikipedia.org/wiki/Binomial_coefficient#Series_involving_binomial_coefficients

Ответ 6

Для каждого элемента в последовательности длины m вы можете выбрать его или оставить. Таким образом, есть два способа решения каждого элемента. Таким образом, общее число. способов борьбы со всеми элементами m: 2*2*2...... m times = 2^m times.

Ответ 7

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

Ответ 8

Каждый элемент находится либо в подпоследовательности, либо нет. Поэтому, начиная с первого x1, существуют два набора подмножеств: те, у которых есть x1, и те, у кого нет. То же самое можно сделать с меньшей суб-проблемой {x2,..., xm}. Поэтому вы, наконец, получаете 2 ^ м.

Ответ 9

В основном у вас будет в два раза больше подпоследовательностей для каждого нового числа, так как у вас будут (2^(m-1)) "эквивалентные" подпоследовательности, которые сдвинуты на одно пространство вправо (при условии горизонтального упорядочения и добавления справа) плюс подпоследовательность всех элементы.

Ответ 10

Я начал курс алгоритма совсем недавно.

Я думаю, что более интуитивный способ мышления о ответе - подумать о примере.

Например, мы имеем A = (1,2,3) Тогда у нас может быть   0 что 1 путь   1,2 или 3, что 3 пути   (1,2), (1,3), (2,3), а также 3 способа   А также   (1,2,3) == что еще один путь

Общая подпоследовательность 2 ^ 3 или 8. Таким образом, общая формула   mc0 + mC1 + mC2, MC3 +...... MCM

Пожалуйста, поправьте меня, если я ошибаюсь. Я столкнулся с этой проблемой минут назад, и именно так я думал об интуитивной формулировке.