[Закрыть]
 
popoff.donetsk.ua
Выглаженный и выстиранный аккордеон похож на батарейку.
Начало | Новости | Статьи | Форум | Опросы | Карта сайта | Обо мне
popoff.donetsk.ua - Статьи - ДонНТУ - Функциональное и логическое программирование - Генерация перестановок в антилексикографическом порядке (на Си и на Прологе)
Я это делаю
Персональное меню
Голосование
Деньги, либо любимое занятие? Постоянный адрес этого вопроса
Деньги, но неинтересная работа и невозможность уделить время семье
Интересная работа, возможность саморазвиваться, но нищенский заработок
Ваш возраст (не обязательно)
Почему? (не обязательно)

Голосование закрыто.

Поиск по сайту
Реклама
Гинеколог, стоматолог, психотерапевт в Донецке
Статистика

Генерация перестановок в антилексикографическом порядке (на Си и на Прологе)

Постоянный адрес статьи

Что такое генератор перестановок и что такое антилексикографический порядок?

Генератор перестановок - это программа, которая генерирует все возможные перестановки элементов некоторого множества. Например, для множества из трёх элементов {1,2,3} это будут (если отсортировать «по алфавиту»):

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Общее количество перестановок для множества мощностью n считается по формуле: n!.

Алгоритм для генерации перестановок в антилексикографическом порядке может базироваться на двух утверждениях:

  1. Если множество перестановок P упорядочено антилексикографически, то начальная и конечная перестановки - это соответственно (1, 2, …, n) и (n, n-1,…,1).

  2. Упорядоченная антилексикографически последовательность перестановок по значению последнего элемента в них может быть разбита на n блоков длины (n-1)!. При этом q-й блок на последнем месте имеет элемент, равный (n-q+1), а первые n-1 позиций этого блока определяют последовательность перестановок множества {1,2,…,n}\{q} в антилексикографическом порядке.

Пример перестановок в антилексикографическом порядке для множеств {1,2,3} и {1,2,3,4}:

3! 4!
  1 2 3
2 1 3
1 3 2
3 1 2
2 3 1
3 2 1
 
  1 2 3 4
2 1 3 4
1 3 2 4
3 1 2 4
2 3 1 4
3 2 1 4
  1 2 4 3
2 1 4 3
1 4 2 3
4 1 2 3
2 4 1 3
4 2 1 3
  1 3 4 2
3 1 4 2
1 4 3 2
4 1 3 2
3 4 1 2
4 3 1 2
  2 3 4 1
3 2 4 1
2 4 3 1
4 2 3 1
3 4 2 1
4 3 2 1
 

Подробнее о лексикографическом и антилексикографическом порядке перестановок Вы можете почитать, перейдя по ссылке в разделе «Смотрите также».

Генератор перестановок на Си

Алгоритм генерации перестановок в антилексикографическом порядке можно найти практически в любой книжке по дискретной математике. Вот его реализация на языке Си:

#include <stdio.h>
#include <conio.h>

#define N 4

void swap(int *a, int *b)
{
  int t;

  t=*a;
  *a=*b;
  *b=t;
}

void reverse(int * P,int m)
{
   int i=0, j=m;
   while(i<j)
   {
     swap(&P[i], &P[j]);
     ++i;
     --j;
   }
}

void antilex(int * P,int m)
{
  int i;

  if(m==0)
  {
    for(i=0; i<N; ++i)
      printf("%d ",P[i]);
    printf("\n");
  }
  else
  {
    for(i=0; i<=m; ++i)
    {
      antilex(P,m-1);
      if(i<m)
      {
        swap(&P[i], &P[m]);
        reverse(P,m-1);
      }
    }
  }
}

void main()
{
  int i;
  int P[N];

  for(i=0; i<N; ++i)
    P[i] = i+1;

  antilex(P,N-1);
  getch();
}

Основу программы составляет рекурсивная функция antilex.

Генератор перестановок на Прологе

Для полноты изложения приведу здесь генератор перестановок на Прологе, который можно найти практически в любой книге по Прологу. Этот генератор состоит из двух предикатов: предикат position(L1,X,L2) для вставки элемента X в все позиции списка L1 и предикат transposition, который собственно генерирует все перестановки.

domains
  i=integer
  l=i*
predicates
  position(l,i,l)
  transposition(l,l)
clauses
  position(L,X,[X|L]).
  position([H|T1],X,[H|T2]):-position(T1,X,T2).

  transposition([],[]).
  transposition([H|T],L):-
    transposition(T,T1),
    position(T1,H,L).

Посмотрим на результат генерации:

?-transposition([1,2,3],X)
X=[1,2,3]
X=[2,1,3]
X=[2,3,1]
X=[1,3,2]
X=[3,1,2]
X=[3,2,1]
6 Solutions

Как видим, порядок не антилексикографический. Я бы назвал этот порядок случайным.

Более подробно о том, как получился этот генератор перестановок, Вы можете почитать в любой книге по Прологу2.

Перевод программы с Си на Пролог

Если взять приведённый Выше код на языке Си и просто перевести его на Пролог, то получится примерно следующее:

domains
  i=integer
  l=i*
predicates
  pop(l,integer,i)
  replace(l,integer,i,l)
  swap(l,integer,integer,l)
  reverse(l,integer,integer,l)
  antilex(l,integer,l)
  antilex_body(l,integer,integer,l)
clauses
  /*
     Нумерация всех списков - с 0, по аналогии с программой на Си
  */
  /* pop(L,N,X)
     выбрать из списка L элемент с номером N и вернуть его в Х
  */
  pop([H|_],0,H).
  pop([_|T],N,E):-
    N>0,
    N1=N-1,
    pop(T,N1,E).

  /* replace(LSrc,N,X,LRes)
     поменять в списке LSrc элемент с номером N на значение Х.
     Результат вернуть в LRes
  */
  replace([_|L],0,E,[E|L]).
  replace([H|T],N,E,[H|R]):-
    N>0,
    N1=N-1,
    replace(T,N1,E,R).

  /* swap(LSrc,N1,N2,LRes)
     поменять в списке LSrc местами элементы с номерами N1 и N2.
     Результат вернуть в LRes
  */
  swap(L1,N1,N2,L2):-
    pop(L1,N1,E1),
    pop(L1,N2,E2),
    replace(L1,N1,E2,L),
    replace(L,N2,E1,L2).

  /* reverse(LSrc,X,Y,LRes)
     переставить в списке LSrc первые Y элементов в обратном порядке.
     Результат вернуть в LRes
     X - это номер первого элемента, с которого нужно производить перестановку
       соответствует переменной цикла в программе на Си
     вызывать так:
       reverse([1,2,3],0,2,X)
     результат:
       Х=[3,2,1]
  */
  reverse(L,X,Y,L):-X>=Y.
  reverse(L1,X,Y,L2):-
    X<Y,
    swap(L1,X,Y,L),
    X1=X+1,
    Y1=Y-1,
    reverse(L,X1,Y1,L2).

  /* antilex(LSrc,M,LRes)
     переставить в списке LSrc первые M элементов в обратном порядке.
     Результат вернуть в LRes
     M - соответсвует аргументу M в программе на Си
     возвращать переставленный список требуется потому, что в программе на Си
       используется внешняя по отношению к функции antilex() память, выделенная
       под массив Р[] и поэтому при возврате из рекурсивных вызовов функции
       antilex(), все изменения, произведённые над массивом Р видны в
       вызывающей рекурсивной итерации
     вызывать так:
       antilex([1,2,3],2,_)
     результат выводится сразу на экран
  */
  antilex(L,0,L):-write(L),nl.
  antilex(L,M,L1):-
    M>0,
    antilex_body(L,0,M,L1).

  /*
    antilex_body(LSrc,I,M,LRes)
    реализация цикла for() в программе на Си
    I - переменная цикла
    M - значение аргумента m функции antilex()

    Из-за особенностей Пролога, пришлось сделать не совсем точный перевод.
    В программе на Си выполняется рекурсивный вызов antilex(), протом
    производится проверка условия и по ветке "то" этого условия - выполняются
    дополнительные действия.
    В при переводе на Пролог рекурсивный вызов пришлось повторить в двух
    местах: отдельно - по ветке "то" и отдельно - по ветке "иначе".
  */
  antilex_body(L,I,M,LRes):-
    I<M,
    M1=M-1,
    I1=I+1,
    antilex(L,M1,L1),
    swap(L1,I,M,L2),
    reverse(L2,0,M1,L3),
    antilex_body(L3,I1,M,LRes).
  antilex_body(L,I,M,LRes):-
    I=M,
    M1=M-1,
    I1=I+1,
    antilex(L,M1,L1),
    antilex_body(L1,I1,M,LRes).
  antilex_body(L,I,M,L):-
    I>M.

Вот результат выполнения этой Пролог-программы:

Goal: antilex([1,2,3],2,_)
[1,2,3]
[2,1,3]
[1,3,2]
[3,1,2]
[2,3,1]
[3,2,1]
Yes

Как видим, результат правильный. Отмечу здесь лишь некоторые недостатки этой программы:

  • Огромное количество рекурсивных вызовов в программе на Прологе. В программе на Си глубина вложенности рекурсии не превышает размера списка. В программе на Прологе глубина вложенности рекурсии достигает количества всех перестановок всех элементов списка.

    Это влияет не на время работы программы, как многие могли успеть подумать, а на объём используемой памяти. Чтобы сгенерировать все перестановки для списка из 4-х элементов, мне пришлось увеличивать размер стека до 16 КБ. Необходимый объём стека для генерации всех перестановок списка из 5 элементов будет 80 КБ. Для 6 элементов - 480 КБ. Для 7 - более 3 мегабайт. Для 10 элементов - более 2 гигабайт.

    Для сравнения, программа на Си при генерации всех перестановок для списка из 10 элементов не потребует больше 100 байтов памяти для стека.

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

  • Лишние аргументы у предиката antilex(). Можно, конечно, написать предикат, который посчитает длину списка и подставит нужные аргументы, но этот предикат чем-то будет похож на костыли, которые выдают человеку с больными ногами в случае, если ноги вылечить уже невозможно.

  • Использование встроенной функции write() приводит к тому, что сгенерированные перестановки нельзя будет использовать другими предикатами. Программа на Си тоже обладает таким недостатком, но отличие Си от Пролога как раз и состоит в том, что функция в Си может вернуть только одно значение, а предикат на Прологе - сколько угодно значений.

  • По правде говоря, мне на отладку этой программы понадобилось примерно втрое больше времени, чем на вариант, который мы рассмотрим ниже.

  • Если в программе нельзя разобраться, не вводя в неё комментарии - то это плохая программа. Разобраться в хорошей программе можно без дополнительных комментариев.

    Лично я не уверен, что кто-нибудь смог бы легко догадаться, для чего предикаты antilex и antilex_body возвращают изменённый список, если бы я не написал об этом в комментарии. Тем более, учитывая, что в этом аргументе возвращается только одно значение - последнее, а от предиката требуется возвращать все значение. И ещё тем более, что значения возвращать по смыслу тут не требуется, так как все перестановки печатаются на экране функцией write().

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

Есть и другие недостатки. Но уже даже этих недостатков, думаю, достаточно для того, чтобы Вы задали мне вопрос: «а для чего же здесь приведён этот код, раз он такой плохой?» Отвечу на Ваш вопрос так: «Для того, чтобы узнать, откуда берутся плохие программы.»

В данном случае я потратил силы и написал эту программу для того, чтобы продемонстировать, какая она может получиться. Хотя я и потратил на неё много времени, я смог заставить эту программу работать, потому что у меня много опыта и я знаю если не все, то очень многие тонкости работы Пролога. Начинающие программисты двигались бы, на их взгляд, самому простому пути - простому переделыванию одной программы в другую. С реальными примерами, когда задачи решаются подобным способом, я сталкиваюсь чуть ли не каждый день. И слишком часто оказывается, что человек, потратив много сил и времени, решил-таки задачу приведённым выше способом и потом начинает доказывать, что он и так потратил много сил и точно уверен в том, что любой другой способ - сложнее этого.

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

antilex_body(L,I,M,L):-I>M.

Это утверждение противоречит вообще всем тем рассуждениям, которым мы можем следовать, когда «в лоб» переводим программу на Си в программу на Прологе: внутри этого утверждения ничего никуда не передаётся и ничего не вызывается. Условием завершения цикла это тоже назвать нельзя: цикл завершается, если не срабатывают проверки на сравнение переменных I и M в предыдущих двух утверждениях. С точки зрения программы на Си, это третье утверждение вообще неправильное: i не может быть больше, чем m, а вводя данное утверждение, мы сообщаем, что может.

В качестве тренировки, Вы можете поискать ответ на вопрос: «почему, если это утверждение удалить, то выводятся не все перестановки?»

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

Циклы vs рекурсия

Источником приведённой выше плохой программы является в первую очередь путаница между этими двумя понятиями.

Слишком часто обнаруживаются люди, которые, не задумываясь, решают задачу новыми средствами, но старым способом. В данном случае, цикл for() «в лоб» преобразовали в рекурсивный предикат, у которого каждый дочерний рекурсивный вызов соответствует каждой следующей итерации цикла for().

Возможно, это связано с тем распространённым заблуждением, что рекурсия - это один из способов представления циклов. Из этого заблуждения вытекает следующее заблуждение: один рекурсивный вызов соответствует одной итерации цикла. На самом деле это не так.

При работе с циклами мы можем сравнивать итерации как «следующая итерация» - «предыдущая итерация». При работе с рекурсией мы оперируем понятиями «дочерний вызов» - «родительский вызов». У одной итерации цикла не может быть несколько следующих итераций: итерация, следующая непосредственно после данной - всегда одна. У рекурсивной функции может быть много непосредственных дочерних вызовов.

Итерации циклов выполняются по очереди, одна за другой. Каждая следующая итерация цикла не начинается раньше, чем закончится предыдущая.

Рекурсивный вызов содержит в себе все вложенные рекурсивные вызовы. Дочерний вызов не может произойти раньше, чем произойдёт родительский вызов. Родительский вызов не может закончиться раньше, чем закончится дочерний вызов.

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

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

  Вот как выполняются итерации цикла
Вот как выполняются итерации цикла
 
  Правильное дерево моделирования рекурсии
А вот так выполняются рекурсивные вызовы. Правильное дерево моделирования рекурсии.
  Неправильное дерево моделирования рекурсии
Неправильное дерево моделирования рекурсии. Такой возврат не возможен ни в одном языке программирования.
 

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

Генератор перестановок в антилексикографическом порядке на Прологе

Чтобы написать правильный генератор перестановок в антилексикографическом порядке на Прологе, следует изначально отказаться от мысли переделывания программы на Си в программу на Прологе. Следует осознать тот факт, что решение рекурсивным предикатом и решение циклом - это разные, не сравнимые между собой способы решения. И хотя в программе на Си функция antilex() является рекурсивной, в ней также содержится и цикл for(), который, собственно, и портит всю картину.

Написать правильный генератор перестановок нам поможет утверждение, которое я привёл в самом начале этой статьи. На всякий случай повторю:

  Упорядоченная антилексикографически последовательность перестановок по значению последнего элемента в них может быть разбита на n блоков длины (n-1)!. При этом q-й блок на последнем месте имеет элемент, равный (n-q+1), а первые n-1 позиций этого блока определяют последовательность перестановок множества {1,2,…,n}\{q} в антилексикографическом порядке.

Собственно, из этого утверждения мы видим, что нам понадобится вспомогательный предикат, который возвращает из списка все его элементы, при этом удаляя возвращаемый элемент из списка, а также предикат, который потом этот выбранный элемент вставлял бы назад последним. Ну и, собственно предикат для генерации перестановок в антилексикографическом порядке, который будет по одному удалять элементы из списка, генерировать перестановки для полученного подсписка, а потом - вставлять этот элемент обратно в список.

Вот текст программы на языке Пролог:

domains
  i=integer
  l=i*
predicates
  antilex(l,l)
  insertlast(l,i,l)
  pop(l,i,l)
clauses
  insertlast([],X,[X]).
  insertlast([H|T],X,[H|R]):-
    insertlast(T,X,R).

  pop([H|T1],X,[H|T2]):-pop(T1,X,T2).
  pop([X|T],X,T).

  antilex([X],[X]).
  antilex(L1,L2):-
    pop(L1,X,T1),
    antilex(T1,T2),
    insertlast(T2,X,L2).

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

Юрий Попов, popoff.donetsk.ua

Смотрите также

1. Перестановки в антилексикографическом порядке
http://www.mgopu.ru/PVU/2.1/Recurs/GenTrans/antilex.htm

2. Лекция: Логическое программирование. Списки.
http://www.intuit.ru/department/se/pinform/10/10.html

3. Поиск минимума в Прологе.
http://popoff.donetsk.ua/text/work/prg/goto/min.html

4. Рекурсофобия.
http://popoff.donetsk.ua/text/work/prg/sick/recursionphobia.html

Последняя модификация: 16.12.06 05:59

Не проходите мимо! Оставьте Ваш комментарий в форуме! >>>