排列数、组合数生成算法

输入n，r
输出C（r，n），A（r，n）即所有的排列方式，组合方式

先考虑组合，如果能够得到所有的组合数情况，只要分别对这些组合做排列计算即可
要想输出所有的组合情况，必须按照一定的次序，可以按照字典顺序输出所有情况。假设n=4，r=2，那么第一个组合数是1 2，第二个是13。。。第六个是3 4。可以看出组合数的倒数第一位不超过n，倒数第二位不超过n-1，。。。倒数第r位不能超过n-r+1，同时右边的数总是大于左边的数。所以对于任意给定的一个组合，如果其最右边没达到所能达到的最大值，只需将最右边数+1即可得到下一个组合数，如果最右边已经不能再大了，考虑倒数第二位，如果倒数第二位没有达到最大值，将倒数第二位+1，同时这位以后的数字依次比前一个数大1，如果倒数第二位不能再大了，考虑倒数第三位，将倒数第三位+1，同时这位以后的数字依次比前一个数大1。。。。直到倒数第r个数即第一个数已经不能再大了
算法实现如下：

int next_combination(int *num, int n, int r)
{
bool has_next = false;
int i = 0;
for (i = 0; i < r; i++)
if (num[r - i - 1] < n - i) {
num[r - i - 1]++;
has_next = true;
break;
}
if (has_next) {
for (int j = i; j > 0; j--) {
num[r - j] = num[r - j - 1] + 1;
}
return 1;
}
return 0;
}

下面考虑排列
这里也按照字典顺序输出所有排列，假设有排列S₁，S₂，，。。。S_n，要想得到下一个排列，则需要从右向左扫描，找出第一个位置S_m，满足S_m<S_m+1，S_m左边的部分不变，调整S_m及其右边部分即可得到下一个排列。S_m右边部分是递减的，从右向左扫描，找出第一个S_k，满足S_k>S_m，交换S_k，S_m   的值，现在的情况是，从S_m+1到S_n是递减的，再将这部分元素逆置，得到最终结果，算法描述如下：

int next_permutation(int *num, int n)
{
if (n <= 1)
return 0;
int m = n - 2;
while (num[m] > num[m + 1] && m >= 0)
m--;
if (m < 0)
return 0;
int k = n - 1;
while (num[m] > num[k])
k--;
std::swap(num[m], num[k]);
int p = m + 1;
int q = n - 1;
while (p < q) {
std::swap(num[p], num[q]);
p++;
q--;
}
return 1;
}

回到开头，输入n，r，先调用next_combination得到一个排列，再对这个排列调用next_permutation即可得到最后的排列情况。如果只需要组合情况，只需调用next_combination

测试程序：

for (int i = 0; i < r; i++)

res[i] = i + 1;

int *tmp = new int[r];

do {

memcpy(tmp, res, r * sizeof(int));

do {

output_combination(tmp, r);

     } while (next_permutation(tmp, r));

} while (next_combination(res, n, r));

delete tmp;

delete res;

要把第一次实现RMI的过程记录下来

服务器端：
定义 客户端要访问的接口
 package com.tx.distributed;

import java.rmi.Remote;
import java.rmi.RemoteException;

public interface TimeGenerator extends Remote {

    java.util.Date getCurrentTime() throws RemoteException;

    String sayHello() throws RemoteException;

    void attach(DistributedClient obj, long d) throws RemoteException;

    void detach(DistributedClient obj) throws RemoteException;
}

实现接口
package com.tx.distributed;

import java.io.Serializable;
import java.rmi.NotBoundException;
import java.rmi.RMISecurityManager;
import java.rmi.RemoteException;
import java.rmi.registry.LocateRegistry;
import java.rmi.registry.Registry;
import java.rmi.server.UnicastRemoteObject;
import java.util.Calendar;
import java.util.Date;
import java.util.HashMap;

public class TimeGeneratorImpl implements TimeGenerator, Serializable {

    /**
     *
     */
    private static final long serialVersionUID = -3123942071701576393L;

    /**
     *
     */
    private HashMap<DistributedClient, Object> clients = new HashMap<DistributedClient, Object>();

    protected TimeGeneratorImpl() throws RemoteException {
        super();
    }

    public static void main(String[] args)
    {
        if (System.getSecurityManager() == null) {
            System.setSecurityManager(new RMISecurityManager());
        }
        try {
            String name = "TimeGenerator";
            TimeGenerator timeGenerator = new TimeGeneratorImpl();
            TimeGenerator stub = (TimeGenerator) UnicastRemoteObject
                    .exportObject(timeGenerator, 0);
            Registry registry = LocateRegistry.getRegistry();
            registry.rebind(name, stub);
            TimeGenerator t = (TimeGenerator) registry.lookup(name);
            System.out.println("Server started on: " + t.getCurrentTime());
        } catch (RemoteException e) {
            e.printStackTrace();
        } catch (NotBoundException e) {
            e.printStackTrace();

        }

    }

    @Override
    public Date getCurrentTime() throws RemoteException
    {
        Date date = new Date();

        return date;
    }

    @Override
    public String sayHello() throws RemoteException
    {
        return "Hello";
    }

    @Override
    public void attach(DistributedClient obj,long d) throws RemoteException
    {
        clients.put(obj, "");
        obj.update(new Date(Calendar.getInstance().getTimeInMillis() + d));
    }

    @Override
    public void detach(DistributedClient obj) throws RemoteException
    {
        clients.remove(obj);
    }

}
客户端回调接口
package com.tx.distributed;

import java.rmi.Remote;
import java.rmi.RemoteException;
import java.util.Date;

public interface DistributedClient extends Remote {
    public void update(Date d) throws RemoteException;
}
客户端
定义服务器端接口，跟服务器端接口一样
package com.tx.distributed;

import java.rmi.Remote;
import java.rmi.RemoteException;

public interface TimeGenerator extends Remote {
    java.util.Date getCurrentTime() throws RemoteException;

    String sayHello() throws RemoteException;

    void attach(DistributedClient obj, long d) throws RemoteException;

    void detach(DistributedClient obj) throws RemoteException;
}
模拟时钟客户端定义了回调函数的操作
package com.tx.distributed;

import java.io.Serializable;
import java.rmi.RemoteException;
import java.rmi.server.UnicastRemoteObject;
import java.util.Date;

public class AnalogueClock extends UnicastRemoteObject implements Serializable,
        DistributedClient {

    protected AnalogueClock() throws RemoteException {
        super();
    }

    /**
     *
     */
    private static final long serialVersionUID = -3432644283769542956L;

    @Override
    public void update(Date d) throws RemoteException
    {
        System.out.println("Analogue: " + d);
    }

}

实验
package com.tx.distributed;

import java.rmi.NotBoundException;
import java.rmi.RMISecurityManager;
import java.rmi.RemoteException;
import java.rmi.registry.LocateRegistry;
import java.rmi.registry.Registry;
import java.util.Date;

public class Test {

    /**
     * @param args
     */
    public static void main(String[] args)
    {
        if (System.getSecurityManager() == null) {
            System.setSecurityManager(new RMISecurityManager() {
                @Override
                public void checkConnect(String host, int port)
                {
                }

                @Override
                public void checkConnect(String host, int port, Object context)
                {
                }
            });
        }

        try {
            String name = "TimeGenerator";
            Registry registry = LocateRegistry.getRegistry("114.212.81.47");
            TimeGenerator timeGenerator = (TimeGenerator) registry.lookup(name);
            Date date = timeGenerator.getCurrentTime();
            System.out.println("Current time: " + date);
            AnalogueClock analogueClock = new AnalogueClock();
            DigitalClock digitalClock = new DigitalClock();
            timeGenerator.attach(analogueClock, 3600000);
            timeGenerator.attach(digitalClock, 3600000 * 2);
        } catch (RemoteException e) {
            e.printStackTrace();
        } catch (NotBoundException e) {
            e.printStackTrace();
        }
    }

}
 

2n个MM围成一圈，求相互接吻而不打扰另一对的方法数

将2n个人从0开始编号，从0到2n-1，从此往后，0只能和奇数号MM接吻，否则和一个偶数号MM发生关系的情况下，她们中间剩下奇数个MM，最后必然落单一个人
假设2n个人共有h（n）种接吻方法，当0号MM和1号MM接吻时，仅剩下2n-2个人，共有h(n-1)种方法，当0号MM和3号MM接吻时，她们的一边有2个人，有h（1）种方法，一边有2n-4个人，有h（n-2）种方法，当0号MM和5号MM接吻时，她们的一边有4个人，有h（2）种方法，一边有2n-6个人，有h（n-3）种方法，。。。。当0号MM和2n-1号MM接吻时，仅剩下2n-2个人，共有h（n-1)种方法。
可见，h（n）=h（0）×h（n-1）+h（1）×h（n-2）+h（2）×h（n-3）+......+h（n-1）×h（0）
这是Catalan数的一种形式，共有C（n，2n）/（n+1）种方法。