Алгоритмическая задача о красках.

> А равномерность распределения гарантируется? Не могу сообразить...

если кратко — хз =) лет семь уже анализом алгоритмов не занимался, вряд ли смогу посчитать О даже для самого примитивного алгоритма…

я просто запускал несколько раз (≈пару–тройку десятков раз) (но не чаще, чем 1раз в 1сек, т.к. srand(time(0)) >_<") программу и смотрел счётчик вызовов и время выполнения, отсюда и выводы. если завтра будет время, и если додумаюсь, как более-менее просто и достаточно точно просчитать максимальное время поиска решения, обязательно сообщу =)

Имелась ввиду не сложность алгоритма, а результат его работы: не получится ли так, что одна раскраска будет встречаться в 2 раза чаще другой?

> эскиз. вопросы?

Как будет вместо эскиза работающая программа, так и приходи ;D

> не получится ли так, что одна раскраска будет встречаться в 2 раза чаще другой?

эм… не совсем понял… имеется в виду a=b=c & d=e + зеркало + поворот? да, такое будет, но абсолютно одинаковых раскрасок — нет.

> а по поводу объяснить… ой тяжело мне это ^_^'

Я все-таки попробую прояснить некоторые детали: 
массив rel - это разница в индексах с соседями, чей номер меньше текущего, или я не прав?

По алгоритму рекурсии:
1. начинаем заполнять от нулевого (первого) элемента.
2. если  i == 19, т.е. все элементы заполнены - то выходим.
3. Если i == центральный элемент - то переходим к следующему.
4. Далее идет randomize. Вроде бы как перемешивает номера цветов внутри массива inx. А как именно - было бы проще если бы в двух словах arsi нам это рассказал.
5. Далее в цикле перебираем краски. 
  а) Если краска закончилась, то след шаг цикла.
  б) Закрашиваем текущий элементу в краску.


Дальше пусть лучше расскажет arsi, я уверен, что у него лучше получится ;)

Таким образов всего 2 вопроса:

1) Что делалется в функции randomize? 2) Что происходит в цикле for внутри iterate.

//WBR

> массив rel - это разница в индексах с соседями, чей номер меньше текущего, или я не прав?

точно. в нём содержатся смещения к предыдущим (уже закрашенным) сотам, с которыми данная сота не должна совпадать. в примере на перле в одноимённом списке были абсолютные индексы.

> Далее идет randomize. Вроде бы как перемешивает номера цветов внутри массива inx. А как именно - было бы проще если бы в двух словах arsi нам это рассказал.

^_^' скажем так, не перемешивает, а заполняет массив числами от 0 до n-1 (при n ≤ sizeof(mask)*8, конечно же). а работает она очень просто: n раз получаем случайное число от 1 до n–i (т.е. [1..n], [1..n-1], ..., [1]). это случайное число будет указывать, сколько нулевых битов в маске нужно найти. как только будет найдено необходимое количество, цикл прерывается и переменная v будет содержать индекс этого бита + 1 (v увеличивается после каждой итерации; r уменьшается только если найден нулевой бит, и когда r достигает нуля — цикл прекращается). дальше индекс бита добавляется в массив и в маске соотв. бит устанавливается в единицу.

примерно так =)

по пунктам — да, всё верно.

> 2) Что происходит в цикле for внутри iterate.

в смысле этот цикл: {for (r = rel[i]; *r && ok; ++r) if (*p == p[*r]) ok = 0;} ?

у каждой соты может быть от нуля до трёх предыдущих соседей, а массив описан как rel[19][4], т.е. 4 ячейки на каждую соту, т.о. всегда после списка смещений к соседям будет 0 (т.к. не инициализированные элементы статического массива будут равны нулю). вот достижение этого значения и будет условием выхода из цикла, ну или ok станет ненулевым раньше. указатель r как раз и «бегает» по этому списку соседей. p — указатель на текущую ячейку массива cells ({p=&cells[i];}). т.о. p[-1], например, будет предыдущим относительно *p (по сути, p[i] ≡ *(p + i), так что ничто не мешает использовать отрицательные индексы). вот в условии и проверяется, ровно ли значение (закраска) текущей ячейки (соты) очередному соседу из списка. если да, то ok обнуляется и данный цикл прекращается.

хм… кстати, этот массив можно было записать так: {for (r = rel[i]; *r && *p != p[*r]; ++r);} тогда следующая проверка будет такой: {if (*r) continue;} т.о. избавляемся от переменной ok и всего, что с ней связано =) (тогда {ok = iterate(i + 1);} можно заменить на {if (iterate(i + 1)) return 1;} — всё равно после нахождения решения массив уже не понадобится; и {if (ok) return 1;} вообще убрать)

замечательно... а есть ли возможность модернизировать алгоритм. Сделать его параметризуемым. Т.е ввести некий параметр, каждому значению которого соответствует одно и только одно решение?

Чисто академический интерес. Первое что приходит на ум - номер решения. Но в случае рекурсивного алгоритма это не подходит. Может путь обхода? или что-либо еще?

Я не вижу смысла напрягаться ради оптимизации жалких 1М решений (которые остались после перестановок цветов).

> Я не вижу смысла напрягаться ради оптимизации жалких 1М решений (которые остались после перестановок цветов).

А как же вожделенный сферический конь в вакууме? :D

Вчера весь вечер ломал голову над как можно более плотной нумерацией раскрасок. Сразу скажу, что победы не вышло. За то придумал способ кодировки раскрасок, использующий менее 32 бит на раскраску.

Предлагается перечислять цвета ячеек в следующем порядке:

  	  	02	  	03	  	05
  	18	  	01	  	04	  	06
17	  	16	  	  	  	07	  	08
  	15	  	13	  	10	  	09
  	  	14	  	12	  	11

Цвет ячейки #1 ничем не ограничен, так что выбираем из 5 цветов.
Ячейки #1 и #2 - соседи, поэтому цвет ячейки #2 выбираем из 4 незанятых ячейкой #1 цветов.
Ячейки #1, #2 и #3 - соседи, поэтому цвет ячейки #3 выбираем из 3 незянатях ячейками #1 и #2 цветов.

Ячейки #1, #3 и #4 - соседи, поэтому цвет ячейки #4 выбираем из 3 незанятых ячейками #1 и #3 цветов.
Ячейки #3, #4 и #5 - соседи, поэтому цвет ячейки #5 выбираем из 3 незанятых ячейками #3 и #4 цветов.
Ячейки #4, #5 и #6 - соседи, поэтому цвет ячейки #6 выбираем из 3 незанятых ячейками #4 и #5 цветов.

Ячейки #4, #6 и #7 - соседи, поэтому цвет ячейки #7 выбираем из 3 незанятых ячейками #4 и #6 цветов.
Ячейки #6, #7 и #8 - соседи, поэтому цвет ячейки #8 выбираем из 3 незанятых ячейками #6 и #7 цветов.
Ячейки #7, #8 и #9 - соседи, поэтому цвет ячейки #9 выбираем из 3 незанятых ячейками #7 и #8 цветов.

И так далее.

Получается (5 * 4 * 3) * (3 * 3 * 3) * (3 * 3 * 3) * (3 * 3 * 3) * (3 * 3 * 3) * (3 * 3 * 3) = 20 * 3^16 = 860 934 420 способов выбрать цвета. Что меньше, чем 2^32 (и потому легко кодируется 32-битным числом).

Часть из этих способов не дает "хорошей" раскраски, так как не состыкует цвета ячеек #16 и #18 с цветами ячеек #1 и #2. Часть способов не дает "хорошей" раскраски, так как не укладывается в объем имеющихся "тюбиков".

За то нам известно, что всего "хороших" раскрасок 12*784565 = 9 414 780. Выходит, что в среднем примерно один из ста способов выбрать цвета по указанной схеме является "хорошим".

На самом деле цвет ячейки #18 можно не указывать, а определять по остаткам в "тюбиках". Это сокращает число способов в три раза - до 286 978 140, и в среднем каждый тридцатый способ - "хороший".

Способы имеют сквозную, взаимно однозначную нумерацию.

Есть еще путь, продложенный smh: исследовать структуру множества трансформаций, сохраняющих "хорошесть" раскраски. Возможно, из этого удалось бы вытянуть еще какие-то полезные сведения...

Выпускники матмеха ЛГУ не желают поупражняться в алгебре? :D

По просьбам трудящихся...

Тут можно уменьшить потребление оперативки взамен на потребление цпу. Т.е. сохранить в массив 2КБ (т.е. 1000 решений, номера которых образуют арифм. прогрессию) и от них уже плясать (т.е. искать решение номер "сохранненый+дельта").

З.Ы. Попытки *еще* уменьшить потребление памяти не интересны совсем.

> 1000 решений, номера которых образуют арифм. прогрессию

А они образуют? Каким образом нужно выбирать нумерацию, чтобы образовывали? O_o

А насчет *чисто алгебраического* если не решения, то сильного снижения количества вариантов -- возможно, что вполне реально. Только мне щас лень.

> А они образуют? Каким образом нужно выбирать нумерацию, чтобы образовывали?

Не 2-байтовые коды образуют арифм. прогрессию, а *номера*.

Еще потребление ЦПУ можно снизить, если внутри всех этих интервалов решение[789n]...решение[789(n+1)] коды окажется приблизительно линейно зависящими от номера, для каждого интервала можно будет найти максимальное отклонение от линейной функции *и* эти интервалы не будут пересекаться. Но это уже х.з.

s/эти интервалы не будут/...интервалы, которые дает отклонение от линейной функции не будут/

Угу, понял.

Уже знаем, что "хороших" раскрасок всего 12*784565. Так вот 784565 = 5 * 156913, и (если верить интернетам) 156913 - простое число! Вдруг это не просто совпадение?

Это говорит о том, что одновременно повороты и перестановки цветов выбрасывать нельзя. Иначе бы делилось на 6. Видимо, существуют решения, переходящие в себя при перестановке и последующем повороте. Хм.

> Это говорит о том, что одновременно повороты и перестановки цветов выбрасывать нельзя. Иначе бы делилось на 6. Видимо, существуют решения, переходящие в себя при перестановке и последующем повороте. Хм.

Совершенно верно. Но более того это говорит о том, что повороты и отражения выбрасывать нельзя вообще, либо как-то кодировать число от 1 до 24 (6 (кол-во поворотов) * 4 (кол-во отражений)), вместе с решением.

> исследовать структуру множества трансформаций, сохраняющих "хорошесть" раскраски

Какая самая простая трансформация? Перестановка местами двух ячеек.

Как понять, совмещаются ли две "хороших" раскраски при помощи простейшей трансформации? Записи этих раскрасок отличаются ровно двумя символами.

Как понять, можно начать с какой-нибудь "хорошей" раскраски, и пользуясь только простейшими трансформациями перечислить вообще все "хорошие" раскраски? Надо построить граф, где вершины - "хорошие" раскраски, а ребра - простейшие транформации. И посчитать, сколько компонент связности у графа.

Как можно строить граф? Есть два пути:

Путь #1. Для каждой "хорошей" раскраски перебрать по очереди все простейшие перестановки, и посмотрять, не получилось ли другой "хорошей" раскраски. Если получилось, узнать ее номер, и построить ребро. Простейших перестановок не так много (18*17=306), так что ничего ужасного в этом переборе нет.

Путь #2. Перебрать все пары "хороших" раскрасок. Некоторые из них будут отличаться как раз на простейшую перестанову. Номера узнавать не надо - мы с них начинаем. Так что ребро у нас в руках. Этим путем я и пошел. Вот только беда - пар "хороших" раскрасок дохрена - примерно 10^14 штук.  Когда сообразил, что есть путь #1, было уже поздно :D Надеюсь, за пару суток досчитает :D

=========================================

#include <algorithm>
#include <string>
#include <vector>
#include <iostream>
#include <fstream>
#include <cassert>

#include <stdint.h>

#include <errno.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>

inline bool magick(uint64_t a) // hot!
{
	a |= (a >> 1) | (a >> 2);
	a &= 0x9249249249249;
	a &= a - 1;
	a &= a - 1;
	return !a;
}

#define EXACT_SIZE ( 12 * 784565 )
#define BLOCK_SIZE ( 2048 )
#define APPROX_SIZE ( ( (EXACT_SIZE/BLOCK_SIZE) + 1 ) * BLOCK_SIZE )

void work(const uint64_t *c, size_t offset, size_t step, std::ostream &stream)
{
	for(size_t ii =  0; ii < APPROX_SIZE; ii += BLOCK_SIZE)
	for(size_t jj = ii; jj < APPROX_SIZE; jj += BLOCK_SIZE)
	for(size_t i = offset; i < BLOCK_SIZE; i += step)
	for(size_t j = 0; j < BLOCK_SIZE; ++j)
	if(__builtin_expect(magick(c[ii + i]^c[jj + j]), 0))
	{
		if(ii + i < jj + j) if(jj + j < EXACT_SIZE)
		stream << ii + i << "\t" << jj + j << std::endl;
	}
}

void fork_and_work(const uint64_t *c, size_t fork_degree)
{
	size_t n = (1 << fork_degree);
	assert(BLOCK_SIZE % n == 0);
	for(size_t i = 0; i < n; ++i)
	{
		if(fork() == 0)
		{
			std::string file_name("graph.");
			file_name.append("x", i + 1);
			std::ofstream stream(file_name.c_str());
			work(c, i, n, stream);
			return;
		}
	}
	while(wait(0) != -1 && errno != ECHILD)
	{
	}
	return;
}

void lower_priority()
{
	for(int i = 0; i < 20; ++i)
	{
		nice(1);
	}
}

class Coloring
{
	char c[18];

//			0		1		2
//		3		4		5		6
//	7		8				9		10
//		11		12		13		14
//			15		16		17

public:

	void Reset()
	{
		c[ 0] = 'a';
		c[ 1] = 'a';
		c[ 2] = 'a';
		c[ 3] = 'a';
		c[ 4] = 'b';
		c[ 5] = 'b';
		c[ 6] = 'b';
		c[ 7] = 'b';
		c[ 8] = 'c';
		c[ 9] = 'c';
		c[10] = 'c';
		c[11] = 'c';
		c[12] = 'd';
		c[13] = 'd';
		c[14] = 'd';
		c[15] = 'e';
		c[16] = 'e';
		c[17] = 'e';
	}

	bool Next()
	{
		return std::next_permutation(c, c + sizeof(c));
	}

	bool IsMonotoneABC() const
	{
		char max = 'a' - 1;
		for(unsigned i = 0; i < sizeof(c); ++i)
		{
			char x = c[i];
			if(x == 'a' || x == 'b' || x == 'c')
			{
				if(x > max)
				{
					if(x != max + 1)
					{
						return false;
					}
					max = x;
				}
			}
		}
		return true;
	}

	bool IsMonotoneDE() const
	{
		char max = 'd' - 1;
		for(unsigned i = 0; i < sizeof(c); ++i)
		{
			char x = c[i];
			if(x == 'd' || x == 'e')
			{
				if(x > max)
				{
					if(x != max + 1)
					{
						return false;
					}
					max = x;
				}
			}
		}
		return true;
	}

	bool IsGood() const
	{
		return
			c[ 0] != c[ 1] && c[ 0] != c[ 3] && c[ 0] != c[ 4] &&
			c[ 1] != c[ 2] && c[ 1] != c[ 4] && c[ 1] != c[ 5] &&
			c[ 2] != c[ 5] && c[ 2] != c[ 6] &&
			c[ 3] != c[ 4] && c[ 3] != c[ 7] && c[ 3] != c[ 8] &&
			c[ 4] != c[ 5] && c[ 4] != c[ 8] &&
			c[ 5] != c[ 6] && c[ 5] != c[ 9] &&
			c[ 6] != c[ 9] && c[ 6] != c[10] &&
			c[ 7] != c[ 8] && c[ 7] != c[11] &&
			c[ 8] != c[11] && c[ 8] != c[12] &&
			c[ 9] != c[10] && c[ 9] != c[13] && c[ 9] != c[14] &&
			c[10] != c[14] &&
			c[11] != c[12] && c[11] != c[15] &&
			c[12] != c[13] && c[12] != c[15] && c[12] != c[16] &&
			c[13] != c[14] && c[13] != c[16] && c[13] != c[17] &&
			c[14] != c[17] &&
			c[15] != c[16] &&
			c[16] != c[17];
	}

	std::string ToString() const
	{
		return std::string(c, c + sizeof(c));
	}

	uint64_t ToUInt64() const
	{
		uint64_t ret = 0;
		for(unsigned i = 0; i < sizeof(c); ++i)
		{
			ret <<= 3;
			ret |= c[i] - 'a';
		}
		return ret;
	}
};

int main()
{
	lower_priority();

	std::vector<uint64_t> v;
	v.reserve(APPROX_SIZE);

	Coloring c;
	c.Reset();
	while(c.Next()) if(c.IsGood())
	{
		v.push_back(c.ToUInt64());
	}

	assert(v.size() == EXACT_SIZE);
	v.resize(APPROX_SIZE);

	fork_and_work(&v.front(), 1);

	return 0;
}

s/18*17=306/18*17*0.5=153/

А для узнавания номеров можно было б хеш-таблицу прикрутить... Мне бы эту идею, да на два часа раньше :(

> А для узнавания номеров можно было б хеш-таблицу прикрутить... Мне бы эту идею, да на два часа раньше :(

Я же говорил, что жалкие 1М вариантов -- не место для приложения ума. В том числе и потому, что можно польститься на брутфорс. Было бы у тебя 10^28 вместо 10^14, ты бы точно подумал еще 2 часа :-)

> Но более того это говорит о том, что повороты и отражения выбрасывать нельзя вообще, либо как-то кодировать число от 1 до 24 (6 (кол-во поворотов) * 4 (кол-во отражений)), вместе с решением.

Попробуйте отбросить все повороты+отражения, численно? Не отбрасывая при этом перестановки цветов. Во-первых, я уверен, что разных сочетаний поворот+отражение не больше 12 (отражений существенно разных не 4, а 2). Во-вторых, как-то не очевидно, сколько в итоге получится разных "хороших" раскрасок. Будем знать еще один факт...

> В том числе и потому, что можно польститься на брутфорс.

Доказательство теоремы про планарные графы и 4 цвета тоже в конечном итоге сводится к брутфорсу ,)

Даже имея возможность брутфорсить (оверкилл!!), разломать сабжевую задачку не так-то просто. Игрушка для ума.

Впрочем, я уже попробовал. Вот количества "хороших" раскрасок:
9414780 -- если ничего не выкидывать
784565 -- если выкидывать только перестановки цветов
785267 -- если выкидывать только вращения+отражения
65823 -- если выкидывать и перестановки цветов, и вращения+отражения

Какое из этих четырех количеств подсчитывается - зависит от того, какие последние два аргумента у вызова функции GetMappings() из main().

Каждый запуск занимает от 3,5 до 6,5 минут, на Core2.

Надеюсь, багов у меня не налеплено... Хорошо бы, если б кто-нибудь независимо проверил эти факты.

=================================

#include <string>
#include <vector>
#include <cassert>
#include <algorithm>
#include <iostream>

#include <tr1/unordered_set>

class Coloring
{
	char c[18];

//	  	  	 0	  	 1	  	 2
//	  	 3	  	 4	  	 5	  	 6
//	 7	  	 8	  	  	  	 9	  	10
//	  	11	  	12	  	13	  	14
//	  	  	15	  	16	  	17

public:

	void Reset()
	{
		c[ 0] = 'a';
		c[ 1] = 'a';
		c[ 2] = 'a';
		c[ 3] = 'a';
		c[ 4] = 'b';
		c[ 5] = 'b';
		c[ 6] = 'b';
		c[ 7] = 'b';
		c[ 8] = 'c';
		c[ 9] = 'c';
		c[10] = 'c';
		c[11] = 'c';
		c[12] = 'd';
		c[13] = 'd';
		c[14] = 'd';
		c[15] = 'e';
		c[16] = 'e';
		c[17] = 'e';
	}

	bool Next()
	{
		return std::next_permutation(c, c + sizeof(c));
	}

	bool IsMonotoneABC() const
	{
		char max = 'a' - 1;
		for(unsigned i = 0; i < sizeof(c); ++i)
		{
			char x = c[i];
			if(x == 'a' || x == 'b' || x == 'c')
			{
				if(x > max)
				{
					if(x != max + 1)
					{
						return false;
					}
					max = x;
				}
			}
		}
		return true;
	}

	bool IsMonotoneDE() const
	{
		char max = 'd' - 1;
		for(unsigned i = 0; i < sizeof(c); ++i)
		{
			char x = c[i];
			if(x == 'd' || x == 'e')
			{
				if(x > max)
				{
					if(x != max + 1)
					{
						return false;
					}
					max = x;
				}
			}
		}
		return true;
	}

	bool IsEqual(const Coloring &arg) const
	{
		for(unsigned i = 0; i < sizeof(c); ++i)
		{
			if(arg.c[i] != c[i])
			{
				return false;
			}
		}
		return true;
	}

	bool IsGood() const
	{
		return
			c[ 0] != c[ 1] && c[ 0] != c[ 3] && c[ 0] != c[ 4] &&
			c[ 1] != c[ 2] && c[ 1] != c[ 4] && c[ 1] != c[ 5] &&
			c[ 2] != c[ 5] && c[ 2] != c[ 6] &&
			c[ 3] != c[ 4] && c[ 3] != c[ 7] && c[ 3] != c[ 8] &&
			c[ 4] != c[ 5] && c[ 4] != c[ 8] &&
			c[ 5] != c[ 6] && c[ 5] != c[ 9] &&
			c[ 6] != c[ 9] && c[ 6] != c[10] &&
			c[ 7] != c[ 8] && c[ 7] != c[11] &&
			c[ 8] != c[11] && c[ 8] != c[12] &&
			c[ 9] != c[10] && c[ 9] != c[13] && c[ 9] != c[14] &&
			c[10] != c[14] &&
			c[11] != c[12] && c[11] != c[15] &&
			c[12] != c[13] && c[12] != c[15] && c[12] != c[16] &&
			c[13] != c[14] && c[13] != c[16] && c[13] != c[17] &&
			c[14] != c[17] &&
			c[15] != c[16] &&
			c[16] != c[17];
	}

	std::string ToString() const
	{
		return std::string(c, c + sizeof(c));
	}

	uint64_t ToUInt64() const
	{
		uint64_t ret = 0;
		for(unsigned i = 0; i < sizeof(c); ++i)
		{
			ret <<= 3;
			ret |= c[i] - 'a';
		}
		return ret;
	}

	Coloring Mirror() const
	{
		Coloring ret;
		ret.c[ 0] = c[ 2];
		ret.c[ 1] = c[ 1];
		ret.c[ 2] = c[ 0];
		ret.c[ 3] = c[ 6];
		ret.c[ 4] = c[ 5];
		ret.c[ 5] = c[ 4];
		ret.c[ 6] = c[ 3];
		ret.c[ 7] = c[10];
		ret.c[ 8] = c[ 9];
		ret.c[ 9] = c[ 8];
		ret.c[10] = c[ 7];
		ret.c[11] = c[14];
		ret.c[12] = c[13];
		ret.c[13] = c[12];
		ret.c[14] = c[11];
		ret.c[15] = c[17];
		ret.c[16] = c[16];
		ret.c[17] = c[15];
		return ret;
	}

	Coloring Rotate() const
	{
		Coloring ret;
		ret.c[ 0] = c[ 7];
		ret.c[ 1] = c[ 3];
		ret.c[ 2] = c[ 0];
		ret.c[ 3] = c[11];
		ret.c[ 4] = c[ 8];
		ret.c[ 5] = c[ 4];
		ret.c[ 6] = c[ 1];
		ret.c[ 7] = c[15];
		ret.c[ 8] = c[12];
		ret.c[ 9] = c[ 5];
		ret.c[10] = c[ 2];
		ret.c[11] = c[16];
		ret.c[12] = c[13];
		ret.c[13] = c[ 9];
		ret.c[14] = c[ 6];
		ret.c[15] = c[17];
		ret.c[16] = c[14];
		ret.c[17] = c[10];
		return ret;
	}

	Coloring SubstituteColors(const char s[5]) const
	{
		Coloring ret;
		ret.c[ 0] = s[c[ 0] - 'a'];
		ret.c[ 1] = s[c[ 1] - 'a'];
		ret.c[ 2] = s[c[ 2] - 'a'];
		ret.c[ 3] = s[c[ 3] - 'a'];
		ret.c[ 4] = s[c[ 4] - 'a'];
		ret.c[ 5] = s[c[ 5] - 'a'];
		ret.c[ 6] = s[c[ 6] - 'a'];
		ret.c[ 7] = s[c[ 7] - 'a'];
		ret.c[ 8] = s[c[ 8] - 'a'];
		ret.c[ 9] = s[c[ 9] - 'a'];
		ret.c[10] = s[c[10] - 'a'];
		ret.c[11] = s[c[11] - 'a'];
		ret.c[12] = s[c[12] - 'a'];
		ret.c[13] = s[c[13] - 'a'];
		ret.c[14] = s[c[14] - 'a'];
		ret.c[15] = s[c[15] - 'a'];
		ret.c[16] = s[c[16] - 'a'];
		ret.c[17] = s[c[17] - 'a'];
		return ret;
	}

	Coloring RotateColorsABC() const
	{
		const char s[5] = {'c', 'a', 'b', 'd', 'e'};
		return SubstituteColors(s);
	}

	Coloring MirrorColorsABC() const
	{
		const char s[5] = {'c', 'b', 'a', 'd', 'e'};
		return SubstituteColors(s);
	}

	Coloring MirrorColorsDE() const
	{
		const char s[5] = {'a', 'b', 'c', 'e', 'd'};
		return SubstituteColors(s);
	}

	Coloring SubstituteCells(unsigned i, unsigned j) const
	{
		Coloring ret(*this);
		ret.c[i] = c[j];
		ret.c[j] = c[i];
		return ret;
	}
};

void GetMappings(std::vector<Coloring> &v, const Coloring &c, bool rotate_and_mirror, bool substitute_colors)
{
	v.clear();

	v.push_back(c);

	if(rotate_and_mirror)
	for(unsigned i = 0, size = v.size(); i < size; ++i)
	{
		v.push_back(v[i].Mirror());
	}

	if(rotate_and_mirror)
	for(unsigned i = 0, size = v.size(); i < size; ++i)
	{
		v.push_back(v[i].Rotate());
		v.push_back(v.back().Rotate());
		v.push_back(v.back().Rotate());
		v.push_back(v.back().Rotate());
		v.push_back(v.back().Rotate());
	}

	if(substitute_colors)
	for(unsigned i = 0, size = v.size(); i < size; ++i)
	{
		v.push_back(v[i].RotateColorsABC());
		v.push_back(v.back().RotateColorsABC());
	}

	if(substitute_colors)
	for(unsigned i = 0, size = v.size(); i < size; ++i)
	{
		v.push_back(v[i].MirrorColorsABC());
	}

	if(substitute_colors)
	for(unsigned i = 0, size = v.size(); i < size; ++i)
	{
		v.push_back(v[i].MirrorColorsDE());
	}

	// sanity checks

	for(unsigned i = 0, size = v.size(); i < size; ++i)
	{
		assert(v[i].IsGood());
	}

	if(rotate_and_mirror && substitute_colors)
	{
		assert(v.size() == 12*12);
	}
	else if(rotate_and_mirror || substitute_colors)
	{
		assert(v.size() == 12);
	}
	else
	{
		assert(v.size() == 1);
	}
};

int main()
{
	Coloring c;
	c.Reset();

	std::vector<Coloring> v;
	std::tr1::unordered_set<std::string> s;

	while(c.Next()) if(c.IsGood())
	{
		GetMappings(v, c, false, false);

		bool unique = true;
		for(unsigned i = 0, size = v.size(); i < size; ++i)
		{
			if(s.find(v[i].ToString()) != s.end())
			{
				unique = false;
				break;
			}
		}
		if(unique)
		{
			s.insert(c.ToString());
			std::cout << c.ToString() << std::endl;
		}
	}

	return 0;
}

Ну вот, мой маленький брутфорс успешно уложился в 20 часов работы на Athlon64 x2. Распределение степеней вершин графа:

число вершин     степень
    432            11
   4824            12
  25704            13
 113256            14
 317232            15
 693432            16
1119456            17
1481208            18
1600344            19
1468800            20
1121028            21
 729828            22
 416232            23
 200916            24
  78876            25
  30600            26
   8796            27
   1944            28
   1620            29
     12            30
    180            31
     60            33

То есть 432 вершины степени 11, и 60 вершин степени 33. В целом ничего красивого. Как посчитаю число связных компонент - отпишусь.

Видимо не мне одному эта головоломка понравилась (:

> Первое что приходит на ум - номер решения.
> Но в случае рекурсивного алгоритма это не подходит.

почему же? можно и так, если время терпит.

это как решение задачи «сделать ракету для уничтожения истребителей»
по-русски и по-американски: пока американцы пихали в ракеты системы
самонаведения с искусственным интеллектом, русские в свои поставили
такой движок, что от момента её обнаружения до попадания
пилот элементарно не успеет сманеврировать ;)


-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----

#include <stdio.h>                                       
#include <stdlib.h>                                      
#include <time.h>                                        

static const char colors[12][5] = {
    "abcde", "acbde", "bacde", "bcade", "cabde", "cbade",
    "abced", "acbed", "baced", "bcaed", "cabed", "cbaed" 
};                                                       
static const char *cp;                                   

static char cells[19];
static char *cell = cells;
static const int rels[18][4] = {
    {0}, {-1}, {-1},            
    {-3}, {-4, -3, -1}, {-4, -3, -1}, {-4, -1},
    {-4}, {-5, -4, -1}, {-4, -3}, {-4, -1},    
    {-4, -3}, {-4, -1}, {-4, -1}, {-5, -4, -1},
    {-4, -3}, {-4, -3, -1}, {-4, -3, -1}       
};                                             
static const int *rel = *rels;                 

static int left[5] = { 4, 4, 4, 3, 3 };

#undef C
#define C(i) cp[(int)cells[i]]
static void display(void) {   
    printf("%c%c%c ", C(0), C(1), C(2));
    printf("%c%c%c%c ", C(3), C(4), C(5), C(6));
    printf("%c%c~%c%c ", C(7), C(8), C(9), C(10));
    printf("%c%c%c%c ", C(11), C(12), C(13), C(14));
    printf("%c%c%c\n", C(15), C(16), C(17));        
}                                                   

static int cnt;
static void iterate(void) {
    int c = 0;             
    const int *r;          
                           
    if (*cell == '.') {    
        if (!cnt--) {
            display();
            exit(0);
        }
    } else {
        do {
            if (!left[c])
                continue;
            if ((c == 1 && left[0] == 4) || (c == 2 && left[1] == 4) || (c == 4 && left[3] == 3))
                continue;
            for (r = rel; *r && c != cell[*r]; ++r);
            if (*r)
                continue;
            *cell = c;
            --left[c];
            rel += 4;
            ++cell;
            iterate();
            --cell;
            rel -= 4;
            ++left[c];
        } while (++c < 5);
    }
}

int main(int argc, char **argv) {
    if (argc > 1)
        cnt = atoi(argv[1]);
    else {
        srand(time(0));
        cnt = rand();
    }
    cnt %= 9414780;
    cp = colors[cnt % 12];
    cnt /= 12;
    cells[18] = '.';
    iterate();
    return 1;
}

-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----

на моей машине (AMD Athlon(tm) 64 X2 Dual Core Processor 4400+)
максимальное время поиска (решение №9414779) ≈0.3сек:

time ./solve-fast 9414779
ede dcbd ea~ca bcab abc

real    0m0.301s
user    0m0.293s
sys     0m0.003s


собирал с -О3, кстати.

> 9414780 -- если ничего не выкидывать
> 784565 -- если выкидывать только перестановки цветов
> 785267 -- если выкидывать только вращения+отражения
> 65823 -- если выкидывать и перестановки цветов, и вращения+отражения

Итак, выбрасывание вращений+отражений дает сокращение не в 12 раз, а примерно в 11.92

Получается так из-за того, что для небольшого процента "хороших" раскрасок, вращение+отражение может перевести раскраску саму в себя. Логично выделить этот небольшой процент в отдельную таблицу. Получится такое разложение:

9414780 = 12 * 784565 = 12 * ( 12 * A + B ), где A - соответствует раскраскам, никогда не переходящим под действием вращение+отражение+перестановка_цветов сама в себя. B - соответствует переходящим.

У меня получилось A=64957. Следовательно B=5081. Это позволяет еще ощутимо сократить размер хранимых в бинарнике таблиц. До 280 килобайт, если пользоваться 32-битной кодировкой.

==============================

Программа, которой я пользовался для рассчета таблицы A точно такая же, как предыдущая опубликованная мною в этой ветке тут программа. За исключением цикла while внутри main(). Который и публикую :)



	while(c.Next()) if(c.IsGood()) if(c.IsMonotoneABC()) if(c.IsMonotoneDE())
	{
		GetMappings(v, c, true, true);

		bool unique = true;
		for(unsigned i = 0, size = v.size(); i < size && unique; ++i)
		{
			if(s.find(v[i].ToString()) != s.end())
			{
				unique = false;
			}

			for(unsigned j = 0; j < size && unique; ++j)
			{
				if(i != j && v[i].IsEqual(v[j]))
				{
					unique = false;
				}
			}

		}
		if(unique)
		{
			s.insert(c.ToString());
			std::cout << c.ToString() << std::endl;
		}
	}

> До 280 килобайт

Господа, даже Билли говорил, что 640K ought to be enough for anybody. Сквозная нумерация, довольно быстрые выборки. Никаких проблем с равномерностью распределения. Мое стремление к совершенству вот-вот иссякнет :)

> если пользоваться 32-битной кодировкой

Кстати, есть более удобный (с точки зрения декодирования) способ 32-битной кодировки.

Порядок, в котором перечисляются ячейки:

  	  	02	  	03	  	05
  	18	  	01	  	04	  	06
17	  	16	  	  	  	07	  	08
  	15	  	13	  	10	  	09
  	  	14	  	12	  	11

Легко видеть, что 18 ячеек распадается на 6 "лепестков", по 3 ячейки в каждом. Первый лепесток - ячейки #1, #2, #3. Второй лепесток - ячейки #3, #4, #5. И так далее.

Внутри каждого лепестка все 3 ячейки соседствуют друг с другом. Поэтому есть только 5*4*3=60 непротиворечивых способов выбрать цвета этих ячеек. Иначе говоря, есть 60 разновидностей лепестков. Номер лепестка легко закодировать в 6 битов (туда как раз умещается число от 0 до 63). Шесть битов легко выкусить побитовыми операциями, и использовать в качестве индекса в декодировочной таблице. Последние 4 лепестка именно так и закодируем, использовав 4*6=24 бита.

Сколько есть непротиворечивых способов выбрать цвета ячеек у первых двух лепестков вместе взятых? (5*4*3)*(3*3*3)=1620. Много... Но! Когда мы сокращали размер таблиц, мы выкинули перестановки цветов. Это значит, что в таблицах хранятся только последовательности из 18 ячеек, удовлетворяющие свойствам IsMonotoneABC и IsMonotoneDE. Если этому свойству удовлетворяет вся последовательность из 18 ячеек, то удовлетворяет и ее начало из первых 6 ячеек. Это сокращает число способов выбрать первые два лепестка в 12 раз. Имеем 1620/12=135. Что легко закодировать в 8 битов (туда как раз умещается число от 0 до 255). Выкусывем их побитовыми операциями и делаем выборку из декодировочной таблицы. Так что на первые два лепестка ушло еще 8 битов.

Суммарный размер декодировочных таблиц не трудно уложить в 1 килобайт.

В итоге 24 + 8 = 32 бита. То, что надо.

s/ячейки #3, #4, #5/ячейки #4, #5, #6/

Более наглядно нумерация ячеек и разбиение на 6 "лепестков" по 3 ячейки в каждом: http://img507.imageshack.us/img507/2292/43405000.jpg

а я всё ускоряю свой перебор ^_^'
заменил рекурсию циклом.
добавил опорные точки решений для быстрого «позиционирования».
добавил бенчмарк ^_^'

теперь программа разбита на два сорца: собственно «считалка» и файл опорных решений
(генерируется автоматически отдельной программой + скриптом).

основной кот:
-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----
#include <stdio.h>                                    
#include <stdlib.h>                                   
#include <sys/time.h>                                 
#include <assert.h>                                   

static const char colors[12][5] = {
    "abcde", "acbde", "bacde", "bcade", "cabde", "cbade",
    "abced", "acbed", "baced", "bcaed", "cabed", "cbaed"};
static const char *cp;                                    

static int cells[18];
static int *cell = cells;
static const int rels[18][4] = {
    {0}, {-1}, {-1},            
    {-3}, {-4, -3, -1}, {-4, -3, -1}, {-4, -1},
    {-4}, {-5, -4, -1}, {-4, -3}, {-4, -1},    
    {-4, -3}, {-4, -1}, {-4, -1}, {-5, -4, -1},
    {-4, -3}, {-4, -3, -1}, {-4, -3, -1}};     
static const int *rel = *rels;                 

static int left[5] = { 4, 4, 4, 3, 3 };

struct timeval tv_start;
static int id;

#undef C
#define C(i) cp[cells[i]]
static inline void display(void) {
    struct timeval tv_end;        
    gettimeofday(&tv_end, NULL);  
    tv_end.tv_sec -= tv_start.tv_sec;
    tv_end.tv_usec += tv_end.tv_sec * 1000000;
    tv_end.tv_usec -= tv_start.tv_usec;       
                                              
    printf("%d: %c%c%c %c%c%c%c %c%c~%c%c %c%c%c%c %c%c%c // 0.%06d sec\n", id,
        C(0), C(1), C(2), C(3), C(4), C(5), C(6), C(7), C(8), C(9),            
        C(10), C(11), C(12), C(13), C(14), C(15), C(16), C(17),                
        (int) tv_end.tv_usec);                                                 
}

int main(int argc, char **argv) {
    extern int pts[][2];         
    int i = 0, v;                
    int c;                       
    const int *r;                
    int cnt;                     
                                 
    gettimeofday(&tv_start, NULL);
    if (argc > 1)                 
        id = abs(atoi(argv[1]));  
    else {                        
        srand(tv_start.tv_usec);  
        id = rand();              
    }                             
    id %= 9414780;                
    cp = colors[id % 12];         
    cnt = id / 12;                
                                  
    while (cnt >= *pts[i]) ++i;   
    if (i)                        
        cnt -= *pts[i-1];         
    v = pts[i][1];
    i = v & 15;
    rel += 4 * i;
    for (v >>= 4; i--; v /= 5)
        --left[*cell++ = v % 5];
    for (;;) {
        while (*cell == 5) {
            assert(cell != cells);
            *cell-- = 0;
            rel -= 4;
            ++left[cell[0]++];
        }
        c = *cell;
        if (!left[c] || (c == 1 && left[0] == 4) || (c == 2 && left[1] == 4) || (c == 4 && left[3] == 3)) {
            ++*cell;
            continue;
        }
        for (r = rel; *r && c != cell[*r]; ++r);
        if (*r)
            ++*cell;
        else if (++cell == cells+18) {
            if (!cnt--) {
                display();
                exit(0);
            }
            ++*--cell;
        } else {
            --left[c];
            rel += 4;
        }
    }
}
-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----

сорц с данными (пример):
-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----
int pts[][2]={
    {25488,2084}, {46312,4084}, {77620,6084}, {120115,2884},
    {146395,4884}, {181807,26885}, {200105,46885}, {246519,3284},
    {282499,5284}, {303170,7284}, {330717,9284}, {376186,243},
    {411682,2644}, {457297,4644}, {481338,6644}, {512861,8644},
    {550509,1843}, {589568,452}, {617711,2452}, {655972,4452},
    {681121,8452}, {705239,1251}, {742592,1651}, {784565,370}};
-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----8<-----
с этой таблицей время поиска до 10–20мс, в среднем — около миллисекунды; размер бинарника — 7к =).
с таблицей на 1.5к точек — до миллисекунды, в среднем — сотни микросекунд; бинарник — 19к.
вот =)

> в среднем — сотни микросекунд

Это сотни тысяч тактов. Полагаю, что полностью табличное решение должно быть еще раз в 100-1000 быстрее.

Вчера вечером написал (аналогичный вашему предыдущему варианту) итеративный переборный алгоритм, но работающий не в терминах отдельных ячеек, а в терминах "лепестков". Из-за того, что одним махом добавляется сразу три ячейки, раннее отбрасывание плохих решений работает несколько менее эффективно, чем у вас. Но по этой же причине многие проверки становятся быстрее - я упаковал наполненность всех 5 "тюбиков" в один uint32, и за одну проверку охватываю сразу все тюбики, соответствующие трем ячейкам. Что в результате перевесит: плюсы или минусы - пока не ясно. Часов через 5 добавлю в свое поделие перестановки цветов, и опубликую.

> Это сотни тысяч тактов. Полагаю, что полностью табличное решение должно быть еще раз в 100-1000 быстрее.

несомненно =) но есть нюансы: если приложение запускается отдельно, то время на инициализацию процесса, разбор аргументов и последующий разбор результатов вызвавшей программой будет ощутимо больше времени, требуемого для поиска решения ;) более того, если программа будет запускаться раз в несколько минут (или при дефиците памяти), время запуска будет _очень_ ощутимым. с другой стороны, если данные будут запрашиваться/необходимы постоянно, то есть смысл реализовать данную функцию либо в виде отдельной библиотеки, либо в виде сервера на tcp/udp/unix sockets (хотя последнее вряд ли будет шустрее предложенного варианта с таблицей на полторы «ка»), тогда имеет смысл сделать пред.расчёт таблицы на старте (0.3 сек старта для бешеной собаки^W^W демона — не время), и потом уже по ней выдавать результаты — да хоть и четыре метра пусть сожрёт, по сравнению с фф/жабой/ооо — капля в море.

> Вчера вечером написал (аналогичный вашему предыдущему варианту) итеративный переборный алгоритм, но работающий не в терминах отдельных ячеек, а в терминах "лепестков". Из-за того, что одним махом добавляется сразу три ячейки, раннее отбрасывание плохих решений работает несколько менее эффективно, чем у вас. Но по этой же причине многие проверки становятся быстрее - я упаковал наполненность всех 5 "тюбиков" в один uint32, и за одну проверку охватываю сразу все тюбики, соответствующие трем ячейкам. Что в результате перевесит: плюсы или минусы - пока не ясно. Часов через 5 добавлю в свое поделие перестановки цветов, и опубликую.

я уже рассматривал похожую систему, но т.к. на работе сейчас такой завал, что уже и дома моск включать нет никакого желания, то до ума ещё не довёл. на выходных попробую. но суть следующая: я разбивал всё поле на три зоны по шесть сот:
   A A A
  A A A B
 C C × B B
  C C B B
   C C B
в каждой группе я выделял три пары, где одна была независимой а две контактировали с соседними группами. каждая группа имеет 1620 вариантов, причём только первая группа может иметь любой из этих вариантов, вторая (В), если не ошибаюсь, только половину. для третьей не считал… или забыл уже. а количество возможных пар, если без оптимизации, — 25. т.е. совсем несложно для каждой пары сделать список пар, которые могут следовать за ней (по часовой стрелке). а 25 признаков элементарно кодируется в виде битовой маски, т.е. массива из 25 целых полностью определяет, какая именно пара может за ней стоять. плюс добавляем массив из 1620 записей, каждая из которых содержит пару «перед», пару «после», «независимую» пару и пять значений, определяющих количество используемых соответствующих цветов (чтобы не считать лишний раз). не помню точного числа, но если хранить не группу, а множество групп в виде: пара «перед», пара «после» и список возможных «независимых» пар (до семи), то массив сокращается до сотен элементов. т.о. перебор сводится к трём уровням вложенности вместо восемнадцати. но до конца этот алгоритм я пока не реализовал, а та недоделка делает перебор за 6 сек, что по сравнению с 0.3 сек предыдущего фулл-брутфорс-алгоритма прогрессом не является =( но, возможно, на его основе будет намного проще сделать таблицу промежуточных решений для быстрого позиционирования и последующего совсем короткого перебора.

зы: топикстартеру респект за задачу ;)

> Это сокращает число способов выбрать первые два лепестка в 12 раз.

Неверно.

1. Некоторые пары лепестков совсем не содержат цветов d и e. Количество таких лепестков сокращается в 6 раз, а не в 12 (перестановка местами d и e переводит их самих в себя). Их должно быть (3*2*1)*(1*1*1) = 6.

2. Некоторые пары лепестков совсем не содержат каких-нибудь двух цветов из тройки abc. Количество таких лепестков сокращается в 6 раз, а не в 12 (перестановка местами отсутсвующих цветов переводит их самих в себя). Их должно быть 3*(3*2*1)*(1*1*1)=18.

Если я ничего на этот раз не упустил, должно получиться (1620-6-18)/12+6/6+18/6=133+1+3=137 вариантов выбрать первую пару лепестков.

Как и обещал, выкладываю.

Собирать нужно так:
g++ -O3 -DNDEBUG ./e.cc

Перебор всех 784565 вариантов на моем Athlon x2 занимает около 0.13 секунды. Размер бинарника - 15 Кб.

Дизассемблер не смотрел: так что есть шанс, что компилятор еще и тупит где-то.

Наверное, дальше нужно прикручивать опорные точки, но это уже не очень-то интересно...

======================================

/*
    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, version 3 of the License.

    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, see <http://www.gnu.org/licenses/>.
*/

#include <cassert>
#include <cstddef>
#include <cstdio>
#include <stdint.h>

#define MASK_SHIFT 4
#define MAKE_MASK(COLOR) ( ( ( uint32_t ) 1 ) << ( ( COLOR ) * MASK_SHIFT ) )
#define MAKE_BOUNDARY(COLOR) ( MAKE_MASK(COLOR) << (MASK_SHIFT - 1) )
#define OVERFLOW_MASK ( MAKE_BOUNDARY(0) | MAKE_BOUNDARY(1) | MAKE_BOUNDARY(2) | MAKE_BOUNDARY(3) | MAKE_BOUNDARY(4) )
#define INITIAL_MASK ( MAKE_MASK(0) * 4 + MAKE_MASK(1) * 4 + MAKE_MASK(2) * 4 + MAKE_MASK(3) * 3 + MAKE_MASK(4) * 3 )
#define REQ_DELTA ( OVERFLOW_MASK - INITIAL_MASK )

struct Node
{
	uint32_t mask;
	uint32_t req;
	size_t m;
	char i, j, k;

	Node()
	{
	}

	Node(char ii, char jj, char kk) :
		mask( MAKE_MASK(ii) | MAKE_MASK(jj) | MAKE_MASK(kk) ),
		req(0),
		m(ii * 4 + kk - (ii > kk ? 0 : 1)),
		i(ii), j(jj), k(kk)
	{
		if(i == 1 || i == 2 || i == 4)
		{
			req |= MAKE_BOUNDARY(i - 1);
		}
		if(j == 1 || j == 2 || j == 4) if(i + 1 != j)
		{
			req |= MAKE_BOUNDARY(j - 1);
		}
		if(k == 1 || k == 2 || k == 4) if(i + 1 != k && j + 1 != k)
		{
			req |= MAKE_BOUNDARY(k - 1);
		}
	}
};

class NodeConstIterator
{
	const Node *begin;
	const Node *end;
public:
	NodeConstIterator() : begin(0), end(0)
	{
	}
	NodeConstIterator(const Node *b, const Node *e) : begin(b), end(e)
	{
	}
	bool Next()
	{
		assert(begin < end);
		return ++begin != end;
	}
	const Node *Get() const
	{
		assert(begin < end);
		return begin;
	}
};

class RootTable
{
	Node nodes[7];
public:
	RootTable()
	{
		size_t n = 0;
		for(char i = 0; i < 5; ++i)
		for(char j = 0; j < 5; ++j) if(j != i)
		for(char k = 0; k < 5; ++k) if(k != i  && k != j)
		{
			Node node(i, j, k);
			if(!node.req)
			{
				assert(n < 7);
				nodes[n] = node;
				n += 1;
			}
		}
	}
	NodeConstIterator GetIterator() const
	{
		return NodeConstIterator(nodes - 1, nodes + 7);
	}
};

class StepTable
{
	Node nodes[20][27];
public:
	StepTable()
	{
		size_t m = 0;
		for(char fi = 0; fi < 5; ++fi)
		for(char la = 0; la < 5; ++la) if(la != fi)
		{
			size_t n = 0;
			for(char i = 0; i < 5; ++i) if(i != fi && i != la)
			for(char j = 0; j < 5; ++j) if(j != la && j != i)
			for(char k = 0; k < 5; ++k) if(k != i  && k != j)
			{
				assert(m < 20);
				assert(n < 27);
				nodes[m][n] = Node(i, j, k);
				n += 1;
			}
			m += 1;
		}
	}
	NodeConstIterator GetIterator(size_t m) const
	{
		assert(m < 20);
		return NodeConstIterator(nodes[m] - 1, nodes[m] + 27);
	}
};

class Generator
{
	const RootTable root_table;
	const StepTable step_table;

	uint32_t mask;
	NodeConstIterator iterators[6];

	bool TailFitsHead() const
	{
		const Node *head = iterators[0].Get();
		const Node *tail = iterators[5].Get();
		return head->i != tail->i && head->i != tail->k && head->j != tail->k;
	}

	bool Seek(size_t depth)
	{
		while(true)
		{
			if(iterators[depth].Next())
			{
				const Node *node = iterators[depth].Get();
				uint32_t new_mask = mask - node->mask;
				if( ( new_mask & OVERFLOW_MASK ) == 0 )
				if( ( ( mask + REQ_DELTA ) & node->req ) == 0 )
				{
					if(depth == 5)
					{
						assert(new_mask == 0);
						if(TailFitsHead())
						{
							return true;
						}
					}
					else
					{
						mask = new_mask;
						depth += 1;
						iterators[depth] = step_table.GetIterator(node->m);
					}
				}
			}
			else
			{
				if(depth == 0)
				{
					return false;
				}

				depth -= 1;
				mask += iterators[depth].Get()->mask;
			}
		}
	}

public:

	Generator()
	{
		Reset();
	}

	void Reset()
	{
		mask = INITIAL_MASK;
		iterators[0] = root_table.GetIterator();
		Seek(0);
	}

	bool Next()
	{
		bool ok = Seek(5);
		if(!ok) Reset();
		return ok;
	}

	void Get(char dst[18]) const
	{
		for(size_t depth = 0; depth < 6; ++depth)
		{
			const Node *node = iterators[depth].Get();
			dst[depth * 3 + 0] = node->i;
			dst[depth * 3 + 1] = node->j;
			dst[depth * 3 + 2] = node->k;
		}
	}

};

void print12(const char c[18])
{
	const size_t r[18] = {4,0,1,5,2,6,9,10,14,13,17,16,12,15,11,8,7,3};
	const char p[12][5] =
				{
					{'a', 'b', 'c', 'd', 'e'}, {'a', 'b', 'c', 'e', 'd'},
					{'c', 'a', 'b', 'd', 'e'}, {'c', 'a', 'b', 'e', 'd'},
					{'b', 'c', 'a', 'd', 'e'}, {'b', 'c', 'a', 'e', 'd'},
					{'a', 'c', 'b', 'd', 'e'}, {'a', 'c', 'b', 'e', 'd'},
					{'b', 'a', 'c', 'd', 'e'}, {'b', 'a', 'c', 'e', 'd'},
					{'c', 'b', 'a', 'd', 'e'}, {'c', 'b', 'a', 'e', 'd'}
				};

	char t[20];
	t[18] = '\n';
	t[19] = 0;

	for(size_t i = 0; i < 12; ++i)
	{
		for(size_t j = 0; j < 18; ++j)
		{
			t[r[j]] = p[i][c[j]];
		}
		printf(t);
	}
}

int main()
{
	Generator generator;

	do
	{
//		char c[18];
//		generator.Get(c);
//		print12(c);
	}
	while(generator.Next());

	return 0;
}

А вот совершенно аналогичная перебиралка, но работающая в терминах одногой ячейки, а не лепестка из трех ячеек.

Перебор всех 784565 вариантов на моем Athlon x2 занимает около 0.23 секунды. То есть примерво в 2 раза медленне предыдущего варианта.

За то бинарник уменьшился до 5 килобайт. Видимо, за счет того, что не нужно больше порождать таблицы. Учитывая, что над размером кода я совершенно не парился ни в том ни в другом случае, это ничего особо не значит...

Мораль: перебор лепестками - эффективнее.

======================================

/*
    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, version 3 of the License.

    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, see <http://www.gnu.org/licenses/>.
*/

#include <cassert>
#include <cstddef>
#include <cstdio>
#include <stdint.h>

#define MASK_SHIFT 4
#define MAKE_MASK(COLOR) ( ( ( uint32_t ) 1 ) << ( ( COLOR ) * MASK_SHIFT ) )
#define MAKE_BOUNDARY(COLOR) ( MAKE_MASK(COLOR) << (MASK_SHIFT - 1) )
#define OVERFLOW_MASK ( MAKE_BOUNDARY(0) | MAKE_BOUNDARY(1) | MAKE_BOUNDARY(2) | MAKE_BOUNDARY(3) | MAKE_BOUNDARY(4) )
#define INITIAL_MASK ( MAKE_MASK(0) * 4 + MAKE_MASK(1) * 4 + MAKE_MASK(2) * 4 + MAKE_MASK(3) * 3 + MAKE_MASK(4) * 3 )
#define REQ_DELTA ( OVERFLOW_MASK - INITIAL_MASK )
#define REQ_MASK ( MAKE_BOUNDARY(0) | MAKE_BOUNDARY(1) | MAKE_BOUNDARY(3) )

#define MAKE_DIV(DEPTH) ( ( ( uint32_t ) 1 ) << ( DEPTH ) )
#define DIV3_MASK ( MAKE_DIV(0) | MAKE_DIV(3) | MAKE_DIV(6) | MAKE_DIV(9) | MAKE_DIV(12) | MAKE_DIV(15) | MAKE_DIV(18) )

class Generator
{
	uint32_t mask;
	char c[3+18];

	bool Seek(size_t depth)
	{
		while(true)
		{
			assert(c[depth] < 5);
			if(++c[depth] != 5)
			{
				uint32_t node_mask = MAKE_MASK(c[depth]);
				uint32_t new_mask = mask - node_mask;
				if( ( new_mask & OVERFLOW_MASK ) == 0 )
				if( ( REQ_MASK & ( mask + REQ_DELTA ) & ( node_mask >> 1 ) ) == 0 )
				if( c[depth] != c[depth-1] )
				if( c[depth] != c[depth-2-(bool)( MAKE_DIV(depth) & DIV3_MASK )] )
				{
					if(depth == 3+17)
					{
						assert(new_mask == 0);
						// TailFitsHead : part2
						if(c[3 + 0 + 0] != c[3 + 15 + 2] && c[3 + 0 + 1] != c[3 + 15 + 2])
						{
							return true;
						}
					}
					else
					{
						// TailFitsHead : part1 - check it as early as possible
						if(depth != 3+15 || c[3 + 0 + 0] != c[3 + 15 + 0])
						{
							mask = new_mask;
							depth += 1;
							c[depth] = -1;
						}
					}
				}
			}
			else
			{
				if(depth == 3)
				{
					return false;
				}

				depth -= 1;
				mask += MAKE_MASK(c[depth]);
			}
		}
	}

public:

	Generator()
	{
		c[0 + 0] = -1;
		c[0 + 1] = -1;
		c[0 + 2] = -1;
		Reset();
	}

	void Reset()
	{
		mask = INITIAL_MASK;
		c[3 + 0] = -1;
		Seek(3);
	}

	bool Next()
	{
		bool ok = Seek(3+17);
		if(!ok) Reset();
		return ok;
	}

	void Get(char dst[18]) const
	{
		for(size_t depth = 0; depth < 18; ++depth)
		{
			dst[depth] = c[3+depth];
		}
	}

};

void print12(const char c[18])
{
	const size_t r[18] = {4,0,1,5,2,6,9,10,14,13,17,16,12,15,11,8,7,3};
	const char p[12][5] =
				{
					{'a', 'b', 'c', 'd', 'e'}, {'a', 'b', 'c', 'e', 'd'},
					{'c', 'a', 'b', 'd', 'e'}, {'c', 'a', 'b', 'e', 'd'},
					{'b', 'c', 'a', 'd', 'e'}, {'b', 'c', 'a', 'e', 'd'},
					{'a', 'c', 'b', 'd', 'e'}, {'a', 'c', 'b', 'e', 'd'},
					{'b', 'a', 'c', 'd', 'e'}, {'b', 'a', 'c', 'e', 'd'},
					{'c', 'b', 'a', 'd', 'e'}, {'c', 'b', 'a', 'e', 'd'}
				};

	char t[20];
	t[18] = '\n';
	t[19] = 0;

	for(size_t i = 0; i < 12; ++i)
	{
		for(size_t j = 0; j < 18; ++j)
		{
			t[r[j]] = p[i][c[j]];
		}
		printf(t);
	}
}

int main()
{
	Generator generator;
	do
	{
//		char c[18];
//		generator.Get(c);
//		print12(c);
	}
	while(generator.Next());

	return 0;
}

> file_name.append("x", i + 1);

Тут ошибка. Должно быть file_name.append(i + 1, 'x');

> Как посчитаю число связных компонент - отпишусь.

Это оказалось неожиданно проблематично.

Сначала решил, что воспользуюсь boost::graph. Нужно как-то граф из текстового файла - перечня ребер - загнанть в бустовый граф. Долго разбирался с boost::read_graphviz. Потренировался на маленьких файлах - работает. Ок. Слепил для пробы graphviz файл из одних только 9414780 вершин. Зову boost::read_graphviz. Отъело 2.7 гигабайта оперативки, и успешно загрузилось. Ок. Сделал graphviz файл собственнно с 90209124 ребрами. Пытаюсь загрузить его - съело более 13 Гб оперативки, ушло глубоко в своп, и в конце концов было прибито.

Ладно, допустим boost::graph кривой. Лезу в гугль со словами graph library. Получаю GOBLIN Graph library, "Goblin is a full-featured tool chain for handling graphs". Гут. Скачиваю, собираю. Оказывается, graphviz файлы оно читать не умеет. Ладо, изучаю DIMACS Graph Format. Делаю файл. Пытаюсь загрузить, а в ответ мне: "Number of nodes is out of range". Грррррр :-E

В общем, написать свой маленький велосипед оказалось гораздо быстрее и проще, чем ковыряться в чужих библиотеках..

Результат: граф имеет одну компоненту связности.

Это значит, что абсолютно любые две "хорошие" раскраски можно соеденить цепочкой из "хороших" раскрасок, причем соседние раскраски в этой цепочке будут отличаться только перестановкой двух ячеек.

Пример цепочки, соединяющей раскраски ababcebcacdecabded и dedbcbacacdecababe: 

aba bceb ca~cd ecab ded
aba bcdb ca~ce ecab ded
aea bcdb ca~ce ecab dbd
aeb bcda ca~ce ecab dbd
aed bcba ca~ce ecab dbd
aed bcba ca~cd ecab dbe
ded bcba ca~cd ecab abe

========================================

Программа использует _очень_ глубокую рекурсию, поэтому перед запуском нужно выполнить команду
$ ulimit -s unlimited
(это в bash-е, как в других шеллах - не знаю; суть в том, чтобы размер стека был неограниченным), иначе будет ошибка сегментирования.

Пример запуска (использующий те файлы, которые порождает моя "брутфорсовая" программа http://www.linux.org.ru/jump-message.jsp?msgid=3884902&cid=3893037 с исправлением http://www.linux.org.ru/jump-message.jsp?msgid=3884902&cid=3905553 ):
$ time ./a.out graphs/graph.x graphs/graph.xx
Read file graphs/graph.x done, num_branches = 45156991
Read file graphs/graph.xx done, num_branches = 45052133
Read data done, total_branches = 90209124
Component size = 9414780
Analysis done, num_components = 1

real    1m7.402s
user    1m4.540s
sys     0m2.740s

========================================

#include <iostream>
#include <fstream>
#include <vector>

struct Vertex
{
	bool visited;
	std::vector<uint32_t> branches;
	Vertex()
	{
		visited = false;
		branches.reserve(26);
	}
};

std::vector<Vertex> graph;

uint32_t f(uint32_t vertex)
{
	uint32_t ret = 0;
	if(!graph[vertex].visited)
	{
		graph[vertex].visited = true;
		ret += 1;
		for(size_t i = 0; i < graph[vertex].branches.size(); ++i)
		{
			ret += f(graph[vertex].branches[i]);
		}
	}
	return ret;
}

int main(int argc, char **argv)
{
	graph.reserve(10000000);

	size_t total_branches = 0;
	for(size_t k = 1; k < argc; ++k)
	{
		std::ifstream stream(argv[k]);

		size_t num_branches = 0;
		while(true)
		{
			uint32_t i, j;
			stream >> i;
			stream >> j;
			if(!stream) break;
			if(graph.size() <= i) graph.resize(i + 1);
			if(graph.size() <= j) graph.resize(j + 1);
			graph[i].branches.push_back(j);
			graph[j].branches.push_back(i);
			num_branches += 1;
		}
		total_branches += num_branches;
		std::cout << "Read file " << argv[k] << " done, num_branches = " << num_branches << std::endl;
	}
	std::cout << "Read data done, total_branches = " << total_branches << std::endl;

	int32_t num_components = 0;
	for(size_t i = 0; i < graph.size(); ++i)
	{
		if(!graph[i].visited)
		{
			num_components += 1;
			std::cout << "Component size = " << f(i) << std::endl;
		}
	}
	std::cout << "Analysis done, num_components = " << num_components << std::endl;
	return 0;
}

> 9414780 = 12 * 784565 = 12 * ( 12 * A + B ), где A - соответствует раскраскам, никогда не переходящим под действием вращение+отражение+перестановка_цветов сама в себя. B - соответствует переходящим. У меня получилось A=64957. Следовательно B=5081.

Хочется как можно больше узнать о свойствах таблицы A.

Возьмем произвольную "хорошую" раскраску. Рассмотрим множество из 144 раскрасок, получающееся из данной раскраски путем всевозможных вращений, отражений и перестановок цветов. Утверждение: либо все раскраски в этом множестве уникальны, либо каждая раскраска в этом множестве имеет хотя бы одну с ней совпадающую.

Вероятно, это утверждение можно доказать исходя из алгебраических соображений. Для чего придется напрягать голову, и будет риск ошибки в доказательстве. Я проверил его экспериментально.

===========================

Программа совпадает с http://www.linux.org.ru/jump-message.jsp?msgid=3884902&cid=3894730 за исключением функции main(), которую и привожу.

Результат запуска таков: Passed 64957 0 5081

int main()
{
	Coloring c;
	c.Reset();

	std::vector<Coloring> v;
	std::tr1::unordered_set<std::string> s;

	unsigned count0 = 0, count144 = 0;

	while(c.Next()) if(c.IsGood()) if(c.IsMonotoneABC()) if(c.IsMonotoneDE())
	{
		GetMappings(v, c, true, true);

		unsigned num_paired = 0; // number of elements in v[] that have at least one equal element in v[]

		for(unsigned i = 0, size = v.size(); i < size; ++i)
		for(unsigned j = 0; j < size; ++j) if(i != j)
		if(v[i].IsEqual(v[j]))
		{
			num_paired += 1;
			break;
		}

		if(num_paired == 0)
		{
			++count0;
		}
		else if(num_paired == 144)
		{
			++count144;
		}
		else
		{
			std::cout << "Failed" << std::endl;
			return 1;
		}
	}

	std::cout << "Passed " << count0 / 12 << " " << count0 % 12 << " " << count144 << std::endl;
	return 0;
}

Кажется, есть идея.

Договоримся о порядке перечисления ячеек внутри лепестка:
1. Ячейка, прижатая к центральной
2. Ячейка, прижатая к той грани ячейки #1, которая как можно дальше от центральной ячейки.
3. Ячейка, прижатая к ячейкам #1 и #2, по часовой стрелке от них.

Предлагается разбить 60 возможных лепестков на 7 классов:
Класс 0P: Лепестки abc, acb, bac, bca, cab, cba.
Класс 1P: Лепестки abd, bad, bcd, cbd, cad, acd, abe, bae, bce, cbe, cae, ace.
Класс 1Q: Лепестки adb, bda, bdc, cdb, cda, adc, aeb, bea, bec, ceb, cea, aec.
Класс 1R: Лепестки dab, dba, dbc, dcb, dca, dac, eab, eba, ebc, ecb, eca, eac.
Класс 2P: Лепестки ade, bde, cde, aed, bed, ced.
Класс 2Q: Лепестки dae, dbe, dce, ead, ebd, ecd.
Класс 2R: Лепестки dea, deb, dec, eda, edb, edc.

Цифра в названии класа кодирует суммарное количество ячеек цвета 'd' и ячеек цвета 'e'. Буква в названии класса кодирует расположение этих ячеек.

Если лепесток принадлежит некоторому классу, то он будет принадлежать этому же классу и после абсолютно любой перестановки цветов.

Из классификации лепестков вытекает классификация "хороших" раскрасок. Класс раскраски записывается, например, так: 0P-0P-0P-2P-2P-2P.

Свойства классификации "хороших" раскрасок:
1. Класс раскраски не меняется ни при каких перестановках цветов.
2. По классу раскраски легко и однозначно определяется, какой у нее будет класс после поворота.
3. По классу раскраски (не так легко, но все равно) однозначно определяется, какой у нее будет класс после зеркального отражения.
4. Имеется (не вполне тривиальная) связь между лексикографическим порядком на раскрасках, и лексикографическим порядком на классах раскрасок.
5. У любого класса раскрасок сумма цифр его названия равна 6 (суммарное количество ячеек цвета 'd' и 'e').
6а. За ячейкой класса 1P или класса 2P не может следовать ячейка класса 2R.
6б. За ячейкой класса 2Q не может следовать ячейка класса 2Q или класса 2R или класса 1R.
7а. Если класс раскраски не переводится сам в себя никаким сочетанием поворот+отражение, то любая принадлежащая ему раскраска тоже не переводится сама в себя никаким сочетанием поворот+отражение+перестановка_цветов.
7б. Если класс раскраски переводится сам в себя, то про принадлежащие ему раскраски ничего определенного на этот счет сказать нельзя.

В чем же профит? Замена раскрасок их классами ощутимо снижает комбинаторную сложность задачи, и позволяет сосредоточится на исследовании перестановок+отражений. К сожалению, задача о классах раскрасок в математическом смысле "более слабая", чем задача о самих раскрасках. Однако разобравшись с классами, мы, может быть, сможем многократно уменьшить трудоемкость заполнения таблиц A и B рантайм (если мы решительно не хотим таскать лишние 260 килобайт в теле исполнимого файла).

Можно рассмотреть еще "более слабую" в математическом смысле задачу: разбить 60 возможных лепестков на только 3 класса, по суммарному количеству ячеек цвета 'd' и цвета 'e' (но не учитывать расположение этих ячеек внутри лепестка).

Классификация лепестков, чуть нагляднее: http://img111.imageshack.us/img111/4746/legendg.png

По картинке легко понять, что "правильный" порядок на классах лепестков такой: 0P<1P<1Q<2P<1R<2Q<2R. Именно такой порядок нужно использовать для построения "лексикографического" порядка на классах раскрасок, чтобы он хорошо соотносился с лексикографическим порядком на раскрасках.