第８章 組み合わせ解析 駆け足で読む『離散数学〜コンピュータサイエンスの基礎数学』

本駆け足シリーズの全体の目次はこちら

• 階乗 n!、２項係数 binomial coefficient、順列 premutation、r-順列 r-permutation(permutation of the n objects taken r at a time)、重複順列、組み合わせ combination、r-組み合わせ r-combination、順序分割 ordered partitions(細胞 cellsへの分割)
• プログラミング問題
  
  • 階乗、順列数、組み合わせ数、重複順列->Combination

public class Combination {
	public static void main(String[] args) {

		//k!

		int k=3;

		int ka=NFact(k);

		System.out.println("k=" + k + " k!=" + ka);

		//permutation

		int a=5;

		int b=2;

		int ab=NPerm(a,b);

		System.out.println("Perm("+a+","+b+")="+ab);

		//combination

		int n=5;

		int m=3;

		int nm = NComb(n,m);

		System.out.println(n+"_C_"+m+ "= " + nm);

		

		//general permutation

		String[] st ={"1","2","3","3"};

		String[] gp = GeneralPermutation(st);

		

		System.out.println("General permutaion ");

		String ss="";

		System.out.println("No general permutation= "+gp.length);

		for(int i=0;i<gp.length;i++){

			ss+=gp[i] + ",";

		}

		ss+="\n";

		System.out.println(ss);

	}

	public static int NFact(int k){

		int ret=1;

		for(int i=1;i<=k;i++){

			ret*=i;

		}

		return ret;

	}

	public static int NComb(int m,int k){

		int ret=1;

		int a = NFact(m);

		int b1 = NFact(k);

		int b2 = NFact(m-k);

		ret = a/b1/b2;

		return ret;

	}

	public static int NPerm(int m,int k){

		int ret=1;

		int a = NFact(m);

		//int b1 = NFact(k);

		int b2 = NFact(m-k);

		ret = a/b2;

		return ret;

	}

	/*

	 * Courtesy to Mr. Okumura

	 * /**

	 * 順列を生成する Enumeration

	 * N 個の要素から順列を生成する個数は N!

	 * （参考）Ｃ言語によるアルゴリズム入門

	 */

	public static String[] GeneralPermutation(String[] s){

		

		Enumeration e = new PermEnum(s);

		int Nperm=NPerm(s.length,s.length);

		String[] st=new String[Nperm];

		int count = 0;

		while(e.hasMoreElements()) {

			String[] a = (String[])e.nextElement();

			System.out.println("a len " + a.length);

			st[count]="";

			for(int i=0;i<a.length;i++){

				st[count]+=a[i];

			}

			

			count++;

		}

		System.out.println("count="+count);

		String[] distinctSt = new String[0];

		for(int i=0;i<st.length;i++){

			boolean flag = true;

		

			for(int j=0;j<distinctSt.length;j++){

				if(st[i].equals(distinctSt[j])){

					flag=false;

					break;

				}	

			}

			if(flag){

				String[] tmp = new String[distinctSt.length];

				for(int j=0;j<tmp.length;j++){

					tmp[j]=distinctSt[j];

				}

				distinctSt = new String[distinctSt.length+1];

				for(int j=0;j<tmp.length;j++){

					distinctSt[j]=tmp[j];

				}

				distinctSt[distinctSt.length-1]=st[i];

			}

		}

		

		

		

		

		return distinctSt;

	}

}