Использование next_permutation

@okman · Регистрация: 05.04.2013

Студворк — интернет-сервис помощи студентам

Правильно ли я использую next_permutation? Мне нужно вывести все перестановки символов данной строки в алфавитном порядке.

C++
1
2
3
4
5
          do
        {
            lines.push_back(a);
        }
        while (next_permutation(a.begin(), a.end()));

Просто мне кажется что уж больно мало генерируется вариантов

@castaway · 26.07.2015, 20:26

Все вопросы, в том числе риторические, не дают оснований дать правильный ответ.
Что такое a?

@okman · 26.07.2015, 20:30 **[ТС]**

Это просто строка которую я считываю дабы сделать ее перебор

C++
1
2
string a;
cin>>a;

@castaway · 26.07.2015, 20:36

Перебираешь правильно. Как ты их выводишь я не вижу.

@okman · 26.07.2015, 20:41 **[ТС]**

Сначала сортирую так как мне нужно перебор перестановок в лексикографическом порядке потом вывожу

C++
1
2
sort(a.begin(),a.end());
       copy(lines.begin(), lines.end(), ostream_iterator<string>(cout,"\n"));

@castaway · 26.07.2015, 20:46

Я потерял смысл вопроса...
Что вводишь, и что выводит? Почему тебе кажется что вариантов мало?

@okman · 26.07.2015, 20:57 **[ТС]**

Ибо задача при отправлении на сервер падает на 5-ом тесте. Суть задачи:
Дана строка, состоящая из N попарно различных символов. Требуется вывести все перестановки символов данной строки в алфавитном порядке.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main() 
{
    string a;
    freopen("INPUT.txt","r",stdin);
    freopen("OUTPUT.txt","w",stdout);
    cin>>a;
        do
        {
            lines.push_back(a);
        }
        while (next_permutation(a.begin(), a.end()));
        sort(a.begin(),a.end());
       copy(lines.begin(), lines.end(), ostream_iterator<string>(cout,"\n"));
 
    return 0;
}

Добавлено через 3 минуты
In
ab123
Out

Кликните здесь для просмотра всего текста

ab123
ab132
ab213
ab231
ab312
ab321
b123a
b12a3
b132a
b13a2
b1a23
b1a32
b213a
b21a3
b231a
b23a1
b2a13
b2a31
b312a
b31a2
b321a
b32a1
b3a12
b3a21
ba123
ba132
ba213
ba231
ba312
ba321

мне кажется их должно быть 120, разве нет?

@castaway · 26.07.2015, 21:05

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

@okman · 26.07.2015, 21:11 **[ТС]**

Я ничего занять не планирую. Я просто пытаюсь узнать правильно ли я использую stl
Я написал вам задачу которая стоит передо мной, написал свое решение и просто интересуюсь почему не работает. Есть мое решение где я вручную написал перебор. Оно тоже не проходит. Я просто интересуюсь почему. Если у вас вызывают какие-то там чувства посторонние люди то это нужно обсуждать на других форумах

@castaway · 26.07.2015, 21:24

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

@okman · 26.07.2015, 21:28 **[ТС]**

Ну вы же эксперт в с++ неужели не можете ответить в чем проблема моего решения? Без всяких "отвращений" и прочее. Я же не прошу вас решить ее или переписать.
За то что я решу задачу я кроме опыта не получу ничего, не нужно писать глупости о каких то нишах))

Добавлено через 2 минуты
немного выше я показываю результаты теста и задаю вопрос правильный ли результат. Ведь программа должна была вывести 5! строк. Или я не правильно понимаю работы next_permutation?

@ct0r · 26.07.2015, 21:52

okman, так?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
 
int main() 
{
    string a = "cater";
    sort(a.begin(), a.end());
    do {
        cout << a << '\n';
    }
    while (next_permutation(a.begin(), a.end()));
}

@okman · 26.07.2015, 22:03 **[ТС]**

Спасибо большое, значит сортировать нужно было до перебора

не подскажете что конкретно поменялось?

@ct0r · 26.07.2015, 22:15

okman,
next_permutation возвращает перестановку, которая больше. Поэтому если сначала не отсортировать символы в строке, то мы потеряем те перестановки, в которых сейчас меньшие символы идут за бОльшими. То есть например, у нас 1,2,3 меньше, чем "а", поэтому ты там и потерял все перестановки, которые с них начинаются. next_permutation не может вынести их вперед, потому что тогда уже получится лексиграфически меньшая перестановка.

@Kuzia domovenok · 27.07.2015, 16:43

castaway, я не понял, о какой нише ты говоришь.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	Установка Emscripten SDK (emsdk) и CMake на Windows для сборки C и C++ приложений в WebAssembly (Wasm) 8Observer8 30.01.2026 Чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. Система контроля версиями Git. . .	Подключение Box2D v3 к SDL3 для Android: физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	Влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .

@castaway 4986 / 3093 / 456 Регистрация: 10.11.2010 Сообщений: 11,170 Записей в блоге: 10
	26.07.2015, 20:26
	Все вопросы, в том числе риторические, не дают оснований дать правильный ответ. Что такое a? 0

@castaway 4986 / 3093 / 456 Регистрация: 10.11.2010 Сообщений: 11,170 Записей в блоге: 10
	26.07.2015, 20:36
	Перебираешь правильно. Как ты их выводишь я не вижу. 0

@castaway 4986 / 3093 / 456 Регистрация: 10.11.2010 Сообщений: 11,170 Записей в блоге: 10
	26.07.2015, 20:46
	Я потерял смысл вопроса... Что вводишь, и что выводит? Почему тебе кажется что вариантов мало? 0

@castaway 4986 / 3093 / 456 Регистрация: 10.11.2010 Сообщений: 11,170 Записей в блоге: 10
	26.07.2015, 21:05
	Честно говоря, у меня вызывают отвращение пользователи, которые хотят занять свою нишу на определённом ресурсе чужими руками. Вы даже проблему описать не можете. 0

@okman 15 / 21 / 8 Регистрация: 05.04.2013 Сообщений: 204
	26.07.2015, 21:11 [ТС]
	Я ничего занять не планирую. Я просто пытаюсь узнать правильно ли я использую stl Я написал вам задачу которая стоит передо мной, написал свое решение и просто интересуюсь почему не работает. Есть мое решение где я вручную написал перебор. Оно тоже не проходит. Я просто интересуюсь почему. Если у вас вызывают какие-то там чувства посторонние люди то это нужно обсуждать на других форумах 0

@castaway 4986 / 3093 / 456 Регистрация: 10.11.2010 Сообщений: 11,170 Записей в блоге: 10
	26.07.2015, 21:24
	okman, в начале темы вы обозначили проблему, которую подтвердить не смогли. О какой помощи может идти речь? 0

@okman 15 / 21 / 8 Регистрация: 05.04.2013 Сообщений: 204
	26.07.2015, 21:28 [ТС]
	Ну вы же эксперт в с++ неужели не можете ответить в чем проблема моего решения? Без всяких "отвращений" и прочее. Я же не прошу вас решить ее или переписать. За то что я решу задачу я кроме опыта не получу ничего, не нужно писать глупости о каких то нишах)) Добавлено через 2 минуты немного выше я показываю результаты теста и задаю вопрос правильный ли результат. Ведь программа должна была вывести 5! строк. Или я не правильно понимаю работы next_permutation? 0

@okman 15 / 21 / 8 Регистрация: 05.04.2013 Сообщений: 204
	26.07.2015, 22:03 [ТС]
	Спасибо большое, значит сортировать нужно было до перебора не подскажете что конкретно поменялось? 0

@ct0r Игогошка! 1801 / 708 / 44 Регистрация: 19.08.2012 Сообщений: 1,367
	26.07.2015, 22:15
	okman, next_permutation возвращает перестановку, которая больше. Поэтому если сначала не отсортировать символы в строке, то мы потеряем те перестановки, в которых сейчас меньшие символы идут за бОльшими. То есть например, у нас 1,2,3 меньше, чем "а", поэтому ты там и потерял все перестановки, которые с них начинаются. next_permutation не может вынести их вперед, потому что тогда уже получится лексиграфически меньшая перестановка. 1

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,532 Записей в блоге: 1
	27.07.2015, 16:43
	castaway, я не понял, о какой нише ты говоришь. 0

Использование next_permutation

Решение