ZTE pays Microsoft $30 for each Windows Phone license - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PDA - 掌中宝

ZTE pays Microsoft $30 for each Windows Phone license

ZTE pays Microsoft $30 for each Windows Phone license# PDA - 掌中宝

s*n2012-01-19 08:01

1 楼

Suppose we have a list of numbers with repetitions, e.g. {1, 2, 2, 3}, how
to
list all unique combinations? In this case, if k=2, the combinations are
{1,2}, {1,3},{2,2},{2,3}.
这个怎么做?

c*n2012-01-19 08:01

2 楼

Microsoft太黑了吧。

s*n2012-01-19 08:01

3 楼

what is the answer for 1,2,2,2,3
12
13
22
22
22
23
?

【在 s******n 的大作中提到】

: Suppose we have a list of numbers with repetitions, e.g. {1, 2, 2, 3}, how
: to
: list all unique combinations? In this case, if k=2, the combinations are
: {1,2}, {1,3},{2,2},{2,3}.
: 这个怎么做?

n*82012-01-19 08:01

4 楼

No. It's ZTE's so stupid.

s*n2012-01-19 08:01

5 楼

必须是unique的仍然是12, 13, 22, 23

a*x2012-01-19 08:01

6 楼

这是打算搞死卖刀么

【在 n*****8 的大作中提到】

: No. It's ZTE's so stupid.

A*r2012-01-19 08:01

7 楼

先把duplicate的去掉，就转化成一般情形的找k-element subset的问题了。。

【在 s******n 的大作中提到】

l*a2012-01-19 08:01

8 楼

靠,成本一下子就上去了,价格低不了了
zte在手机里面号召力一般,这下谁买啊?

h*k2012-01-19 08:01

9 楼

不能简单去掉duplicate。比如在这个例子里，2,2也是一个合法的输出。
sort数组，然后可以知道每个元素出现在数组里的次数。假设2出现了3次，其它元素都
只出现了一次。然后使用递归，依次处理数组中的元素。假设当处理元素2时，还要输
出2个元素，则下一步递归有三种可能，分别对应选择0个、1个或者2个元数2。

【在 A*********r 的大作中提到】

: 先把duplicate的去掉，就转化成一般情形的找k-element subset的问题了。。

t*p2012-01-19 08:01

10 楼

Already confirmed?这下他们也是手机里面的big player了

【在 c***n 的大作中提到】

: Microsoft太黑了吧。

h*62012-01-19 08:01

11 楼

这种情况倒是简单，问题是更一般的情况就难办了。
在一个可重复集合中，有n个不同元素a1,a2,...,an，分别出现了x1,x2,...,xn次，
现要从该集合中取出k个元素的组合，问有多少种取法，并输出每一种取法。

【在 h**k 的大作中提到】

: 不能简单去掉duplicate。比如在这个例子里，2,2也是一个合法的输出。
: sort数组，然后可以知道每个元素出现在数组里的次数。假设2出现了3次，其它元素都
: 只出现了一次。然后使用递归，依次处理数组中的元素。假设当处理元素2时，还要输
: 出2个元素，则下一步递归有三种可能，分别对应选择0个、1个或者2个元数2。

a*n2012-01-19 08:01

12 楼

那也比教主强吧？
直接不让你卖
不稀罕你那几个钱

h*k2012-01-19 08:01

13 楼

对于a1，如果x1一个递归，即如果a1出现y1次，则问题变成从a2开始输出k-y1个元素。

现要

【在 h**6 的大作中提到】

: 这种情况倒是简单，问题是更一般的情况就难办了。
: 在一个可重复集合中，有n个不同元素a1,a2,...,an，分别出现了x1,x2,...,xn次，
: 现要从该集合中取出k个元素的组合，问有多少种取法，并输出每一种取法。

h*62012-01-19 08:01

14 楼

只求个数可以用DP，输出全部组合则还是需要递归。
在一个可重复集合中，有n个不同元素a1,a2,...,an，分别出现了x1,x2,...,xn次，
现要从该集合中取出k个元素的组合，问有多少种取法，并输出每一种取法。
设f(i, j)为前i个不同元素取出j个的取法，则f(n, m)为全部取法个数。
f(i, j) = sum(k = 0 to min(xi, j, m)){f(i-1, j-k)}

A*r2012-01-19 08:01

15 楼

学习了。。
看来我对题目的理解没有你们深刻。。
我看到一个题目，不能马上意识到题目中的陷阱或者说难点在哪里，非要沉心静气用几
个实例才能理解深刻。有时候懒一点就会犯想当然的错误，这一点不知道怎么提高？

【在 h**k 的大作中提到】

s*n2012-01-19 08:01

16 楼

it ok to 去掉duplicate.对于每个dup输出 xx就好。剩下的就是没有duplicate的了。

【在 A*********r 的大作中提到】

: 学习了。。
: 看来我对题目的理解没有你们深刻。。
: 我看到一个题目，不能马上意识到题目中的陷阱或者说难点在哪里，非要沉心静气用几
: 个实例才能理解深刻。有时候懒一点就会犯想当然的错误，这一点不知道怎么提高？

A*r2012-01-19 08:01

17 楼

嗯，需要记录每个duplicate的次数，然后才知道对每个duplicate，要怎么输出。
如果duplicate的次数少于ｋ的话，那么ｋ里面可以取的ｘ的数目也是变的，挺复杂的
，需要用递归。。

【在 s*****n 的大作中提到】

: it ok to 去掉duplicate.对于每个dup输出 xx就好。剩下的就是没有duplicate的了。