Взято из статьи в журнале MonadReader выпуск#1

Суперпоследовательность s последовательности p — такая последовательность, множество подпоследовательностей которой содержит, среди прочего, все перестановки последовательности p.
Пример:

p = 1 2 3
s = 1 2 3 1 2 3 1
    # # #
    #   #   #
      #   #   #
      #       # #
        # # #
        #   #   #

Чтобы далее не заморачиваться с наборами неуникальных элементов, будем полагать, что p(n) = [1..n], т.е. алфавит из n букв.

Напишите:
1) Предикат, проверяющий, является ли данная строка s суперпоследовательностью для алфавита p(n). Наивная реализация занимает O(n! * length(s)), это неприемлемо долго.
2) Генератор кратчайшей суперпоследовательности для p(n)
3) Формулы для оценки нижней и верхней границ её длины. Понятно, что грубые оценки — это n и n^2-n+1. Можно ли их сузить?
4) Формулы для оценки количества кратчайших суперпоследовательностей.

Для любителей самообразования:
— напишите это на Хаскелле и на J
— — наиболее читаемо
— — наиболее компактно
— — наиболее быстродействующе