求算法

chinesedragon

有一道这样的题：
有一个6*6的方框，有黑白两种球，要放到方框中。要求每行和每一列都是3个黑球3个白球。问有多少种排法？

erduo100

黑球与黑球之间，白球与白球有没有区别?

erduo100

做了不记区别的,但效率不高, 6*6时等了好几分钟都没算出来,4*4却可以.下面以4*4为例.调用函数Perm时,由于每行排列重复算了(2!)^2=4次,故4行共重复了4^4=256次,所以排法有count/256种,
若同色球之间有区别,那么排法有count/256*(8!)*(8!)种


#include <iostream>
#include <string>
#include <vector>

using namespace std;

template<class T>
void Swap(T& a, T& b);

void Perm(vector < vector<int> >& list, int k, int m);

int count = 0;

int main()
{
        const int m = 4;
        vector<int> row;
        int i;
        for (i = 0; i <= m; ++i)
        {
                //0 represent white ball, 1 represent black ball
                if (i <= m/2-1)
                        row.push_back(0);
               
                else
                        row.push_back(1);
        }

        vector < vector<int> > ball(m);
        for (i = 0; i < m; ++i)
        {
                ball[i].resize(m);
                ball[i] = row;
        }

        Perm(ball, 0, m-1);
        cout << "The number of permulation is " << count/256 << endl;

        return 0;
}

void Perm(vector < vector<int> >& list, int k, int m)
{
    int j;

        // The current row
    static int i = 0;
       
    if (k == m)
    {
            ++i;

            if (i != m+1)
                    Perm(list, 0, m);               
               
          
            else
                {
                    int sum, r, c;

                        --i;
                    bool Is_m = true;
                    for (c = 0; c <= m; ++c)
                        {
                            sum = 0;
                            for (r = 0; r <= m; ++r)
                                    sum += list[r][c];

                            if (sum != (m+1)/2)
                                {
                                    Is_m =false;
                                    break;
                                }
                        }
                  
                    if (Is_m)
                            ++count;
                }
        }
       
    else
        {
            for (j = k; j <= m; j++)
                {
                Swap(list[i][k], list[i][j]);
                    Perm(list, k+1, m);
                    Swap(list[i][k], list[i][j]);
                }
          
            if (k == 0)
                    --i;
               
        }
}

template<class T>
void Swap(T& a, T& b)
{// Swap a and b.
    T temp = a; a = b; b = temp;
}

islandxfg

#include "stdio.h"
int pi(int p,int i);
int h51(int i1,int i2 ,int i3 ,int i4 ,int i5,int i);//ii1
int h61(int p1, int p2, int p3,int p4,int p5,int p6,int i);

int p(int p)
{
if(
(pi(p,0)
+pi(p,1)
+pi(p,2)
+pi(p,3)
+pi(p,4)
+pi(p,5)
) == 3 )
  return 1;
   else
return 0;
}

int h5(int p1,int p2,int p3,int p4,int p5)
  {
   return
  (
    h51(p1,p2,p3,p4,p5,0) &
    h51(p1,p2,p3,p4,p5,1) &
    h51(p1,p2,p3,p4,p5,2) &
    h51(p1,p2,p3,p4,p5,3) &
    h51(p1,p2,p3,p4,p5,4)  ) ;
}

int h51(int p1,int p2,int p3,int p4,int p5,int i)
{
int aa;
    aa=pi(p1,i)+
    pi(p2,i)+
    pi(p3,i)+
    pi(p4,i)+
    pi(p5,i);
    return ( aa <4 & aa> 1);
}


    int h6(int p1,int p2,int p3,int p4,int p5,int p6)
    {
    return
    (

    h61(p1,p2,p3,p4,p5,p6,0) &
    h61(p1,p2,p3,p4,p5,p6,1) &
    h61(p1,p2,p3,p4,p5,p6,2) &
    h61(p1,p2,p3,p4,p5,p6,3) &
    h61(p1,p2,p3,p4,p5,p6,4) &
    h61(p1,p2,p3,p4,p5,p6,5)  ) ;
    }
int h61(int p1, int p2, int p3,int p4,int p5,int p6,int i)
    {
    return (
    (
    pi(p1,i)+
    pi(p2,i)+
    pi(p3,i)+
    pi(p4,i)+
    pi(p5,i)+
    pi(p6,i)
    )==3 ); //i3
  }

    int pi(int p ,int i)
    {
    return ( (p>>i)&1 );//i,i
     }


int main()
{
int i1,i2,i3,i4,i5,i6;
long n=0 ,m=0;
for (i1=7;i1<57;i1++)
    if( p(i1)  )
{
printf("%d %ld,\n",i1,n);
for (i2=7;i2<57;i2++)
        if( p(i2)  )
for (i3=7;i3<57;i3++)
        if( p(i3)  )
for (i4=7;i4<57;i4++)
        if( p(i4) & h5(i1,i2,i3,i4,0) )
for (i5=7;i5<57;i5++)
        if( p(i5)  & h5(i1,i2,i3,i4,i5) )
for (i6=0;i6<57;i6++)
        if( p(i6) & h6(i1,i2,i3,i4,i5,i6) )
        n++;
        else m++;
}
printf("Hello %ld %ld !\n", n,m);
return 0;
}
7 0,
11 3966,
13 7932,
14 11898,
19 15864,
21 19830,
22 23796,
25 27762,
26 31728,
28 35694,
35 39660,
37 42222,
38 44784,
41 47346,
42 49908,
44 52470,
49 55032,
50 57594,
52 60156,
56 62718,
Hello 65280 5187840 !

[ 本帖最后由 islandxfg 于 2006-4-6 22:43 编辑 ]

courage121

原帖由 erduo100 于 2006-4-6 18:50 发表
做了不记区别的,但效率不高, 6*6时等了好几分钟都没算出来,4*4却可以.下面以4*4为例.调用函数Perm时,由于每行排列重复算了(2!)^2=4次,故4行共重复了4^4=256次,所以排法有count/256种,
若同色球之间有区别,那么排 ...

算法有错误吧，但是现在找不出来，
4*4时应该有6^4种排法
6*6时应该有20^6种排法，
好像跟杨辉三角有些联系
                                     1              //第0层
                                                     1   1
                                                  1    2   1
                                                1   3   3   1
                                              1  4    6   4   1
                                            1  5  10  10  5   1
                                          1  6 15  20 15  6  1
                                        .................................
如果是N*N时，每一行的排法种类则是第N层中间的那个数