s******n
发帖数: 21 | 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}.
这个怎么做? | s*****n
发帖数: 5488 | 2 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}.
: 这个怎么做?
| s******n
发帖数: 21 | 3 必须是unique的 仍然是12, 13, 22, 23 | A*********r
发帖数: 564 | 4 先把duplicate的去掉，就转化成一般情形的找k-element subset的问题了。。
【在 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}.
: 这个怎么做?
| h**k
发帖数: 3368 | 5 不能简单去掉duplicate。比如在这个例子里，2,2也是一个合法的输出。
sort数组，然后可以知道每个元素出现在数组里的次数。假设2出现了3次，其它元素都
只出现了一次。然后使用递归，依次处理数组中的元素。假设当处理元素2时，还要输
出2个元素，则下一步递归有三种可能，分别对应选择0个、1个或者2个元数2。
【在 A*********r 的大作中提到】
: 先把duplicate的去掉，就转化成一般情形的找k-element subset的问题了。。
| h**6
发帖数: 4160 | 6 这种情况倒是简单，问题是更一般的情况就难办了。
在一个可重复集合中，有n个不同元素a1,a2,...,an，分别出现了x1,x2,...,xn次，
现要从该集合中取出k个元素的组合，问有多少种取法，并输出每一种取法。
【在 h**k 的大作中提到】
: 不能简单去掉duplicate。比如在这个例子里，2,2也是一个合法的输出。
: sort数组，然后可以知道每个元素出现在数组里的次数。假设2出现了3次，其它元素都
: 只出现了一次。然后使用递归，依次处理数组中的元素。假设当处理元素2时，还要输
: 出2个元素，则下一步递归有三种可能，分别对应选择0个、1个或者2个元数2。
| h**k
发帖数: 3368 | 7 对于a1，如果x1
一个递归，即如果a1出现y1次，则问题变成从a2开始输出k-y1个元素。
现要
【在 h**6 的大作中提到】
: 这种情况倒是简单，问题是更一般的情况就难办了。
: 在一个可重复集合中，有n个不同元素a1,a2,...,an，分别出现了x1,x2,...,xn次，
: 现要从该集合中取出k个元素的组合，问有多少种取法，并输出每一种取法。
| h**6
发帖数: 4160 | 8 只求个数可以用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*********r
发帖数: 564 | 9 学习了。。
看来我对题目的理解没有你们深刻。。
我看到一个题目，不能马上意识到题目中的陷阱或者说难点在哪里，非要沉心静气用几
个实例才能理解深刻。有时候懒一点就会犯想当然的错误，这一点不知道怎么提高？
【在 h**k 的大作中提到】
: 不能简单去掉duplicate。比如在这个例子里，2,2也是一个合法的输出。
: sort数组，然后可以知道每个元素出现在数组里的次数。假设2出现了3次，其它元素都
: 只出现了一次。然后使用递归，依次处理数组中的元素。假设当处理元素2时，还要输
: 出2个元素，则下一步递归有三种可能，分别对应选择0个、1个或者2个元数2。
| s*****n
发帖数: 5488 | 10 it ok to 去掉duplicate.对于每个dup输出 xx就好。剩下的就是没有duplicate的了。
【在 A*********r 的大作中提到】
: 学习了。。
: 看来我对题目的理解没有你们深刻。。
: 我看到一个题目，不能马上意识到题目中的陷阱或者说难点在哪里，非要沉心静气用几
: 个实例才能理解深刻。有时候懒一点就会犯想当然的错误，这一点不知道怎么提高？
| A*********r
发帖数: 564 | 11 嗯，需要记录每个duplicate的次数，然后才知道对每个duplicate，要怎么输出。
如果duplicate的次数少于ｋ的话，那么ｋ里面可以取的ｘ的数目也是变的，挺复杂的
，需要用递归。。
【在 s*****n 的大作中提到】
: it ok to 去掉duplicate.对于每个dup输出 xx就好。剩下的就是没有duplicate的了。
| a*******8
发帖数: 2299 | 12 if 取到k个数，output
else
for i = 0; i <= 当前number出现次数; i++
{
if (i+剩下number个数足够取足K个）{
取i个当前number
递归，取下面剩下的number
}
} |
|
