Перестановочные алгоритмы. Перестановка элементов

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

   
Для выполнения перестановки элементов существуют следующие алгоритмы:

  bool
  next_permutation (BidirectionalIterator beg, BidirectionalIterator end)
  bool
  prev_permutation (BidirectionalIterator beg, BidirectionalIterator end)

   
Алгоритм next_permutation() изменяет порядок следования элементов в интервале [beg,end) в соответствии со следующей перестановкой.

   
Алгоритм prev_permutation() изменяет порядок следования элементов в интервале [beg,end) в соответствии с предыдущей перестановкой.

   
Оба алгоритма возвращают false, если элементы находятся в "нормальном" (лексикографическом) порядке, то есть упорядочены по
возрастанию для next_ permutation() или по убыванию для prev_permutation(). Следовательно, для того чтобы перебрать все
перестановки, нужно отсортировать элементы (по возрастанию или убыванию) и организовать цикл, который вызывает алгоритм
next_ permutation() или prev_permutation() до тех пор, пока алгоритм возвращает true.

   Замечание.
Алгоритмы next_permutation() и prev_permutation() также могут использоваться для сортировки элементов в интервале -
просто вызывайте их до тех пор, пока возвращаемое значение остается равным true. Впрочем, такой способ сортировки отличается очень
плохой эффективностью.

   
Сложность линейная (не более numberOfElements/2 обменов).

   
Следующий пример показывает, как при помощи алгоритмов next_permutation() и prev_permutation() генерируются все перестановки элементов:

//---------------------------------------------------------------------------

#include <vcl.h>
#include <iterator>
#include "algostuff.hpp"

#include <conio.h> //необходимо для getch()

#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused
using namespace std;

std::string ToRus(const std::string &in)
{
  char *buff = new char [in.length()+1];
  CharToOem(in.c_str(),buff);
  std::string out(buff);
  delete [] buff;
  return out;
}

int main()
{
  vector<int> coll;

  INSERT_ELEMENTS(coll,1,3);
  PRINT_ELEMENTS(coll,"Исходный вектор:\n");

  // Генерировать перестановки элементов до тех пор, пока они
  //   не будут упорядочены
  //   - при этом перебираются все возможные перестановки,
  //   - потому что в исходном состоянии
  //   - элементы упорядочены по возрастанию
  cout << ToRus("Перестановки:\n");
  while (next_permutation(coll.begin(),coll.end())) {
      PRINT_ELEMENTS(coll," ");
  }
  PRINT_ELEMENTS(coll,"Исходная перестановка:\n");

  // Генерировать перестановки элементов до тех пор,
  //   пока элементы не будут упорядочены по убыванию
  //   - это будет следующая перестановка после сортировки
  //   - по возрастанию, поэтому цикл сразу же завершается
  while (prev_permutation(coll.begin(),coll.end())) {
      PRINT_ELEMENTS(coll," ");
  }
  PRINT_ELEMENTS(coll,"Конечная перестановка:\n");

  // Генерировать перестановки элементов до тех пор,
  //   пока элементы не будут упорядочены по убыванию
  //   - при этом перебираются все возможные перестановки,
  //   - потому что в исходном состоянии
  //   - элементы упорядочены по убыванию
  while (prev_permutation(coll.begin(),coll.end())) {
      PRINT_ELEMENTS(coll," ");
  }
    PRINT_ELEMENTS(coll,"Перестановка:\n");


  getch();
  return 0;
}

//---------------------------------------------------------------------------

Текст этого примера можно взять здесь.

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


Рис.1. Результат выполнения приложения

   
На следующем шаге мы рассмотрим перестановку элементов в случайном порядке.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий