{算法}{技术}将1-n*n 十六个整数填在nxn的格子里, 使从左至右, 从上至下皆增, 共有多少种填法?

[张沈鹏]

以前和同学玩的题目，蛮有意思，附上代码，大家可以写着玩玩：）

========
#coding:utf-8
#将1-n*n 十六个整数填在nxn的格子里, 使从左至右, 从上至下皆增, 共有多少种填法?

from collections import defaultdict

def right(a):
   for i in range(0,4):
       b=i*4
       if not (a[b]<a[b+1]<a[b+2]<a[b+3] and a[i]<a[i+4]<a[i+8]<a[i+12]):
           return False
   return True


def show_shape(num):
   grid = len(num)
   for i in num:
       print "%s%s"%(i*"*","-"*(grid-i))
   print ""

def find_maybe_pos(num):
   grid = len(num)
   pre=grid
   for pos,i in enumerate(num):
       if i<grid:
           if i<pre:
               copy = list(num)
               copy[pos]+=1
               yield copy
               pre = i

def reshape(shape):
   grid = len(shape)
   num = [0]*grid
   for col in xrange(grid):
       count = 0
       for i in shape:
           if i>col:
               count+=1
           else:
               break

       num[col]=count

   for a,b in zip(shape,num):
       if a<b:
           shape = num
       if a>b:
           break
   return shape

def pair_shape(shape):
   grid = len(shape)
   return [grid-i for i in reversed(shape)]

def sum_total(grid=4):
   if not grid:return 0

   init_shape = [0]*grid
   init_shape[0] = 1
   init_shape=tuple(init_shape)
   new_shape_power = defaultdict(int)

   shape_power = {
       init_shape:1
   }
   total = grid**2-1
  # half_total = total/2
   count = 0
   existed = set()
   for i in xrange(1,total):
       for pre_shape in shape_power.keys():
           for shape in find_maybe_pos(pre_shape):
               #print "##########"
               #show_shape(pre_shape)
               #print "->\n"
               #show_shape(shape)
               tuple_shape = tuple(shape)
               if tuple_shape not in new_shape_power:
                   shape = tuple(reshape(shape))
               new_shape_power[tuple_shape]+=shape_power[pre_shape]
       shape_power = new_shape_power
       #for k,v in shape_power.iteritems():
       #    print v
       #    show_shape(k)
       #print ">>>>>>>>>>>>>>",sum(shape_power.itervalues())
       new_shape_power = defaultdict(int)
   return sum(shape_power.itervalues())

#print pair_shape([4,1,0,0])
print sum_total(4)
print sum_total(5)
#print sum_total(10)

[Shuo Chen]

两个月前讨论过了：

http://groups.google.com/group/pongba/browse_thread/thread/f1f671543e1be475/dee2c5a9668bfdcf

[张沈鹏]

没注意，发重复了,sorry:)

[jun lin]

同志们啊，这样的题目有意思吗。。。。

2009/12/29 张沈鹏 <zsp...@gmail.com>

没注意，发重复了,sorry:)

[Shuo Chen]

你来点有意思的？

[jun lin]

至少要加上背景：

又一次你走在路上，发现前方有2帮人在火并，
其中有个美女正向你跑来，同时在大声呼救。
但是你正在思考一个问题：（上面的题目）
而要求完美的你，在把这个问题思考完之前，是不会去做别的事情的。
你到底能不能在美女跑到自己面前的时候，把问题解掉，
然后趁乱把美女OOXX，
还是等美女从身边跑过后，还在思考这个问题，然后被后面追上来的壮男们撞飞？

2009/12/29 Shuo Chen <gian...@gmail.com>

[jun lin]

好吧，我的意思是，像某些教科书的课后题学习。。

2009/12/29 jun lin <linjun...@gmail.com>