。。。

类格雷码顺序生成分划…
某种基于递归的构造。

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

const int N = 100;
int A[N], C[N]; string SS[N];
string S;
int n;

vector<string> res;

void encode(){
	/*for (int i=0;i<n;i++)
		cout << A[i] << " ";
	cout << endl;
	 */
	 
	
	int m = 0;
	for (int i=0;i<n;i++)
		m = max(m, A[i]);
	for (int i=0;i<=m;i++)
		SS[i].clear();
	S.clear();	
	
	for (int i=0;i<n;i++){
		if (i==9) SS[A[i]] += "10";
		else SS[A[i]] += char(i + 49);
		SS[A[i]] += ',';
	}
	
	for (int i=0;i<=m;i++){
		SS[i].erase(SS[i].size()-1);
		S += "{", S += SS[i], S += "},";
	}
	
	
	S.erase(S.size()-1);
	res.push_back(S);
}

void dfs(int k, int m){
	if (k==n){
		encode();
	}
	else {
		
		if ((C[k]&1)==0){
			for (int i=0;i<=m;i++)
				A[k] = i, dfs(k+1, m);
			A[k] = m+1, dfs(k+1, m+1);
		}
		else { 
			
			A[k] = m+1, dfs(k+1, m+1);
			for (int i=m;i>=0;i--)
				A[k] = i, dfs(k+1, m);
		}
	
		C[k]++;
	}
}


int main(){
	while (cin >> n){
		res.clear();
		memset(C, 0, sizeof(C));
		
		dfs(1, 0);
		cout << res.size() << endl;
		for (int i=0;i<res.size();i++)
			cout << res[i] << endl;
	}
}

Posted by xiaodao
Category: 日常