我最近遇到了以下问题:
I have faced the following problem recently:
我们有M个连续整数序列A,开始在A [1] = 1: 1,2,...,M(例如:M = 8,A = 1,2,3,4,5,6,7,8)
We have a sequence A of M consecutive integers, beginning at A[1] = 1: 1,2,...M (example: M = 8 , A = 1,2,3,4,5,6,7,8 )
我们必须集合T由来自L_T连任A.作出一切可能的子序列 (实施例L_T = 3,子序列是{1,2,3},{2,3,4},{3,4,5},...)。让我们致电T砖的元素。
We have the set T consisting of all possible subsequences made from L_T consecutive terms of A. (example L_T = 3 , subsequences are {1,2,3},{2,3,4},{3,4,5},...). Let's call the elements of T "tiles".
我们有集合S包括A具有长度L_S所有可能的子序列。 (例如L_S = 4,如子序列{1,2,3,4},{1,3,7,8},... {4,5,7,8})。
We have the set S consisting of all possible subsequences of A that have length L_S. ( example L_S = 4, subsequences like {1,2,3,4} , {1,3,7,8} ,...{4,5,7,8} ).
我们说一个元s的S可以,如果有T中存在ķ砖覆盖的T K砖,使得自己的电视机方面的工会含有S的一个子集的条款。例如,亚序列{1,2,3}可覆盖2瓦长度2({1,2}和{3,4}),而subsequnce {1,3,5}是不可能的盖带2砖的长度为2,但可能覆盖与2瓦片长度为3的({1,2,3}和{4,5,6})。
We say that an element s of S can be "covered" by K "tiles" of T if there exist K tiles in T such that the union of their sets of terms contains the terms of s as a subset. For example, subsequence {1,2,3} is possible to cover with 2 tiles of length 2 ({1,2} and {3,4}), while subsequnce {1,3,5} is not possible to "cover" with 2 "tiles" of length 2, but is possible to cover with 2 "tiles" of length 3 ({1,2,3} and {4,5,6}).
令C为S的元素,可以覆盖由T. K个瓦片
Let C be the subset of elements of S that can be covered by K tiles of T.
查找的C给出的基数男,L_T,L_S,K。
Find the cardinality of C given M, L_T, L_S, K.
任何想法,将AP preciated如何解决这个问题。
Any ideas would be appreciated how to tackle this problem.
假设 M
是整除 T
,因此,我们有瓦覆盖的初始设置中的所有元素(否则说法目前还不清楚)。的整数倍
Assume M
is divisible by T
, so that we have an integer number of tiles covering all elements of the initial set (otherwise the statement is currently unclear).
首先,让我们来细数 F(P)
:这将是长个子的几乎数量 L_S
它可以精确地所覆盖不超过 P
瓦片,但不是。
从形式上看, F(P)=选择(M / T,P)*选(P * T,L_S)
。
我们首先选择完全 P
覆盖瓦片:方法数为选择(M / T,P)
。
当砖是固定的,我们有完全 P *牛逼
不同的元素可用,并且有选择(P * T,L_S)
的方式选择一个序列。
First, let us count F (P)
: it will be almost the number of subsequences of length L_S
which can be covered by no more than P
tiles, but not exactly that.
Formally, F (P) = choose (M/T, P) * choose (P*T, L_S)
.
We start by choosing exactly P
covering tiles: the number of ways is choose (M/T, P)
.
When the tiles are fixed, we have exactly P * T
distinct elements available, and there are choose (P*T, L_S)
ways to choose a subsequence.
那么,这种方法有一个缺陷。 需要注意的是,当我们选择了一个瓦但在根本不使用它的元素,我们实际上计数一些亚序列一次以上。 举例来说,如果我们固定的三张牌编号为2,6和7,但只用了2和7,我们一次又一次地数着相同的子序列,当我们固定的编号为2,7和一切三个瓷砖
Well, this approach has a flaw. Note that, when we chose a tile but did not use its elements at all, we in fact counted some subsequences more than once. For example, if we fixed three tiles numbered 2, 6 and 7, but used only 2 and 7, we counted the same subsequences again and again when we fixed three tiles numbered 2, 7 and whatever.
上述问题可以通过的排容原理的变化被抵消。
的确,对于一个子只是它使用问:
瓷砖了 P
选择瓷砖,就被计数选择(MQ,PQ)
次,而不是只有一次:问:
的P
选择是固定的,但其他的都是任意的。
The problem described above can be countered by a variation of the inclusion-exclusion principle.
Indeed, for a subsequence which uses only Q
tiles out of P
selected tiles, it is counted choose (M-Q, P-Q)
times instead of only once: Q
of P
choices are fixed, but the other ones are arbitrary.
定义 G(P)
因为它可以覆盖完全 P 瓷砖。
然后, F(P)
是总和•从0至P
产品
上一篇:启发式功能水壶启发式、水壶、功能
下一篇:未知算法的大O算法