Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 26, средняя оценка - 4.62
Konstantin_D
14 / 14 / 6
Регистрация: 21.07.2011
Сообщений: 89
#1

Функция перестановки чисел. Алгоритм - C++

15.03.2012, 15:56. Просмотров 4552. Ответов 3
Метки нет (Все метки)

Нужна функция: int permutation (int n);
Которая печатает все перестановки чисел от 1 до n (по 1 комбинации в каждой строке).
Например, при n равном 2 функция должна напечатать 2 строки:
1 2
2 1
При n равном 3 функция должна напечатать 6 строк:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
При написании функции обратите внимание, что при произвольном n функция должна напечатать 1*2*3*4*…*(n-1)* n строк. Предложите возвращаемое значение.

Вот такая вот хрень попалась. С какой стороны к ней подступиться?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.03.2012, 15:56
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Функция перестановки чисел. Алгоритм (C++):

Составить алгоритм перестановки элементов массива по правилу
Задан массив из попарно различных чисел. Составить алгоритм перестановки...

Составить алгоритм перестановки элементов массива по правилу
Помогите сделать пожалуйста. Задан массив из попарно различных чисел. Составить...

Дано n различных натуральных чисел (n=5). Напечатать все перестановки этих чисел
Дано n различных натуральных чисел (n=5). Напечатать все перестановки этих...

Дано n различных чисел, напечатать все возможные перестановки этих чисел
Помогите пожалуйста решить задачу через рекурсию: Дано n различных чисел,...

Рекурсия: дано n различных натуральных чисел (n = 5). Напечатать все перестановки этих чисел
Дано n различных натуральных чисел (n = 5). Напечатать все перестановки этих...

Все возможные перестановки букв слова - нужен алгоритм
Доброго времени суток, форумчане. Помогите пожалуйста найти/составить алгоритм...

3
Melkor
30 / 30 / 6
Регистрация: 15.12.2011
Сообщений: 108
15.03.2012, 16:25 #2
в STL есть алгоритм next_permutation. посмотри как они его сделали.
1
Konstantin_D
14 / 14 / 6
Регистрация: 21.07.2011
Сообщений: 89
15.03.2012, 19:17  [ТС] #3
Переписал библиотечный next_permutation и получилось следующее:
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
53
54
55
#include <iostream>
#include <algorithm>
using namespace std;
 
// Это аналог библиотечного алгоритма
// next_permutation
bool next_perm(int* first, int* last) 
{
    if (first == last) return false;
    int* i = first;
    ++i;
    if (i == last) return false;
    i = last;
    --i;
 
    for(;;)
    {
        int* ii = i--;
        if (*i < *ii)
        {
            int* j = last;
            while ( !(*i < *--j) );
            iter_swap(i, j);
            reverse(ii, last);
            return true;
        }
        if (i == first)
        {
            reverse(first, last);
            return false;
        }
    }
}
void permutation (int n)
{
    int* ar = new int[n];
    for (int i=0; i<n; ++i)
        ar[i] = i+1;
 
    do
    {
        for (int i=0; i<n; ++i)
            cout << ar[i] << " ";
        cout << endl;
    }
    while ( next_perm(ar, ar+n) );
    
    delete [] ar;
}
int main()
{
    int n = 3;
    cout << "n = " << n << endl;
    permutation(n);
}
Но что-то не соображу как красиво извлечь из функции next_perm алгоритм перестановки чисел, встроить его в функцию permutation и запустить нужное количество раз, выводя содежимое массива на экран.

Добавлено через 5 минут
Работает, зараза, но не пойму как Уже кучу бумаги перевел рисуя схемы. Может кто знает алгоритм перестановки проще? То, что алгоритм существует не один - это точно.
0
sergestus
77 / 77 / 34
Регистрация: 26.10.2011
Сообщений: 220
Завершенные тесты: 1
15.10.2014, 10:41 #4
вот рекурсивный алгоритм:

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;
 
void permutation( int *m, int l, int n )
{
  if( l==n-1 ) 
  {
    for( int i=0; i<n; i++) cout << m[i];
    cout << ' ';
  }
  else 
  {    
    for( int i=l; i<n; i++ )
    {
      int tmp = m[l];
      m[l] = m[i];
      m[i] = tmp;    
      permutation( m, l+1, n );
      tmp = m[l];
      m[l] = m[i];
      m[i] = tmp;    
    }
  }
}
 
int main()
{
  int n = 4;
  int *m = new int[n];
 
  for( int i=0; i<n; i++)
    m[i] = i+1;
 
  permutation( m, 0, n );
  cout << endl;
  system("pause");
}
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.10.2014, 10:41
Привет! Вот еще темы с решениями:

Определить четность произвольной перестановки N чисел. Во входном файле записано само число N и затем N чисел
Определить четность произвольной перестановки N чисел. Во входном файле...

Рекурсивная функция для перестановки цифр в числе
не могу понять как это сделать, помогите пожалуйста:)

Рекурсивная функция: все возможные перестановки символов строки
Дана строка с n элементами. Например abs. Надо выводить все возможные варианты...

Перестановки из n чисел
Не получается написать функцию, которая сохраняет всевозможные перестановки из...


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

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

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