Пишу свой гогнокод по реализации корявых OSP (алгоритм - свой, комбинировал из того, что знал), у меня работает достаточно медленно. Из нагугленного реализация подобного есть только у Sage math: http://www.sagemath.org/doc/reference/combinat/sage/combinat/set_partition_or.... Попробуйте запустить с числами порядка 8-12 (ворнинг: ростет очень быстро: http://oeis.org/A000670).
Еще было бы хорошо услышать мнение по поводу придуманного алгоритма - сначала строю разбиения массива методом restricted growth length, потом заполняю соответственно полученным строкам множество своими числами, потом строю все перестановки по полученным подмножествам на каждое множество. Получается так же, как и в примере, но не так упорядочено (пока пофиг). Суть в том, каким образом можно ускорить алгоритм, чтобы добиться приемлемой скорости, если это вообще реально. (В исходниках Sage берутся все разбиения мощности множества на части от 1 до |S|, и для каждого такого разбиения потом просто перестанавливаются элементы).
Перемещено tazhate из talks
