順列生成　Cプログラム(2)

C

　ネットで調べて、作ってみました。やはり、自作よりネットで調べた方が速いみたいです。(^_^;

/* genperm.c */
#include <stdio.h>

#define MAXN 16		/* nの最大値 */
#define Swap(x,y)	{int _t=x; x=y; y=_t;}

int Perm[MAXN+1];	/* 結果はPerm[1]からPerm[n]に入ります。 */
int InitGenPerm=0;	/* 初期化用グローバル変数 */

/* 順列生成 : 1からnまでの辞書式順列を生成 */
int GenPerm(int n)
{
	int i,j,k,t;

	if(n>MAXN) return(InitGenPerm=0);
	
	if(InitGenPerm){
		for(i=n-1; Perm[i]>Perm[i+1]; i--);
		if(!i) return(InitGenPerm=0);
		
		for(t=k=n+1,j=i+1;j<=n;j++)
			if(Perm[j]>=Perm[i] && Perm[j]<t) t=Perm[k=j];
		if(k!=n+1) Swap(Perm[i],Perm[k]);
	
		for(j=i+1,k=n;j<k;j++,k--)
			Swap(Perm[j],Perm[k]);
	}else{
		/* 最初に1回だけ初期化 */
		Perm[0]=Perm[n+1]=0;
		for(i=1;i<=n;i++) Perm[i]=i;	
	}

	return(InitGenPerm=1);
}

#if 1 /* テスト用 */
int main(void)
{
	int i,c=0;
	int n=5;	/* nを自由に変えてお試しください。 */
	
	while(GenPerm(n)){
		for(i=1; i<=n; i++)
			printf("%d ",Perm[i]);
		printf(" :  %d\n",++c);
	}
	
	return(0);
}
#endif

※参考URL
●Ｃ プログラミング(基礎と応用)

プログラムの開発
6.順列生成の開発Ⅰ(pdfファイル) 182k 　

http://jubilo.cis.ibaraki.ac.jp/~isemba/PROGRAM/CPROG/c.shtml
http://jubilo.cis.ibaraki.ac.jp/~isemba/PROGRAM/CPROG/236.pdf

●よしいずの雑記帳　 再帰呼び出しを使わずに順列や組合せを得るC言語プログラム (2)
●SEND MORE MONEY(3) C言語プログラム - rscの日記