新未名空间

比如说，有7张牌
A A A 7 8 K K

从中任选3张，要求是同一数字的牌最多只能选一张的组合数是多少？

考虑到每个数字的牌分别有1，1，2，3张，所以例子结果是

2*3 * c(2,1) + 2*c(2,2) + 3*c(2,2) = 17

种

问题:
给的输入是一个数组，表示我手里每个数字的牌有多少张(上面例子1,1,2,3)，问此组合数的解?

note:

O(n^3)的解是trivial的，三重循环加起来即可

O(n)呢？

（ヅ） 写了： 2023年 2月 21日 09:04 比如说，有7张牌
A A A 7 8 K K

从中任选3张，要求是同一数字的牌最多只能选一张的组合数是多少？

考虑到每个数字的牌分别有1，1，2，3张，所以例子结果是

2*3 * c(2,1) + 2*c(2,2) + 3*c(2,2) = 17

种

问题:
给的输入是一个数组，表示我手里每个数字的牌有多少张(上面例子1,1,2,3)，问此组合数的解?

note:

O(n^3)的解是trivial的，三重循环加起来即可

O(n)呢？

(type=t1, count=n1), (t2, n2),..., (tk, nk)
n1+n2+...+ nk =n

special cases:
1. (1, n-2), (2, 1), (3, 1)
O(n)

2. (1, L), (2,L),...,(k,L) （n=k L）
O((n/k)^3)

“写出”/列出上面的情况的所有解需要的时间分别是最好的和最坏的。各种情况的平均,应该是O(n*log(n))吧？

meiyoumajia 写了： 2023年 2月 21日 14:20 (type=t1, count=n1), (t2, n2),..., (tk, nk)
n1+n2+...+ nk =n

special cases:
1. (1, n-2), (2, 1), (3, 1)
O(n)

2. (1, L*k), (2,L*k),...,(k,L*k)
O((n/k)^3)

“写出”/列出上面的情况的所有解需要的时间分别是最好的和最坏的。各种情况的平均,应该是O(n*log(n))吧？

这里的n指的是手里牌有多少种数字，例子里面n=4

在特殊情况下，比如所有牌都只有一张，退化成一个很简单的情况c(n,3)，O（1）时间复杂度

（ヅ） 写了： 2023年 2月 21日 15:54 这里的n指的是手里牌有多少种数字，例子里面n=4

在特殊情况下，比如所有牌都只有一张，退化成一个很简单的情况c(n,3)，O（1）时间复杂度

（本来想按所有分布的状态平均求出complexity，但是感觉不容易做，就把删掉的原来的回复再贴了回来。）


你用的k就是我前面的n。那我把符号改一下
还是只讨论共n种牌，共k张牌。从每种最多取一，共取3。

一般的complexity是对应k很大。
你现在是要独立的变量n（它永远不会大于k）也很大，是在k很大的情况下的特殊情况。
(type=t1, count=i1), (t2, i2),..., (tn, in)
i1+i2+...+ in =k


复杂度/complexity与k有很大关系，绝对不可忽略。前面给的例子已经显示了这点。
special cases for big k：
1. (1, k-2), (2, 1), (3, 1） //////这也就是n=3时的一个特例。对这么小的数，讨论complexity没有实际意义，但是对k有。
O(k)

2. (1, L), (2,L),...,(n,L) （k=nL，L与k一样是个很大的整数，考虑k》L》n，在这种情况下n也可以很大）
O((L^3)，也就是O(((k/n)^3)。

meiyoumajia 写了： 2023年 2月 22日 01:06 （本来想按所有分布的状态平均求出complexity，但是感觉不容易做，就把删掉的原来的回复再贴了回来。）


你用的k就是我前面的n。那我把符号改一下
还是只讨论共n种牌，共k张牌。从每种最多取一，共取3。

一般的complexity是对应k很大。
你现在是要独立的变量n（它永远不会大于k）也很大，是在k很大的情况下的特殊情况。
(type=t1, count=i1), (t2, i2),..., (tn, in)
i1+i2+...+ in =k


复杂度/complexity与k有很大关系，绝对不可忽略。前面给的例子已经显示了这点。
special cases for big k：
1. (1, k-2), (2, 1), (3, 1） //////这也就是n=3时的一个特例。对这么小的数，讨论complexity没有实际意义，但是对k有。
O(k)

2. (1, L), (2,L),...,(n,L) （k=nL，L与k一样是个很大的整数，考虑k》L》n，在这种情况下n也可以很大）
O((L^3)，也就是O(((k/n)^3)。

你给的第一个例子，那种情况就是O(1)，并不是你说的O(k)

这里的复杂度，跟k没多大关系，跟n有关

（ヅ） 写了： 2023年 2月 22日 10:35 你给的第一个例子，那种情况就是O(1)，并不是你说的O(k)

这里的复杂度，跟k没多大关系，跟n有关

n=3，而解是k-2。
如果k很大，k-2》n，是O(k).因为对扑克牌那种类型的问题，k-2个“花色”中，取哪种花色是有区别的。你给的那个17的例子就是分辨花色，虽然共取3牌时最多只能取同一“值”中一种花色。

meiyoumajia 写了： 2023年 2月 22日 11:04 解是k-2，因此是O(k).因为对扑克牌那种类型，k-2个“花色”中，取哪种花色是有区别的。你给的那个17的例子就是分辨花色，虽然共取3牌时最多只能取同一“值”中一种花色。

big-O是考虑算多少次，而不是考虑这个数字多大

（ヅ） 写了： 2023年 2月 22日 11:05 big-O是考虑算多少次，而不是考虑这个数字多大

嗯
我前面考虑的是：列出所有解需要时间的complexity


你这要的算的complexity与普通谈的算法不太一样


就考虑你这种

在根本上是
(1+x1_1+...+x1_L1)*
(1+x2_1+...+x2_L2))*
...*
(1+xn_1+...+xn_Ln)
按你给出的输入L1L2...Ln(假定里面的花色也被完全确定了，否则问题会有些不一样)，找出3次项的总个数

共有L种“花色”，输入长度是n（而且其中的花色也已经被完全确定）

长度为n的111...1：答案是n*（n-1）*（n-2）/3/2，要算4次
长度为n的222...2 ：答案是n*（n-1）*（n-2*）*2^3/3/2，要算7次
长度为n的L...L ：答案是n*（n-1）*（n-2*）*L^3/3/2，要算7次
都是O（1）

应该会有怎么算也不是O(1)的情况。