r2 - 14 Sep 2006 - 22:03:41 - Sergej ZnamenskijYou are here: TWiki >  Refaldevel Web > TppBackend > TRefalPermutations
Пусть дано множество {a_i} из N элементов (1 <= i <= N). Тогда все их перестановки <Perm {a_i}> можно записать в следующем виде:
(a_1 <Perm {a_i}\a_1>) (a_2 <Perm {a_i}\a_2>) ... (a_N <Perm {a_i}\a_N),
где знак '\' означает вычитание элемента из множества. И длина и глубина этого выражения равны N. Имея его, понятно, как распечатать все перестановки в традиционном виде.

Рефал-функцию, генерирующую такое выражение, назовём Gen-Perms.

$tfunc Gen-Perms expr = e.perms;

Gen-Perms expr =
    (/*e0*/) (expr) (/*e.perms*/) $iter {
        expr : t1 e2 =
            (e0 t1) (e2) (e.perms (t1 (<Gen-Perms e0 e2>)));  // (1)
    } :: (e0) (expr) (e.perms),
    expr : /*empty*/ =
    e.perms;

На самом деле, эта функция генерирует немного другое выражение -- в строке (1) вызов Gen-Perms заключён в скобки. Это сделано специально, чтобы избежать конкатенации неготового выражения, являющегося результатом вызова, с термом t1.

? А можно ли конкатенировать неготовые выражения, не вычисляя их? То есть почему бы не сделать операцию конкатенации т-функцией?

Например, результат работы <Gen-Perms '123'> будет состоять из трёх термов:

('1' (('2' (('3' ()))) ('3' (('2' ())))))
('2' (('1' (('3' ()))) ('3' (('1' ())))))
('3' (('1' (('2' ()))) ('2' (('1' ())))))

А результат <Gen-Perms '1234'> — из четырёх, и первый терм будет выглядеть так:

('1' (('2' (('3' (('4' ())))
            ('4' (('3' ())))))
      ('3' (('2' (('4' ())))
            ('4' (('2' ())))))
      ('4' (('2' (('3' ())))
            ('3' (('2' ())))))))

Предположим теперь, что мы хотим вывести на экран только те перестановки из 10 элементов, которые начинаются с последовательности '654321':

Main = {
    <Gen-Perms '1234567890'> :
        e ('6' (e ('5' (e ('4' (e ('3' (e ('2' (e ('1' (e.p)) e)) e)) e)) e)) e)) e,
        e.p : e t.q e,
        <Print-Perms ('654321') t.q>,
        $fail;;
};

За счёт того, что функция Gen-Perms объявлена как $tfunc, вычисление её результата должно происходить лениво. Это означает, что ресурсы (время и память), требуемые для работы функции Main должны быть сопоставимы с ресурсами, требуемыми для вычисления Gen-Perms от четырёх элементов (в том смысле, что функция Gen-Perms будет, помимо вычисления <Gen-Perms '7890'>, вызвана всего 6 раз).

Используемая в Main функция Print-Perms определяется следующим образом:

$func Print-Perms (e.start) t.perm = ;

Print-Perms {
    (e.start) (t1 (v.perms)) =
        {
            v.perms : e t.p e,
                <Print-Perms (e.start t1) t.p>,
                $fail;;
        };
    (e.start) (t1 ()) = <PrintLN e.start t1>;
};

-- Anton Orlov - 10 Dec 2004

Edit | WYSIWYG | Attach | Printable | Raw View | Backlinks: Web, All Webs | History: r2 < r1 | More topic actions
 
R+

This site is powered by the TWiki collaboration platformCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback