next_permutation и prev_permutation удобны, и хорошо что они есть(сам их использовал не так давно). Но опять возникает такой вопрос: как много времени могут выполняться данные функции ? Стандарт ничего не говорит (и судя по всему не должен), это не очень хорошо

SSудобны
Когда число элементов не более 12 (Кнут в первом издании говорит о 10, но это было больше 30 лет назад)

mcureenab,

подумал вы это из стандарта взяли, ещё раз посмотрел, и оказывается я вас обманул. В стандарте указано следующее:
ISO/IEC N3242=11-0012Complexity: At most (last-most)/2 swaps.
Хотя бы что-то есть.

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

Видные информатики, Кнут, Скиена говорят о том, что достаточно часто программисты неверно понимают и, самое главное, используют, асимптотические обозначения, и . В стандарте написано "at most". Что это значит ? Не больше ? То есть это оценка сверху ? Либо это значит в большинстве случаев ? Мне кажется что понимать следует так. Хочется чтобы стандарт был более строг в этом отношении.

Думаю что скорее всего использовали перебор с возвратом

mcureenabSashaMercuryв большинстве случаев чьих случаев? моих или твоих или автора? тут распределение не задано, поэтому о статистике случаев нет смысла говорить. если иное не указано, нужно понимать "худший" случай.

для перебора с возвратом наверное стек нужен, а тут стека вроде как нет.

есть тут стек или нет вы не знаете, как и я. На то она и инкапсуляция. Но я уверен что циклический сдвиг в данном алгоритме совершенно ни причём :)

А под 'случаем' тут понимается исходная перестановка. Если вы не согласны с моей трактовкой того что написано в стандарте, предложите свою версию ;)

mcureenabSashaMercuryА под 'случаем' тут понимается исходная перестановка. Если вы не согласны с моей трактовкой того что написано в стандарте, предложите свою версию ;) "At most bla-bla-bla", означает не хуже чем bla-bla-bla для всякого исходного порядка, а не для какого то усредненного.

Тут вы сами себе противоречите

mcureenab Оно и понятно, в одних задачах могут встречаться только "хорошие" порядки для которых и делать ничего не надо, один swap и готово, в других только "плохие" порядки, где надо двигать весь массив.

Dima TСаш, просвяти зачем тебе сложность данного алгоритма? массив из N элементов может быть переставлен N! раз. Т.е. больше 12-13 элементов это много комбинаций, но при этом сама перестановка будет быстра. Какая может быть задача чтобы потребовалось частично переставлять элементы в массиве например из 100-1000 элементов? Все 1000! вариантов точно не перебрать за разумное время.

Было интересно, потому спросил