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

те же перестановки - C++

Восстановить пароль Регистрация
 
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
25.10.2011, 23:53     те же перестановки #1
Вот опять задачка на перестановки, если кому интересно, или кому просто не трудно сделать, буду очень признателен! Заранее огромное спасибо.
Дана последовательность 1, ... , n.
Нужно найти все перестановки этой последовательности так, чтобы числа стоящие на своих позициях не вставали на них снова, и посчитать кол-во этих перестановок.
т.е. например 1, 2, 3. это 2, 3, 1 и 3, 1, 2. кол-во = 2;
1, 2, 3, 4. это 2, 1, 4, 3. 3, 4, 2, 1. 4, 3, 1, 2.и т д
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.10.2011, 23:53     те же перестановки
Посмотрите здесь:

C++ перестановки в С++
Перестановки C++
C++ Сдвиг перестановки.
Инверсии и перестановки C++
перестановки с повторениями! C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
26.10.2011, 00:00     те же перестановки #2
Montanaa, задача очень проста:
кол-во всегда равно n-1
а сами перестановки делаете циклически (по кругу) сдвигая числа.
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
26.10.2011, 16:12  [ТС]     те же перестановки #3
Вам не составит труда написать код? я так не могу разобраться ((
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
26.10.2011, 16:18     те же перестановки #4
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
int main()
{
    int n;
    std::cin >> n;
    std::vector<int> arr(n);
    std::cout << "Count: " << n - 1 << "\nPermutations:\n";
    for (int i = 0; i < n; ++i)
        arr[i] = i + 1;
    
    for (int i = 0; i < n - 1; ++i)
    {
        std::rotate( arr.begin(), arr.begin() + 1, arr.end() );
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int> (std::cout, " ") );
        std::cout << std::endl;
    }
}
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
26.10.2011, 16:38  [ТС]     те же перестановки #5
Цитата Сообщение от diagon Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
int main()
{
    int n;
    std::cin >> n;
    std::vector<int> arr(n);
    std::cout << "Count: " << n - 1 << "\nPermutations:\n";
    for (int i = 0; i < n; ++i)
        arr[i] = i + 1;
    
    for (int i = 0; i < n - 1; ++i)
    {
        std::rotate( arr.begin(), arr.begin() + 1, arr.end() );
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int> (std::cout, " ") );
        std::cout << std::endl;
    }
}
смысл немножко не в этом. я задаю какую то последовательность цифр. а программа должна выводить все возможные перестановки так, чтобы цифры не стояли на своих позициях. и посчитать кол-во таких перестановок
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
26.10.2011, 19:15     те же перестановки #6
Цитата Сообщение от Montanaa Посмотреть сообщение
смысл немножко не в этом. я задаю какую то последовательность цифр. а программа должна выводить все возможные перестановки так, чтобы цифры не стояли на своих позициях. и посчитать кол-во таких перестановок
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
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
int main()
{
        std::cout << "Enter size of array: ";
        int n;
        std::cin >> n;
        
        std::cout << "Enter array: ";
        std::vector<int> arr(n);
        for (int i = 0; i < n; ++i)
            std::cin >> arr[i];
            
        std::cout << "Count: " << n - 1 << "\nPermutations:\n";
        
        for (int i = 0; i < n - 1; ++i)
        {
                std::rotate( arr.begin(), arr.begin() + 1, arr.end() );
                std::copy( arr.begin(), arr.end(), std::ostream_iterator<int> (std::cout, " ") );
                std::cout << std::endl;
        }
}
Yandex
Объявления
26.10.2011, 19:15     те же перестановки
Ответ Создать тему
Опции темы

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