Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/18: Рейтинг темы: голосов - 18, средняя оценка - 4.67
0 / 0 / 0
Регистрация: 16.08.2015
Сообщений: 8
1

Сортировка обменом (перестановками)

05.11.2018, 23:05. Показов 3539. Ответов 8
Метки нет (Все метки)

Требуется написать программу для решения задачи(картинка во вложении). Имеется код для генерации всех перестановок. Но эта генерация работает, предварительно отсортировав строку. Как написать генерацию, которая выведет всевозможные перестановки, не сортируя строку перед этим? Нужно сделать так, чтобы генерация перестановок остановилась, когда строка будет отсортирована по возрастанию, как это реализовать?


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <string>
#include <algorithm>
 
int main() {
    string a;
    cin >> a;
    string s = a;
    sort(s.begin(), s.end());
    do
        cout << s << endl;
    while (next_permutation(s.begin(), s.end()));
    system("pause");
}
0
Миниатюры
Сортировка обменом (перестановками)  
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
05.11.2018, 23:05
Ответы с готовыми решениями:

сортировка перестановками
нужно отсортировать линейный список перестановками я так понимаю это тоже самое что пузырек?

Сортировка перестановками
Хотел написать функцию для сортировки. Компилятор ошибок не выдает.На выводе выходит это: 3 2 5 4 ...

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

Сортировка обменом массива. Усложненный вариант сортировки
Сделать сортировку обменом массива случайных чисел от -Н до Н-1. Рвсположить элементы сначала...

8
1473 / 937 / 810
Регистрация: 30.04.2016
Сообщений: 3,255
05.11.2018, 23:15 2
Dabby, здравствуйте! Чтобы перебрать все возможные сочетания, функции next_permutation() нужная отправная точка, то есть отсортированная строка. Проверку можно сделать с помощью функции is_sorted(). Можно еще использовать рекурсию для получения всех вариантов. Смотря, что вам нужно. Сочетания, размещения, с повторами или без?
0
0 / 0 / 0
Регистрация: 16.08.2015
Сообщений: 8
05.11.2018, 23:59  [ТС] 3
Цитата Сообщение от Fixer_84 Посмотреть сообщение
Можно еще использовать рекурсию для получения всех вариантов. Смотря, что вам нужно. Сочетания, размещения, с повторами или без?
Спасибо за ответ! Судя по всему, нужна рекурсия, с повторами, которая будет выполняться при условии !is_sorted()

Добавлено через 34 минуты
Fixer_84, не разобрался как тут ответ работает
0
470 / 422 / 290
Регистрация: 10.03.2015
Сообщений: 1,782
06.11.2018, 00:07 4
Dabby, А теперь вопрос: что вы пытаетесь сделать после того, как отсортировали строку, выполнив при этом нужное задание?
0
0 / 0 / 0
Регистрация: 16.08.2015
Сообщений: 8
06.11.2018, 00:14  [ТС] 5
Dabby, А теперь вопрос: что вы пытаетесь сделать после того, как отсортировали строку, выполнив при этом нужное задание?
SuperKir, после выполнения сортировки просто вывести отсортированную строку.
0
470 / 422 / 290
Регистрация: 10.03.2015
Сообщений: 1,782
06.11.2018, 00:17 6
Dabby, эм..
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <string>
#include <algorithm>
 
using namespace std;
 
int main() {
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    cout << s << endl;
}
0
0 / 0 / 0
Регистрация: 16.08.2015
Сообщений: 8
06.11.2018, 00:21  [ТС] 7
SuperKir, нужно это сделать именно с помощью генерации перестановок
0
1473 / 937 / 810
Регистрация: 30.04.2016
Сообщений: 3,255
07.11.2018, 00:32 8
Лучший ответ Сообщение было отмечено Dabby как решение

Решение

Dabby, здравствуйте! Вот вариант с рекурсией:

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
#include <iostream> 
#include <string> 
#include <algorithm>
 
    using namespace std;
    
string res;
 
void printPerm(string const &s, string const &perm) {
    if (s.length() == 0) {
        if (is_sorted(perm.begin(), perm.end())) {
            res = perm;
            return;
        }
        return;
    }
    for (int i = 0; i < s.length(); i++) {
        char ch = s[i];
        string tmp = s.substr(0, i) + s.substr(i + 1);
        printPerm(tmp, perm + ch);
    }
}
 
void perm(string const &s) {
    printPerm(s, "");
}
 
int main() {
    string s;
    cout << "Enter a string (length <= 10):\n";
    getline(cin, s);
    perm(s);
    cout << "Output of the program:\n";
    cout << res << "\n";
    system("pause");
    return 0;
}
2
0 / 0 / 0
Регистрация: 16.08.2015
Сообщений: 8
07.11.2018, 14:47  [ТС] 9
Fixer_84, большое спасибо за ответ, это именно то, что нужно было!
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.11.2018, 14:47

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

Что делает сортировка простым обменом в одномерном массиве?
что делает сортировка простым обменом в одномерном массиве?по какому принципу она меняет элементы?

Сортировка массива методом Шейкера с выводом количества сравнений и обменом
Написал код для сортировки массива по Шейкеру. Мне еще нужно реализовать подсчет числа сравнений и...

Сортировка выбором, сортировка вставкой, сортировка заменой, сортировка обменом ("пузырьковая" сортировка)
Создать класс, содержащий массив и реализующий алгоритмы сортировки и бинарного поиска в этом...

Сортировка чисел выбором и простейшими перестановками
Ребят, помогите плииз написать проги! 1. Найти элемент массива, имеющий наименьшее значение,...


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.