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

Question

Если мне дать последовательность X = {x1,x2,....xm}, то у меня будет (2^m) подпоследовательности. Кто-нибудь может объяснить, как я могу прийти к этой формуле интуитивно? Я могу начать с 3 элементов, затем 4, а затем 5 и прийти к этой формуле, но я не думаю, что понимаю. Откуда взялась «2»? Я не делю пополам или что-то здесь. Спасибо за помощь.

Answer 1

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

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 в приведенном выше примере) двоичных цифр, сколько двоичных чисел (подмножеств) может быть сгенерировано?Вы должны ответить на этот вопрос сейчас;)

Answer 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)

Answer 3

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

Answer 4

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

Answer 5

Для каждого элемента в последовательности длиной m, вы можете выбрать его или оставить. Таким образом, есть 2 способа иметь дело с каждым элементом. Поэтому итого нет. способов работы со всеми элементами m составляет 2*2*2...... m раз = 2^m раз.

Answer 6

Для любой последовательности 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

Answer 7

Если у вас есть последовательность S, что произойдет, когда вы добавите новый элемент x в конец S?

Все подпоследовательности S по-прежнему являются подпоследовательностями вашей новой последовательности. Как и все эти подпоследовательности с добавлением x в конце.

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

Answer 8

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

Answer 9

Чтобы расширить принятый ответ, число подпоследовательностей можно представить в математических терминах.Давайте рассмотрим пример строки: «ABC».

Количество подпоследовательностей строки 'ABC':

=> C(3, 0) + C(3, 1) + C(3, 2) + C(3, 3) = 1 + 3 + 3 + 1 = 8 (2^3).

(Примечание: C (m, n) обозначает количество подпоследовательностей размера 'n' из строкиsize 'm')

Это легко проверить, перечислив все из них:

C(3, 0) = '', // Taking 0 letters at a time out of the given string.
C(3, 1) = 'A', 'B', 'C', // Taking 1 letter at a time.
C(3, 2) = 'AB', 'AC', 'BC', // Taking 2 letters at a time.
C(3, 3) = 'ABC'. // Taking 3 letters at a time.
(Total count = 8)

Мы сохраняем последовательность букв для подпоследовательности, следовательно, Комбинация вместо Перестановка .

Примечание: сумма биномиальных коэффициентов с использованием теоремы о биномах = 2 ^ n.Доказательство ниже:

From Binomial theorem,
(x + y)^n = C(n, 0) x^n y^0 + .... + C(n, n) x^0 y^n

Using x = 1, y = 1,
(1+1)^n = C(n, 0) 1^n 1^0 + .... + C(n, n) 1^0 1^n 
=> 2^n = C(n,0) + C(n,1) + .... + C(n,n)

Отсюда и 2, из биномиальной теоремы.

Answer 10

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

Полагаю, что более интуитивный способ обдумать ответ - это подумать над примером.

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

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

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