UVa 10063 - Knuth's Permutation

1321 단어
제목: 크누스 서열, 배열 조합을 만드는 방법.
새 문자로 이전 문자열의 조합에 삽입될 때마다 빈 문자열이 시작됩니다.
분석: 귀속, 체인 테이블.체인 테이블을 이용하여 저장하고 직접 귀속하여 해답을 구하면 된다.
설명: 마지막 그룹의 출력 후 빈칸이 있든 없든 상관없는 것 같고, 빈 줄의 데이터가 없는 것 같습니다.
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>

using namespace std;

char data[11];
char save[3628800][11];
int  used[11];

typedef struct noded
{
	char   data;
	noded* next;
}dnode;
dnode  D[11];
dnode* Head;

int  Count;
void dfs( int d, int n )
{
	if ( d == n ) {
		dnode* p = Head;
		for ( int i = 0 ; i < n ; ++ i ) {
			save[Count][i] = p->data;
			p = p->next;
		}
		save[Count ++][n] = 0;
		return;
	}
	dnode *p = Head,*q = p;
	for ( int i = 0 ; i <= d ; ++ i ) {
		//  
		D[d].data = data[d];
		D[d].next = p;
		if ( !i ) Head = &D[d];
		else q->next = &D[d];
		//  
		dfs( d+1, n );
		//  
		if ( !i ) Head = p;
		else q->next = p;
		
		q = p;
		if ( i < d ) p = p->next;
	}
}

int main()
{
	int count = 0; 
	while ( scanf("%s",data) != EOF ) {
		if ( count ++ ) printf("
"); Count = 1; memset( save, 0, sizeof(save) ); dfs( 0, strlen(data) ); for ( int i = 1 ; i < Count ; ++ i ) printf("%s
",save[i]); } return 0; }

좋은 웹페이지 즐겨찾기