1〜18桁の高橋の数 (http://masami.d2.r-cms.jp/blog_detail/blog_id=3&id=6) を求める。力技の割には意外と速い。

takahashi_num_1_18.c

// 1桁〜18桁までの高橋の数を求める。
// 高橋の数 : http://masami.d2.r-cms.jp/blog_detail/blog_id=3&id=6
#include <stdio.h>
#include <stdbool.h>

// 高橋の数を格納する型。
typedef long long num_t;
#define PRId_num_t "lld"

// 自然数から各桁を構成する数字を数える。
// counts[n] : n の出現数
void count_digits(num_t n, int counts[restrict static 10])
{
	for(size_t i = 0; i < 10; i++)
	{
		counts[i] = 0;
	}

	while(n > 0)
	{
		counts[n % 10]++;
		n /= 10;
	}
}

// counts から構成できる最大の自然数を返す。
// counts[n] : n の出現数
num_t counts_to_max(const int counts[restrict static 10])
{
	num_t n = 0;
	for(int i = 9; i >= 0; i--)
	{
		for(int j = 0; j < counts[i]; j++)
		{
			n = n * 10 + i;
		}
	}

	return n;
}

// counts から構成できる最小の自然数を返す。
// ここで、最上位桁は0以外となるようにする (counts[0]以外が0の場合を除く)
// c
num_t counts_to_min(const int counts[restrict static 10])
{
	num_t n = 0;

	// minimum digits other than 0
	int min_dig = 0;
	for(int i = 1; i < 10; i++)
	{
		if(counts[i] > 0)
		{
			min_dig = i;
			break;
		}
	}
	n = min_dig;

	for(int i = 0; i < 10; i++)
	{
		int c = (i == min_dig)? counts[i] - 1: counts[i];
		for(int j = 0; j < c; j++)
		{
			n = n * 10 + i;
		}
	}
	return n;
}


bool are_same_counts(const int c1[restrict static 10], const int c2[restrict static 10])
{
	for(int i = 0; i < 10; i++)
	{
		if(c1[i] != c2[i])
		{
			return false;
		}
	}
	return true;
}

// counts から構成できる高橋の数があればその数、なければ (num_t)-1。
// counts[n] : n の出現数
num_t takahashi_num(const int counts[restrict static 10])
{
	num_t min = counts_to_min(counts);
	num_t max = counts_to_max(counts);
	num_t diff = max - min;
	int diff_counts[10];
	count_digits(diff, diff_counts);
	if(are_same_counts(counts, diff_counts))
	{
		return diff;
	}
	else
	{
		return (num_t)-1;
	}
}


// counts[index] から counts[9] の合計が sum となるような
// 全パターン (各要素は0以上) に対して callback を呼び出す。
void enum_sets(
	int counts[restrict static 10],
	int sum, int index,
	void (*callback)(const int counts[restrict static 10]))
{
	if(sum == 0)
	{
		for(int i = index; i < 10; i++)
		{
			counts[i] = 0;
		}
		callback(counts);
	}
	else if(index == 9)
	{
		counts[index] = sum;
		callback(counts);
	}
	else
	{
		for(int i = 0; i <= sum; i++)
		{
			counts[index] = i;
			enum_sets(counts, sum - i, index + 1, callback);
		}
	}
}


void callback(const int counts[restrict static 10])
{
	num_t t = takahashi_num(counts);
	if(t != (num_t)-1)
	{
		printf("%"PRId_num_t"\n", t);
	}
}

int main(void)
{
	int counts[10];

	// 1 桁から 18 桁まで。
	for(int i = 1; i <= 18; i++)
	{
		enum_sets(counts, i, 0, callback);
	}

	return 0;
}

takahashi_num_opt_1_18.c

// 1桁〜18桁までの高橋の数を求める。
// 高橋の数 : http://masami.d2.r-cms.jp/blog_detail/blog_id=3&id=6
// 高橋の数が 9 の倍数であるという性質を利用して枝刈りを行っている。
#include <stdio.h>
#include <stdbool.h>

// 高橋の数を格納する型。
typedef long long num_t;
#define PRId_num_t "lld"

// 自然数から各桁を構成する数字を数える。
// counts[n] : n の出現数
void count_digits(num_t n, int counts[restrict static 10])
{
	for(size_t i = 0; i < 10; i++)
	{
		counts[i] = 0;
	}

	while(n > 0)
	{
		counts[n % 10]++;
		n /= 10;
	}
}

// counts から構成できる最大の自然数を返す。
// counts[n] : n の出現数
num_t counts_to_max(const int counts[restrict static 10])
{
	num_t n = 0;
	for(int i = 9; i >= 0; i--)
	{
		for(int j = 0; j < counts[i]; j++)
		{
			n = n * 10 + i;
		}
	}

	return n;
}

// counts から構成できる最小の自然数を返す。
// ここで、最上位桁は0以外となるようにする (counts[0]以外が0の場合を除く)
// c
num_t counts_to_min(const int counts[restrict static 10])
{
	num_t n = 0;

	// minimum digits other than 0
	int min_dig = 0;
	for(int i = 1; i < 10; i++)
	{
		if(counts[i] > 0)
		{
			min_dig = i;
			break;
		}
	}
	n = min_dig;

	for(int i = 0; i < 10; i++)
	{
		int c = (i == min_dig)? counts[i] - 1: counts[i];
		for(int j = 0; j < c; j++)
		{
			n = n * 10 + i;
		}
	}
	return n;
}


bool are_same_counts(const int c1[restrict static 10], const int c2[restrict static 10])
{
	for(int i = 0; i < 10; i++)
	{
		if(c1[i] != c2[i])
		{
			return false;
		}
	}
	return true;
}

// counts から構成できる高橋の数があればその数、なければ (num_t)-1。
// counts[n] : n の出現数
num_t takahashi_num(const int counts[restrict static 10])
{
	num_t min = counts_to_min(counts);
	num_t max = counts_to_max(counts);
	num_t diff = max - min;
	int diff_counts[10];
	count_digits(diff, diff_counts);
	if(are_same_counts(counts, diff_counts))
	{
		return diff;
	}
	else
	{
		return (num_t)-1;
	}
}


// counts[index] から counts[9] の合計が sum となるような
// パターン (各要素は0以上) のうち、counts[i] * i の合計が 9 の倍数となる
// ものに対して callback を呼び出す。
void enum_sets(
	int counts[restrict static 10],
	int sum, int index, int weight_sum,
	void (*callback)(const int counts[restrict static 10]))
{
	if(sum == 0)
	{
		if(weight_sum % 9 == 0)
		{
			for(int i = index; i < 10; i++)
			{
				counts[i] = 0;
			}
			callback(counts);
		}
	}
	else if(index == 9)
	{
		// 正確には、weight_sum + index * sum が
		// 9の倍数か否かの判定だが、index * sum = 9 * sum
		// は9の倍数であることが確定しているので、わざわざ
		// 足して判定する必要はない。
		if(weight_sum % 9 == 0)
		{
			counts[index] = sum;
			callback(counts);
		}
	}
	else
	{
		for(int i = 0; i <= sum; i++)
		{
			counts[index] = i;
			enum_sets(counts, sum - i, index + 1, weight_sum + i * index, callback);
		}
	}
}


void callback(const int counts[restrict static 10])
{
	num_t t = takahashi_num(counts);
	if(t != (num_t)-1)
	{
		printf("%"PRId_num_t"\n", t);
	}
}

int main(void)
{
	int counts[10];

	// 1 桁から 18 桁まで。
	for(int i = 1; i <= 18; i++)
	{
		enum_sets(counts, i, 0, 0, callback);
	}

	return 0;
}