///////////////////////////////////////////////////////////////////////////////
// Copyright (C) 2007 Nakayama Masahito (m-nakayama@h7.dion.ne.jp) Osaka Japan
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
// 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
// 
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
///////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <windows.h>

// 経過時間計測
__int64 watch1 = 0;
void start_watch(void){
	QueryPerformanceCounter((LARGE_INTEGER *)&watch1);
}
void stop_watch(void){
	__int64 watch2 = 0, freq = 0;
	QueryPerformanceCounter((LARGE_INTEGER *)&watch2);
	QueryPerformanceFrequency((LARGE_INTEGER *)&freq);
	printf("elapsed = %.15f (msec)\n",(watch2-watch1)/(double)freq*1000.0);
}

// 結果格納
long stack[100]={-1};
long scnt = 1;
inline void push(long x){
	stack[scnt] = x;
	scnt++;
}
inline long pop(void){
	scnt--;
	return stack[scnt];
}
inline long empty_stack(void){
	stack[0] = -1;
	scnt = 1;
}

// 組合せ
void combination_bitwise(long m, long n)
{
	unsigned long max = 1 << m;

	register unsigned long i;
	for(i = 0; i < max; ++i){
		// count num of 1 bits
		unsigned long x = i;
		x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
		x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
		x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
		x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
		x = (x & 0x0000ffff) + ((x >>16) & 0x0000ffff);
		if(x != n)
			continue;
		// retrieve bits
		empty_stack();
		for(long j = 0; j < m; ++j){
			if(i & (1 << j))
				push(j);
		}
		// print result
		for(;;){
			long k = pop();
			if(k==-1)
				break;
			printf("%d ",k+1);
		}
		printf("\n");
	}
}

int main(void)
{
	start_watch();
	combination_bitwise(8, 3);
	stop_watch();

	start_watch();
	combination_bitwise(30, 10);
	stop_watch();

	//start_watch();
	//combination_bitwise(32, 11);
	//stop_watch();

	return 0;
}