Форум программистов, компьютерный форум CyberForum.ru

Next_permutation - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 44, средняя оценка - 4.91
sam5213
0 / 0 / 0
Регистрация: 13.07.2010
Сообщений: 46
21.06.2012, 10:16     Next_permutation #1
Здравствуйте,
Вот не понимаю, каким образом алгоритм next_permutation выполняет следующую большую перестановку. Он как-то генерирует элементы последовательности? как в самом деле он работает?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.06.2012, 10:16     Next_permutation
Посмотрите здесь:

C++ Перестановки с next_permutation
Перестановки next_permutation + map C++
C++ Использование next_permutation

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
21.06.2012, 10:27     Next_permutation #2
Элементы последовательности (итераторы) передаются в виде аргументов.

Производит перестановку элементов диапазона

Переставляет элементы диапазона [first, last), в результате чего получается следующая, бОльшая перестановка. Сравнение отдельных элементов происходит: в первом варианте с помощью оператора <, а во втором варианте с помощью оператора comp.

Перестановка - это любой вариант из N! возможных вариантов расположения элементов в диапазоне относительно друг друга. Различные перестановки могут быть упорядочены по возрастанию их относительного лексикографического сравнения между собой; Первая перестановка в таком отсортированном списке (та, которая является лексикографически наименьшей из всех перестановок) будет та, при которой все элементы диапазона упорядочены по возрастанию. Наибольшая перестановка будет та, в которой все элементы упорядочены по убыванию.

Если функция может определить следующую перестановку, она переставляет элементы в следующую перестановку и возвращает истину. Если невозможно определить следующую перестановку (потому что она уже является наибольшей), функция переставляет элементы в соответствии с первой перестановкой (отсортированной по возрастанию) и возвращает ложь.
sam5213
0 / 0 / 0
Регистрация: 13.07.2010
Сообщений: 46
21.06.2012, 10:37  [ТС]     Next_permutation #3
вы могли бы мне по-подробнее рассказать вот этот момент "Элементы последовательности (итераторы) передаются в виде аргументов" ?
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
21.06.2012, 10:44     Next_permutation #4
next_permutation( ИТЕРАТОР_НАЧАЛА_МАССИВА, ИТЕРАТОР_КОНЦА_МАССИВА );

Если массив это vector<int> v;, то вызов будет
next_permutation( v.begin(), v.end() );
А вообще, MSDN.
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,405
21.06.2012, 12:30     Next_permutation #5
http://cplusplus.com/reference/algor...t_permutation/
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
// next_permutation and prev_permutation, with and without an explicitly
  // supplied comparison function.
 
  /**
   *  @brief  Permute range into the next "dictionary" ordering.
   *  @param  first  Start of range.
   *  @param  last   End of range.
   *  @return  False if wrapped to first permutation, true otherwise.
   *
   *  Treats all permutations of the range as a set of "dictionary" sorted
   *  sequences.  Permutes the current sequence into the next one of this set.
   *  Returns true if there are more sequences to generate.  If the sequence
   *  is the largest of the set, the smallest is generated and false returned.
  */
  template<typename _BidirectionalIterator>
    bool
    next_permutation(_BidirectionalIterator __first,
             _BidirectionalIterator __last)
    {
      // concept requirements
      __glibcxx_function_requires(_BidirectionalIteratorConcept<
                  _BidirectionalIterator>)
      __glibcxx_function_requires(_LessThanComparableConcept<
        typename iterator_traits<_BidirectionalIterator>::value_type>)
      __glibcxx_requires_valid_range(__first, __last);
 
      if (__first == __last)
    return false;
      _BidirectionalIterator __i = __first;
      ++__i;
      if (__i == __last)
    return false;
      __i = __last;
      --__i;
 
      for(;;)
    {
      _BidirectionalIterator __ii = __i;
      --__i;
      if (*__i < *__ii)
        {
          _BidirectionalIterator __j = __last;
          while (!(*__i < *--__j))
        {}
          std::iter_swap(__i, __j);
          std::reverse(__ii, __last);
          return true;
        }
      if (__i == __first)
        {
          std::reverse(__first, __last);
          return false;
        }
    }
    }
 
  /**
   *  @brief  Permute range into the next "dictionary" ordering using
   *  comparison functor.
   *  @param  first  Start of range.
   *  @param  last   End of range.
   *  @param  comp
   *  @return  False if wrapped to first permutation, true otherwise.
   *
   *  Treats all permutations of the range [first,last) as a set of
   *  "dictionary" sorted sequences ordered by @a comp.  Permutes the current
   *  sequence into the next one of this set.  Returns true if there are more
   *  sequences to generate.  If the sequence is the largest of the set, the
   *  smallest is generated and false returned.
  */
  template<typename _BidirectionalIterator, typename _Compare>
    bool
    next_permutation(_BidirectionalIterator __first,
             _BidirectionalIterator __last, _Compare __comp)
    {
      // concept requirements
      __glibcxx_function_requires(_BidirectionalIteratorConcept<
                  _BidirectionalIterator>)
      __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
        typename iterator_traits<_BidirectionalIterator>::value_type,
        typename iterator_traits<_BidirectionalIterator>::value_type>)
      __glibcxx_requires_valid_range(__first, __last);
 
      if (__first == __last)
    return false;
      _BidirectionalIterator __i = __first;
      ++__i;
      if (__i == __last)
    return false;
      __i = __last;
      --__i;
 
      for(;;)
    {
      _BidirectionalIterator __ii = __i;
      --__i;
      if (__comp(*__i, *__ii))
        {
          _BidirectionalIterator __j = __last;
          while (!__comp(*__i, *--__j))
        {}
          std::iter_swap(__i, __j);
          std::reverse(__ii, __last);
          return true;
        }
      if (__i == __first)
        {
          std::reverse(__first, __last);
          return false;
        }
    }
    }
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
21.06.2012, 20:03     Next_permutation #6
Он генерирует лексикографические перестановки, которые более наглядны, но менее эффективны. Подробнее о перестановках можно у С. Скиена почитать.
Yandex
Объявления
21.06.2012, 20:03     Next_permutation
Ответ Создать тему
Опции темы

Текущее время: 08:37. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru