順列生成　Cプログラム

C

　順列生成プログラムをCで作ってみました。自作ですのでたぶん効率よくないです。(^_^;
　再帰を使ったのものが主流である中、非再帰のものは珍しいかも。(^_^;
ずっと昔に、N-88BASICで自作したものをCに翻訳して改良しました。(^_^;

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

#define MAXN 16	/* nの最大値 */

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

/* 順列生成 : 1からnまでの順列を生成 */
int GenPerm(int n)
{
	static int i[MAXN+1];
	int j,k,flag;

	if(n>MAXN) return(InitGenPerm=0);
	if(InitGenPerm){
		for(k=n; i[k]==n; k--);
		i[k]++;
	}else
		i[k=1]=1;	/* 最初に1回だけ初期化 */
		
	while(k>0){
		while(1){		/* 無限ループ */
			Perm[k]=i[k];
			for(flag=0,j=1; j<k; j++)
				if(Perm[k]==Perm[j]) flag=1;
			if(flag)		break;
			else if(k==n)	return(InitGenPerm=1);
			else		i[++k]=1;
		}
		for(; i[k]==n; k--);
		i[k]++;
	}
	return(InitGenPerm=0);
}

#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

　これを使って、前回の【プログラム　クイズ】の回答を書き直してみました。

/* Quiz_Opr2.c */
#include <stdio.h>
/* genperm.c の main を #if 0 〜 #endif で無効化して _genperm.c に改名したソース */
#include "_genperm.c"
/* calc.c の main を #if 0 〜 #endif で無効化して _calc.c に改名したソース */
#include "_calc.c"

/* _calc.c を使いやすくするための関数 */
double Evaluate(char *src)
{
	point = 0;
	strcpy(expr,src);
	return(getValue());
}

/* 左辺と右辺を得る */
void GetLhsAndRhs(char *s,char *l,char *r)
{
	while(*s!='=')
		*l++=*s++;
	*l='\0',s++;
	while(*s)
		*r++=*s++;
	*r='\0';
}

#define Op(i)	opr[Perm[(i)+1]-1]		/* 略記用 */	

int main(void)
{
	char opr[8]="+-*/=";		/* 少し多めに余裕をもって */
	char buf[32],lhs[32],rhs[32];
	
	while(GenPerm(5)){
		if(Op(4)=='/') continue; /* ÷0は _calc.c でエラーになるのでスキップ */
		sprintf(buf,"5%c4%c3%c2%c1%c0",Op(0),Op(1),Op(2),Op(3),Op(4));
		printf("%s",buf);
		GetLhsAndRhs(buf,lhs,rhs);	/* 左辺と右辺を得る */
		if(Evaluate(lhs)==Evaluate(rhs))	printf(" <--- Hit\n");
		else				printf("\n");
	}
	
	return(0);
}

※参考URL
http://q.hatena.ne.jp/1296542184
http://d.hatena.ne.jp/rsc96074/20110202/1296655979
　こちらの順列生成アルゴリズムの方がいいようです。(^_^;
●よしいずの雑記帳　 再帰呼び出しを使わずに順列や組合せを得るC言語プログラム (2)
●SEND MORE MONEY(3) C言語プログラム - rscの日記

P.S.
　使用した関数電卓のソース calc.c がリンク切れになっているようなので、EZFUNC のソースを使って Evaluate 関数等を書き直してみました。(^_^;
●ちょっと前のクイズ（3）