b****u
发帖数: 1130 | 1 9个小球 1 -9放到 3个相同的盒子，每个放3个。
比如（123）（456）（789）
（124）（356）（789）
.....
不能用递归，最好用 next()的方法来解决。
大家有没有好方法。 | H********n
发帖数: 99 | 2 leetcode next permutation
【在 b****u 的大作中提到】
: 9个小球 1 -9放到 3个相同的盒子，每个放3个。
: 比如（123）（456）（789）
: （124）（356）（789）
: .....
: 不能用递归，最好用 next()的方法来解决。
: 大家有没有好方法。
| b*****n
发帖数: 618 | 3 楼上正解，就是1-9的next permutation | b****u
发帖数: 1130 | 4 不是1-9 permutation.
3盒子是一样的，而且同一个盒子里也没有排列问题。这实际是一个组合问题。 | b*****n
发帖数: 618 | 5 没想到更好的方法，感觉略复杂但是应该work：
思路跟next permutation是类似的，只是需要每三个数每三个数的进行考虑。
先考虑比较简单的情况，假设只有两个盒子，123456
1.保证每个盒子里面的数是递增的
2.next()的时候实际上要找下一个满足条件的更大的数，
找的规则是：
比如第一个个盒子是123，第二个盒子是456
从第一个盒子最后一个数开始找，能不能在第二个盒子里面找到比它大的最小的数，如
果找到了就swap，
比如现在这种情况就是先看3，在第二个盒子里面找比3大的最小的是4，交换过后就是
124356，然后继续可以找到125346，126345
这个时候最后一个数就找不到了，找到数第二个数，需要做的是找到比2大的最小的两
个数34，所以下一个是134256，继续可以找到135246，136245，145236，146235，
156234
这个时候最后两个数56都找不到了，用同样的方法处理第倒数第三个数，依次类推。
这个方法可以扩展到任意个盒子。
【在 b****u 的大作中提到】
: 不是1-9 permutation.
: 3盒子是一样的，而且同一个盒子里也没有排列问题。这实际是一个组合问题。
| l******s
发帖数: 3045 | 6 好像BFS + Queue
共1680个解。
private static IEnumerable ThreeBuckets(){
Queue queue = new Queue();
for (int[,] tmp = new int[3, 3] { { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 } };
tmp[2, 0] == 0; tmp = queue.Peek()[2, 0] != 0 ? queue.Peek() : queue.Dequeue
())
for (int i = 1; i < 10; i++)
if (!(i == tmp[0, 0] || i == tmp[0, 1] || i == tmp[0, 2] || i == tmp[1, 0] |
| i == tmp[1, 1] || i == tmp[1, 2]))
for (int j = i + 1; j < 10; j++)
if (!(j == tmp[0, 0] || j == tmp[0, 1] || j == tmp[0, 2] || j == tmp[1, 0] |
| j == tmp[1, 1] || j == tmp[1, 2]))
for (int k = j + 1; k < 10; k++)
if (!(k == tmp[0, 0] || k == tmp[0, 1] || k == tmp[0, 2] || k == tmp[1, 0] |
| k == tmp[1, 1] || k == tmp[1, 2]))
queue.Enqueue(tmp[0, 0] == 0 ? new int[3, 3] { { i, j, k }, { 0, 0, 0 }, { 0
, 0, 0 } } : tmp[0, 0] != 0 && tmp[1, 0] == 0 ? new int[3, 3] { { tmp[0, 0],
tmp[0, 1], tmp[0, 2] }, { i, j, k }, { 0, 0, 0 } } : new int[3, 3] { { tmp[
0, 0], tmp[0, 1], tmp[0, 2] }, { tmp[1, 0], tmp[1, 1], tmp[1, 2] }, { i, j,
k } });
while (queue.Count != 0) yield return queue.Dequeue();
} | s***c
发帖数: 639 | 7 你们都不看题的么，这题真不简单
【在 b*****n 的大作中提到】
: 楼上正解，就是1-9的next permutation
| b***e
发帖数: 1419 | 8 这个其实就是C(8,2)*C(5,2)=280。next函数就是两个组合枚举的next函数按C(5,2)低
位(进位至)C(8,2)高位的结合。
【在 b****u 的大作中提到】
: 9个小球 1 -9放到 3个相同的盒子，每个放3个。
: 比如（123）（456）（789）
: （124）（356）（789）
: .....
: 不能用递归，最好用 next()的方法来解决。
: 大家有没有好方法。
| t****m
发帖数: 140 | 9 我来提供个思路，求大家指正，如果看的觉得还不错，能顺便求个new grad内推:-)?
***************************这是分割线*********************************
先看一个简单的例子，比如把编号为1,2,3,4的四个球放到两个相同的盒子里面（9个球
放到三个相同盒子里类似思路）：
Section A：
需要注意的是盒子是相同的，而且在同一个盒子内的球不排序。
这就说明其实
【1,2】【3,4】
【3,4】【1,2】
【4,3】【2,1】
【3,4】【2,1】
etc.的表达方法虽然不一样，但是分组方法其实是一样的
如何在写code的时候避免表达不同但是分组方法其实相同的问题呢，
让我们用【1,2】【3,4】这种数组的表达方法来represent这一种分组的方法
在【1,2】【3,4】这个表达方式的例子里，大家可以看到的规律是：
（1）每一个数组内部是排序的，即【1,2】或者【3,4】，不可能出现【2,1】或者
【4,3】
（2）数组之间以首元素排序，由于【1,2】中的1比【3,4】中的3小，所以【1,2】
排在【3,4】之前
由此有了分组的unique的表达方法，这样可以避免重复
Section B：
接下来看如何把不同的分组方法一个个找出来：
在这个例子里，我们要做的事情就是把1,2,3,4这四个数放到【X,X】【X,X】的数组里
，并且符合A中所提的分组方法的表达规律
假设这个【X,X】【X,X】叫Array吧
现在往第一个数组的第一个位置（Array[0][0]）填数字，需要符合A中所提的规律，那
么你能填什么呢？
填4？明显不符合A中所提的两条规律，因为4是最大的数字，Array[0][0]的位置填了4
，那么Array[0][1] 和Array[1][0]就没数填了
填3？好像也不行，因为我们知道Array[0][0]
][0]
如此我们就知道Array[0][0]的位置只能填1，所以我们把【X,X】【X,X】变成了【1,，
X】【X,X】
接下来再看Array[1][0]，既然Array[0][0]肯定是1了，那么Array[1][0]需要比1大
，而且Array[1][0]需要小于Array[1][1]，所以Array[1][0]的范围是2-3
于是我们又有了两种可能，把【1，X】【X,X】变成了
【1，X】【2,X】或者【1，X】【3,X】
如此反复，每一步都可能产生很多种可能，我们把每一种可能都记下来放到一个叫cur_
level的数组里，然后再用cur_level里的可能去推下一步的各种可能，最终就能得到结果
在上面的这个例子里，各种可能的示意图是这样的
1--------- 【X,X】【X,X】
|
|
2---------【1，X】【X,X】
|
--------------
| |
| |
3--【1，X】【2,X】 【1，X】【3,X】
| |
-------------- ------------
| | |
| | |
【1，3】【2,4】， 【1，4】【2,3】 ， 【1，2】【3,4】
一共三种方法
C(4,2)*C(2,2)/C(2,1)=3 | c*******e
发帖数: 35 | 10 我觉得你需要复习下概率了。是c(9,3)*c(6,3)*c(3,3)/p(3,3)
【在 l******s 的大作中提到】
: 好像BFS + Queue
: 共1680个解。
: private static IEnumerable ThreeBuckets(){
: Queue queue = new Queue();
: for (int[,] tmp = new int[3, 3] { { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 } };
: tmp[2, 0] == 0; tmp = queue.Peek()[2, 0] != 0 ? queue.Peek() : queue.Dequeue
: ())
: for (int i = 1; i < 10; i++)
: if (!(i == tmp[0, 0] || i == tmp[0, 1] || i == tmp[0, 2] || i == tmp[1, 0] |
: | i == tmp[1, 1] || i == tmp[1, 2]))
| | | i*****o
发帖数: 105 | 11
This is cool, the code is ugly:
#include
int
has3bits(unsigned c)
{
int n = 0;
while (c) {
n += (c&1);
c >>= 1;
if(n > 3) {
break;
}
}
return n == 3;
}
unsigned
highbit(unsigned c)
{
unsigned h = 0x100;
while (!(h & c) && h) {
h >>= 1;
}
return h;
}
int
c3_next(unsigned *c1, unsigned *c2)
{
unsigned c1_min = 0x100, c2_min;
int found = 0, found1 = 0;
while (!found) {
if (has3bits(*c1)) {
goto next_c2;
}
while (*c1 > c1_min) {
(*c1)--;
if (has3bits(*c1)) {
found1 = 1;
break;
}
}
if (!found1) {
goto out;
}
*c2 = (~(*c1)) & 0x1ff;
next_c2:
c2_min = highbit(*c2);
while (*c2 > c2_min) {
(*c2)--;
if (((*c2) & (*c1)) == 0 && has3bits(*c2)) {
found = 1;
break;
}
}
if (!found) {
(*c1)--;
if (has3bits(*c1)) {
*c2 = (~(*c1)) & 0x1ff;
} else {
found1 = 0;
}
}
}
out:
return found;
}
c3_print(unsigned c1, unsigned c2)
{
unsigned i, n;
n = c1;
for (i = 1; i <= 9; i++) {
if (n & (1<<(9-i))) {
printf("%d", i);
}
}
printf(" ");
n = c2;
for (i = 1; i <= 9; i++) {
if (n & (1<<(9-i))) {
printf("%d", i);
}
}
printf(" ");
n = ~(c1 | c2) & 0x1ff;
for (i = 1; i <= 9; i++) {
if (n & (1<<(9-i))) {
printf("%d", i);
}
}
printf("n");
}
main()
{
unsigned c1, c2;
c1 = (0x7 << 6);
c2 = (~c1) & 0x1ff;
while (c3_next(&c1, &c2)) {
c3_print(c1, c2);
}
}
【在 b***e 的大作中提到】
: 这个其实就是C(8,2)*C(5,2)=280。next函数就是两个组合枚举的next函数按C(5,2)低
: 位(进位至)C(8,2)高位的结合。
| t****m
发帖数: 140 | 12 尼玛本来不想贴code，虽然很丑，还是发一个：
N = 9
NSQRT = 3
NSQRTI = 2
def combination(self):
# write your code here
# check
initial = [0 for i in range(N)]
cur_level = []
cur_level.append(initial)
next_level = []
for i in range(NSQRT):
for j in range(NSQRT):
for case in cur_level:
low, high = 0, 0
num_map = set()
for num in case:
num_map.add(num)
if i==0 and j==0:
low = 1
high = 1
elif i==0:
low = case[j*NSQRT-NSQRT] + 1
high = N-((NSQRTI-j)*NSQRT+NSQRTI)
else:
low = case[i+j*NSQRT-1] + 1
high = N-(NSQRTI-i)
for k in range(low, high+1):
if not k in num_map:
case[j*NSQRT+i] = k
next_level.append(case[:])
cur_level = next_level
next_level = []
return len(cur_level) | b***e
发帖数: 1419 | 13 太麻烦了。这样想：1一定要放在某个盒子里。从另外三个里挑一个和1放一起，C(3,1)
=3.
【在 t****m 的大作中提到】
: 我来提供个思路，求大家指正，如果看的觉得还不错，能顺便求个new grad内推:-)?
: ***************************这是分割线*********************************
: 先看一个简单的例子，比如把编号为1,2,3,4的四个球放到两个相同的盒子里面（9个球
: 放到三个相同盒子里类似思路）：
: Section A：
: 需要注意的是盒子是相同的，而且在同一个盒子内的球不排序。
: 这就说明其实
: 【1,2】【3,4】
: 【3,4】【1,2】
: 【4,3】【2,1】
| t****m
发帖数: 140 | 14 你说的思路对四个球放两个盒子可以
九个球放三个盒子就不行了
我描述的思路应该可以扩展到九个球三个盒子
1)
【在 b***e 的大作中提到】
: 太麻烦了。这样想：1一定要放在某个盒子里。从另外三个里挑一个和1放一起，C(3,1)
: =3.
| b***e
发帖数: 1419 | 15 前面已经说了九球三盒的情况，就是C(8,2)*C(5,2). 先定住1号球，然后从另外八个里
选两个和1号同盒。这是C(8,2). 后面的递归，每次减3，就是C(5,2)和C(2,2)。这样
next函数很好写，就是两个组合枚举next函数按进位结合。
【在 t****m 的大作中提到】
: 你说的思路对四个球放两个盒子可以
: 九个球放三个盒子就不行了
: 我描述的思路应该可以扩展到九个球三个盒子
:
: 1)
| b*****n
发帖数: 618 | 16 牛！这个解法好
【在 b***e 的大作中提到】
: 前面已经说了九球三盒的情况，就是C(8,2)*C(5,2). 先定住1号球，然后从另外八个里
: 选两个和1号同盒。这是C(8,2). 后面的递归，每次减3，就是C(5,2)和C(2,2)。这样
: next函数很好写，就是两个组合枚举next函数按进位结合。
| A*******e
发帖数: 2419 | 17 楼主不是不让用递归吗？
【在 b***e 的大作中提到】
: 前面已经说了九球三盒的情况，就是C(8,2)*C(5,2). 先定住1号球，然后从另外八个里
: 选两个和1号同盒。这是C(8,2). 后面的递归，每次减3，就是C(5,2)和C(2,2)。这样
: next函数很好写，就是两个组合枚举next函数按进位结合。
|
|
