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

Опять алгоритмы сорировки) - C++

Восстановить пароль Регистрация
 
tcennoc
1 / 1 / 0
Регистрация: 22.11.2013
Сообщений: 35
03.12.2013, 20:51     Опять алгоритмы сорировки) #1
Подскажите пожалуйста какой алгоритм сортировки будет выдавать все перестановки чисел без повторений.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.12.2013, 20:51     Опять алгоритмы сорировки)
Посмотрите здесь:

опять строки C++
Опять конструкторы C++
C++ Опять интегралы....
Опять текстуры C++
Опять static C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nick Alte
Эксперт С++
1590 / 982 / 115
Регистрация: 27.09.2009
Сообщений: 1,897
Завершенные тесты: 1
03.12.2013, 21:01     Опять алгоритмы сорировки) #2
Для этого нужен не алгоритм сортировки, а алгоритм перестановки.
tcennoc
1 / 1 / 0
Регистрация: 22.11.2013
Сообщений: 35
03.12.2013, 21:17  [ТС]     Опять алгоритмы сорировки) #3
Цитата Сообщение от Nick Alte Посмотреть сообщение
Для этого нужен не алгоритм сортировки, а алгоритм перестановки.
Это понятно, лексикографически, я уже сделал. Но какой еще алгоритм лучше применить для рекурсии? Пробовал обычную пузырьковую сортировку, но есть дубли.
Можно ли применить алгоритм сортировки в целях перестановки чисел.
Либо подскажите алгоритм кроме лексикографического.Не в виде программы, а пошагово.
Nick Alte
Эксперт С++
1590 / 982 / 115
Регистрация: 27.09.2009
Сообщений: 1,897
Завершенные тесты: 1
03.12.2013, 21:24     Опять алгоритмы сорировки) #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
По отдельности слова знакомые, но вот общий смысл совершенно теряется. Что понятно? Что лексикографически? Какая рекурсия? Зачем тут вообще сортировка?

Не по теме:

- Петька, приборы!
- Семьдесят восемь!
- Что семьдесят восемь?!
- А что приборы?!

tcennoc
1 / 1 / 0
Регистрация: 22.11.2013
Сообщений: 35
03.12.2013, 21:44  [ТС]     Опять алгоритмы сорировки) #5
Цитата Сообщение от Nick Alte Посмотреть сообщение
По отдельности слова знакомые, но вот общий смысл совершенно теряется. Что понятно? Что лексикографически? Какая рекурсия? Зачем тут вообще сортировка?

Не по теме:

- Петька, приборы!
- Семьдесят восемь!
- Что семьдесят восемь?!
- А что приборы?!

Какой алгоритм применить для нахождения перестановок рекурсией?
P.S. Я знаю, что для нахождения перестановок применяется алгоритм перестановок. Одним из алгоритмов перестановок является нахождение перестановок в лексикографическом порядке этот алгоритм я уже использовал.Хочу составить программу по нахождению перестановок при помощи рекурсии, для этой цели нужно выбрать алгоритм. С точки зрения простоты реализации предполагал, что можно использовать какой-либо алгоритм сортировки. Попробовал пузырьковый,но есть повторения. Исходя из вышеизложенного, что вы посоветуете.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
03.12.2013, 21:53     Опять алгоритмы сорировки) #6
Вам еще нужно, чтобы при всех перестановках последовательности (1; 2; 4; 3; 3) не выводило 2 раза 1 2 4 3 3 ?
tcennoc
1 / 1 / 0
Регистрация: 22.11.2013
Сообщений: 35
03.12.2013, 21:58  [ТС]     Опять алгоритмы сорировки) #7
Цитата Сообщение от Dani Посмотреть сообщение
Вам еще нужно, чтобы при всех перестановках последовательности (1; 2; 4; 3; 3) не выводило 2 раза 1 2 3 4 3 3 ?
Нет не нужно.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
03.12.2013, 22:00     Опять алгоритмы сорировки) #8
tcennoc, т.е. оно может выводить 2 раза такое? Что-то я совсем не в теме.
tcennoc
1 / 1 / 0
Регистрация: 22.11.2013
Сообщений: 35
03.12.2013, 22:03  [ТС]     Опять алгоритмы сорировки) #9
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
#include<iostream>
using namespace std;
const int n=4;
const int m=0;
 
void r(int* ar,int m,int n);
void swap(int* a,int* b);
int _tmain(int argc, _TCHAR* argv[])
{
int* ar=new int[n];
for(int i=0;i<n;i++)
ar[i]=i+1;
r(ar,m,n);
system("pause");
 
    return 0;
}
void r(int* ar,int m,int n)
{
if(m==23)
return;
if(n==1)
n=4;
if(ar+n-1>ar+n-2)
{
swap(ar+n-1,ar+n-2);
for(int i=0;i<4;i++)
cout<<*(ar+i);
cout<<endl;
}
r(ar,m+1,n-1);
}
void swap(int* a,int* b)
{
int temp=*a;
*a=*b;
*b=temp;
}
Выводит повторы.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
03.12.2013, 22:07     Опять алгоритмы сорировки) #10
Если тебе нужна сортировка, то, по глупому, например, ее можно юзать так: Возьми все перестановки, забей в вектор и отсортируй их обычным сортом (только их нужно сравнивать с первого элемента поэлементно). Затем, если в отсортированном векторе текущая и предыдущая перестановки не равны, то вывести текущую.
tcennoc
1 / 1 / 0
Регистрация: 22.11.2013
Сообщений: 35
03.12.2013, 22:16  [ТС]     Опять алгоритмы сорировки) #11
Цитата Сообщение от Dani Посмотреть сообщение
Если тебе нужна сортировка, то, по глупому, например, ее можно юзать так: Возьми все перестановки, забей в вектор и отсортируй их обычным сортом (только их нужно сравнивать с первого элемента поэлементно). Затем, если в отсортированном векторе текущая и предыдущая перестановки не равны, то вывести текущую.
Сортировка не обязательна. Вы бы не могли подсказать алгоритм перестановки кроме лексикографического. Не программу, а сам алгоритм словесно.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
03.12.2013, 22:21     Опять алгоритмы сорировки) #12
Если ты генерируешь перестановки лексикографически (ПРЕДВАРИТЕЛЬНО ОТСОРТИРОВАВ МАССИВ, ПО КОТОРОМУ ТЫ БУДЕШЬ СТРОИТЬ ПЕРЕСТАНОВКИ), то одинаковые перестановки (если такие будут), то они будут сгенерированы друг за другом. Поэтому, текущую перестановку достаточно проверять с предыдущей на равенство). При равенстве - текущая перестановка будет повтором предыдущей.
tcennoc
1 / 1 / 0
Регистрация: 22.11.2013
Сообщений: 35
03.12.2013, 22:30  [ТС]     Опять алгоритмы сорировки) #13
Цитата Сообщение от Dani Посмотреть сообщение
Если ты генерируешь перестановки лексикографически (ПРЕДВАРИТЕЛЬНО ОТСОРТИРОВАВ МАССИВ, ПО КОТОРОМУ ТЫ БУДЕШЬ СТРОИТЬ ПЕРЕСТАНОВКИ), то одинаковые перестановки (если такие будут), то они будут сгенерированы друг за другом. Поэтому, текущую перестановку достаточно проверять с предыдущей на равенство). При равенстве - текущая перестановка будет повтором предыдущей.
Лексикографически я уже сортировал все там работает, я хотел узнать есть ли еще какой нибудь простой алгоритм для перестановки, который можно было бы выразить рекурсивно. Вроде есть еще какой то рекурсивный алгоритм перестановок, но что он из себя представляет?
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
03.12.2013, 22:31     Опять алгоритмы сорировки) #14
Можно в рекурсии перебирать элемент, который нужно ставить на текущую позицию.
tcennoc
1 / 1 / 0
Регистрация: 22.11.2013
Сообщений: 35
03.12.2013, 22:40  [ТС]     Опять алгоритмы сорировки) #15
Цитата Сообщение от Dani Посмотреть сообщение
Можно в рекурсии перебирать элемент, который нужно ставить на текущую позицию.
А, как это сделать 1234,1243,1423,4123,4132,4312,3412,3421,3241.... Так они будут повторяться вот как это откорректировать?
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
03.12.2013, 22:41     Опять алгоритмы сорировки) #16
М-даа......
ОНИ БУДУТ В ЛЕКСИКОГРАФИЧЕСКОМ ПОРЯДКЕ. А КАК ИСПРАВИТЬ ПОВТОРЫ, ОПИСАНО МНОЮ ВЫШЕ
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.12.2013, 23:35     Опять алгоритмы сорировки)
Еще ссылки по теме:

опять же строки C++
Опять файлы C++
Опять указатели C++

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

Или воспользуйтесь поиском по форуму:
tcennoc
1 / 1 / 0
Регистрация: 22.11.2013
Сообщений: 35
03.12.2013, 23:35  [ТС]     Опять алгоритмы сорировки) #17
Цитата Сообщение от Dani Посмотреть сообщение
М-даа......
ОНИ БУДУТ В ЛЕКСИКОГРАФИЧЕСКОМ ПОРЯДКЕ. А КАК ИСПРАВИТЬ ПОВТОРЫ, ОПИСАНО МНОЮ ВЫШЕ
Т.Е. перебирать элементы 1234 1243 1324 1342 1423 1432 4123 4132 4213 Это лексикографически, а если применять рекурсию они НЕ будут в лексикографическом порядке.Вот нашел http://mech.math.msu.su/~shvetz/54/i...s_sIdeas.xhtml

Добавлено через 9 минут
Вот тут не совсем понятно. Для каждой комбинации 12,21 вставляем 3 12:312 132 123 21: 321 231 213 затем вставляем 4 в каждую из 3х значных комбинаций. Правильно?
Yandex
Объявления
03.12.2013, 23:35     Опять алгоритмы сорировки)
Ответ Создать тему
Опции темы

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