3 / 3 / 4
Регистрация: 11.11.2009
Сообщений: 41
1

Нахождение всех перестановок

12.04.2010, 14:49. Показов 1060. Ответов 2
Метки нет (Все метки)

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
#include <iostream>
#include <string>
using namespace std;
 
 
int aton(char a) // преобразование символа в номер цифры
{
    if ((a >= '0') && (a <= '9'))
        return a - '0';
    else if ((a >= 'a') && (a <= 'z'))
        return a - 'a' + 10;
    else
        return a - 'A' + 10;
}
 
int main()
{int a[10],b,i,j,k,Ls,x,z,q;
string s;
cout<<"Vvedite posledovatel'nost' chisel"<<"\n";
cin>>s;
q=0;i=1;j=1;
Ls=s.length();
for(i=1;i<Ls+1;i++) a[i]=aton(s[i-1]);
b=a[Ls];
do
{
i=Ls-1;
while(a[i]>a[i+1]) i=i-1;
j=i+1;
while(a[j]>a[i]) j=j+1;
j=j-1;
x=a[i];
a[i]=a[j];
a[j]=x;
for(k=1;k<(Ls-i+1)/2;k++)
{
    x=a[i+k];
    a[i+k]=a[Ls-k+1];
    a[Ls-k+1]=x;
}
cout<<"\n";
for(z=1;z<Ls+1;z++)
cout<<a[z];
q++;
cout<<"\n"<<q;
}
while(a[1]!=b);
cout<<"\n";
 
system("pause");
    return 0;
}
проблема состоит в том,что программа находит не все возможные перестановки.
Например
s=123
a=132
a=231
a=321

помогите разобраться в чем ошибка.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.04.2010, 14:49
Ответы с готовыми решениями:

Выведение всех перестановок
Драсте, я вот все время писал на паскале и мне с трудом дается переход на c++. Не могу сделать и...

Перебор всех перестановок символов в строке
Помогите решить задачу пожалуйста. Напишите функцию с прототипом void permute (const string &amp;...

Генерация всех перестановок n элементного множества
с++ 1) Напечатать все перестановки чисел от 1 до n используя рекурсивный алгоритм пример 123...

Генерация всех перестановок заданного множества
Никак не могу понять в чем проблема, задача состояла в генерации всех перестановок заданного...

2
1 / 1 / 1
Регистрация: 11.04.2021
Сообщений: 2
17.04.2021, 13:40 2
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
#include <iostream>
using namespace std;
void swap(int *a, int i, int j)
{
  int s = a[i];
  a[i] = a[j];
  a[j] = s;
}
bool NextSet(int *a, int n)
{
  int j = n - 2;
  while (j != -1 && a[j] >= a[j + 1]) j--;
  if (j == -1)
    return false; // больше перестановок нет
  int k = n - 1;
  while (a[j] >= a[k]) k--;
  swap(a, j, k);
  int l = j + 1, r = n - 1; // сортируем оставшуюся часть последовательности
  while (l<r)
    swap(a, l++, r--);
  return true;
}
void Print(int *a, int n)  // вывод перестановки
{
  static int num = 1; // номер перестановки
  cout.width(3); // ширина поля вывода номера перестановки
  cout << num++ << ": ";
  for (int i = 0; i < n; i++)
    cout << a[i] << " ";
  cout << endl;
}
int main()
{
  int n, *a;
  cin >> n;
  a = new int[n];
  for (int i = 0; i < n; i++)
    a[i] = i + 1;
  Print(a, n);
  while (NextSet(a, n))
    Print(a, n);
  return 0;
//и да кстати есть такая библиотека <algorithm> вроде там есть отдельная функция под это(но я не уверен)
}
0
Диссидент
Эксперт C
26856 / 16758 / 3675
Регистрация: 24.12.2010
Сообщений: 37,521
17.04.2021, 13:58 3
Цитата Сообщение от Lord_bone Посмотреть сообщение
вроде там есть отдельная функция под это(но я не уверен)
Есть. Называется что-то вроде next_permutation
Но я считаю чрезвычайно полезным для начинающих пытаться изобретать свои велосипеды

Добавлено через 3 минуты
Вот нашел... На Си, правда... Но это не суть
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
#include <stdio.h>
#define N 10
 
int main()
{ int s[N+1], t; int i, j, r, k;
 
 for(i=0; i<N; i++) s[i] = i; // Начальное заполнение
 
 while(1) {
   for(i=0; i<N; i++)  // Вывод перестановки
      printf("%2d ", s[i]);
   printf("\n");
       // Находим самое правое место, где s[i] < s[i+1]
   for(i=N-1; i>=0 && s[i] > s[i+1]; i--)   // Тело цикла пустое
   ;
   if (i<0) break; // Уже получили "10-9-8-7-6-5-4-3-2-1" - самую старшую перестановку
       // Находим s[j] - наименьший элемент справа от s[i] и больший его
   for(j=N-1; s[i] > s[j]; j--)
   ;
       // Меняем s[i] <-> s[j]
   t = s[j];
   s[j] = s[i];
   s[i] = t;
       // То, что за "i" - переворачиваем
   for(k=i+1, r=N-1; r > k; k++, r--) {
     t = s[r];
     s[r] = s[k];
     s[k] = t;
   }
 }
 return 0;
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.04.2021, 13:58
Помогаю со студенческими работами здесь

Генерация массива всех перестановок из n элементов.
Нашел по этой теме здесь на форумах такой код: #include &lt;iostream.h&gt; int X; int N; void...

Рекурсивная процедура печати всех перестановок из n символов
&quot;Написать процедуру печати всех перестановок из n символов&quot; методом рекурсии непривычно и...

Вывод всех перестановок без использования массивов
Вот есть такая проблема: нужно вывести все возможные перестановки чисел от 1 до n тема жутко...

Поиск всех перестановок символов из строки (0..9)..пожалуйста помогите!!!
ведь наверняка ктото уже писал такие алгоритмы будь то на олимпеаде или где ещё!!!..... мне в...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru