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

Порядок перестановок - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
Shato
2 / 2 / 0
Регистрация: 16.03.2011
Сообщений: 82
25.10.2011, 21:58     Порядок перестановок #1
Ребят, если сделайте одну задачку, буду очень вам признателен, спасибо заранее вам!
Дано число N и K. Выведите K-ую перестановку в лексикографическом порядке из всех N! N-элементных перестановок.

Входные данные
В первой строке входного файла записано натуральные числа N, K (1 <= N <= 20, 1 <= K <= 2000000000). Гарантируется, что 1 <= K <= N!.

Выходные данные
Выведите искомую перестановку.

Пример

Ввод
3 2

Вывод
1 3 2

Потратьте немного вашего времени, если можете, спасибо!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.10.2011, 21:58     Порядок перестановок
Посмотрите здесь:

C++ кол-во перестановок
Выведение всех перестановок C++
Количество перестановок C++
C++ Задача на количество перестановок
C++ Число перестановок QuickSort
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
25.10.2011, 22:02     Порядок перестановок #2
пример корректен?
Shato
2 / 2 / 0
Регистрация: 16.03.2011
Сообщений: 82
25.10.2011, 22:35  [ТС]     Порядок перестановок #3
Цитата Сообщение от PointsEqual Посмотреть сообщение
пример корректен?
да, точно

Добавлено через 26 минут
Не получается?
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
25.10.2011, 22:39     Порядок перестановок #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
39
40
41
42
#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
std::string Sequence(int n)
{
    stringstream d;
 
    for (int i = 1; i < n + 1; ++i)
        d << i;
    return d.str();
}
 
std::string PermutationK(int n, int k)
{
    std::string seq = Sequence(n);
 
 
    int i = 1;
    //while(i < k)
    //{
        while (next_permutation(seq.begin(), seq.end()))
        {
 
 
        ++i;
        //cout << seq << endl;
        //cin.get();
        if (i >= k)
            return seq;
        }
    //}
}
 
int main()
{
    cout << "Res = " << PermutationK(3,2);
    return 0;
}
потестируй
Shato
2 / 2 / 0
Регистрация: 16.03.2011
Сообщений: 82
25.10.2011, 22:50  [ТС]     Порядок перестановок #5
чет не получается через пробел вывод сделать
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
25.10.2011, 22:54     Порядок перестановок #6
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
#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
std::string Sequence(int n)
{
    stringstream d;
 
    for (int i = 1; i < n + 1; ++i)
        d << i;
    return d.str();
}
 
 
std::string WithSpace(std::string const & str)
{
    std::string res = "";
    int SIZE = str.size();
    for (int i = 0; i < SIZE; ++i)
        res = res + str[i] + " ";
 
    return res;
}
 
 
void PermutationK(int n, int k)
{
    std::string seq = Sequence(n);
 
 
    int i = 1;
 
        while (next_permutation(seq.begin(), seq.end()))
        {
            ++i;
            if (i >= k)
            {
                cout << "Res = " << WithSpace(seq) << endl;
                break;
            }
        }
}
 
int main()
{
    PermutationK(5,2);
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.10.2011, 23:04     Порядок перестановок
Еще ссылки по теме:

C++ Как реализовать перемножение перестановок
Лексикографическое порождение перестановок C++
Метода Гаусса без перестановок C++

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.10.2011, 23:04     Порядок перестановок #7
PointsEqual, эта задача на комбинаторику. При тех значениях N и К, которые заданы - вычисление затянется на долго.

Shato, Вот почти Ваша задача: http://********/index.asp?main=task&id_task=189
Отличие только в том, в Вашем варианте нужно использовать __int64.
Вот код для той задачи (когда-то давно делал):
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
#include <stdio.h>
int fac(int a)
{
    if(a==0 || a==1)
        return 1;
    int temp=1;
    for(int i=2; i<=a; i++)
        temp*=i;
    return temp;
}
 
int main(){
    int N, K, *mas_rez, *mas, i, j, col, temp;
  freopen("input.txt","r",stdin);
 freopen("output.txt","w",stdout);
 scanf("%d %d", &N, &K);
 mas_rez=new int[N];
 mas=new int[N];
 for(i=0; i<N; i++)
     mas[i]=0;
 for(i=0; i<N; i++)
 {
     if(i<N-1)
     {
     temp=fac(N-i);
     temp/=(N-i);
     temp=((K-1)/temp)%(N-i);
     col=0;
     temp++;
     for(j=0; j<N && temp!=0; j++)
     {
         if(mas[j]==0)
            temp--;
         if(temp==0)
             col=j;
     }
     mas_rez[i]=col+1;
     mas[col]=1;
     }
     else
     {
         for(j=0; j<N; j++)
             if(!mas[j])
                 mas_rez[N-1]=j+1;
     }
 }
 for(i=0; i<N; i++)
     printf("%d ", mas_rez[i]);
   return 0;
}
Yandex
Объявления
25.10.2011, 23:04     Порядок перестановок
Ответ Создать тему
Опции темы

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