请教一类组合问题
wuwenjin
1. 正方形分成4*4 16个小方格，把1到16填进去，满足从左到右，从上到下均由大到小排列，共多少种排法？
2. 12个人排两排，每排都按身高由小到大排，要求第二排相应位置上每个人的身高都比第一排上的人要高，问有多少种排法？
这类问题好像可以总结些规律，欢迎大家思考
Kevin
jinhu wang
wuwenjin
jinhu wang
同事儿子的作业，大概意思是这样:
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
4*4,把其中6个1替换成0,使得横竖1的个数都是偶数,一共有几种，并打印出来.
我自己做了下，写得很烦.有没有高人有简洁一点的代码.
刘鎏
Google Young Tableau
--
Liu Liu
Ph.D Student
Department of Systems Engineering
University of TianJin
E-mail: liuli...@gmail.com liu...@tju.edu.cn
jinhu wang
Wen YE
http://en.wikipedia.org/wiki/Young_tableau
发信人: LouisaSquare (苏玉华), 信区: Mathematics
标 题: Re: 百度的一道笔试题，非编程，求思路 (转载)
发信站: 水木社区 (Thu Sep 10 03:53:48 2009), 站内
对于n*n的问题，答案是
（n^2）!/\prod_{i,j}(i+j-1)
所以，4×4的时候，答案为
16!/(1*2*3*4*2*3*4*5*3*4*5*6*4*5*6*7)=24024
证明是用归纳法，但很复杂。可参看下文以及文中提到的参考文献：
An Elementary proof of hook formula
http://www.combinatorics.org/Volume_15/PDF/v15i1r45.pdf
wuwenjin
Cheng, Long
wangji...@gmail.com
On 10月22日, 下午5时58分, Wen YE <whusno...@gmail.com> wrote:
> 水木上的讨论直接给出了这个 wiki:
>
> >http://en.wikipedia.org/wiki/Young_tableau
>
> 同时还有这么一篇帖子提到过
>
> > 发信人: LouisaSquare (苏玉华), 信区: Mathematics
>
> 标 题: Re: 百度的一道笔试题，非编程，求思路 (转载)
>
> 发信站: 水木社区 (Thu Sep 10 03:53:48 2009), 站内
>
> > 对于n*n的问题，答案是
>
> （n^2）!/\prod_{i,j}(i+j-1)
>
> 所以，4×4的时候，答案为
>
> 16!/(1*2*3*4*2*3*4*5*3*4*5*6*4*5*6*7)=24024
>
> > 证明是用归纳法，但很复杂。可参看下文以及文中提到的参考文献：
>
> An Elementary proof of hook formula
>
> http://www.combinatorics.org/Volume_15/PDF/v15i1r45.pdf
>
> 2009/10/22 wuwenjin <kevin.w...@gmail.com>
>
>
>
> > 在水木上看到的两个题，有点类似 ，没想明白，来问问大家
> > 1. 正方形分成4*4 16个小方格，把1到16填进去，满足从左到右，从上到下均由大到小排列，共多少种排法？
> > 2. 12个人排两排，每排都按身高由小到大排，要求第二排相应位置上每个人的身高都比第一排上的人要高，问有多少种排法？
>
> > 这类问题好像可以总结些规律，欢迎大家思考
> > Kevin- 隐藏被引用文字 -
>
> - 显示引用的文字 -
jinhu wang
wangji...@gmail.com
//我这里算的结果是
D:\>a
24024
132
//以下是用c++通过穷举的计算的方法
#include <iostream>
#include <algorithm>
using namespace std;
struct S
{
S(int *p):m_p(p),i(0)
{}
inline void update(int data)
{
m_p[i]=data;
++i;
}
inline void reset()
{i=0;}
int i;
int*m_p;
};
inline bool islower(int *p,int l,int k)
{
for(int j=0;j<k-1;++j)
for(int i=0;i<l;++i)
{
if(p[i+j*l]>p[i+(1+j)*l])
{
return false;
}
}
return true;
}
template<int N_SIZE, int N_NUM>
void myapp()
{
enum{THE_SIZE= N_SIZE*N_NUM};
int p[THE_SIZE]={0};
S*ps[N_NUM];//={new S(p),new(),&c,&d};
double buff[N_NUM];
for(int i=0;i<N_NUM;++i)
{
ps[i]=new ((void*)&buff[i])S(p+i*N_SIZE);
}
int size=0;
int pc[THE_SIZE];//={0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3};
for(int j=0;j<N_NUM;++j)
for(int i=0;i<N_SIZE;++i)
{
pc[i+j*N_SIZE]=j;
}
//MYPP(pc,N_SIZE,N_NUM);
do {
for(int i=0;i<THE_SIZE;++i)
{
ps[pc[i]]->update(i);
}
if(islower(p,N_SIZE,N_NUM))
{
++size;
//MYPP(p,N_SIZE,N_NUM);
}
for(int i=0;i<N_NUM;++i)
{
ps[i]->reset();
}
}while(next_permutation(pc,pc+THE_SIZE));
cout<<size<<endl;
}
int main()
{
{
// AUTOClock clock;
myapp<4,4>();
}
// AUTOClock clock;
myapp<6,2>();
return 0;
Shuo Chen
#include <stdio.h>
int grid[5][5] = { 0 };
int set[17] = { 0 };
int cnt = 0;
void track(int y, int x)
{
if (y > 4)
{
++cnt;
for (int i = 1; i <= 4; ++i)
printf("%2d %2d %2d %2d ", grid[i][1], grid[i][2], grid[i][3],
grid[i][4]);
printf("\n");
}
else
{
for (int i = 1; i <= 16; ++i)
{
if (set[i] == 0 && i > grid[y][x-1] && i > grid[y-1][x])
{
grid[y][x] = i;
set[i] = 1;
if (x < 4)
track(y, x+1);
else
track(y+1, 1);
set[i] = 0;
grid[y][x] = 0;
}
}
}
}
int main()
{
track(1, 1);
printf("%d\n", cnt);
}
On Oct 23, 4:52 pm, "wangjinhu...@gmail.com" <wangjinhu...@gmail.com>
wrote:
Shuo Chen
#include <stdio.h>
int grid[5][5] = {0};
struct node
{
node* next;
node* prev;
int val;
};
node nodes[17];
void track(int y, int x)
{
if (y > 4)
{
++cnt;
for (int i = 1; i <= 4; ++i)
printf("%2d %2d %2d %2d ", grid[i][1], grid[i][2], grid[i][3],
grid[i][4]);
printf("\n");
}
else
{
{
int i = p->val;
if (i > grid[y][x-1] && i > grid[y-1][x])
grid[y][x] = i;
p->next->prev = p->prev;
{
track(y, x+1);
}
else
{
track(y+1, 1);
}
p->next->prev = p;
}
}
}
}
int main()
{
{
nodes[i].val = i;
nodes[i].next = &nodes[i+1];
nodes[i].prev = &nodes[i-1];
}
nodes[0].prev = &nodes[16];
nodes[16].next = &nodes[0];
Bill Wung
--
Sent from my mobile device
笑骂由人，洒脱自如！
心若冰清，天塌不惊！
http://www.iron-feet.cn