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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.75
SDmaN
54 / 51 / 2
Регистрация: 22.07.2011
Сообщений: 436
#1

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

17.10.2013, 22:12. Просмотров 1859. Ответов 15
Метки нет (Все метки)

Даны символы, например ABCDEF, и число n. Нужно вывести все возможные комбинации перестановок этих символов по n. Максимальное число комбинаций будет равно 6^n. Как реализовать алгоритм. Какой час бьюсь.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.10.2013, 22:12
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Перестановки (C++):

Перестановки: чтобы любые две соседние перестановки отличались только порядком двух соседних элементов - C++
Вводится число n <= 8. Вывести все перестановки чисел 1,2..,n, так, чтобы две любые две соседние перестановки отличались только порядком...

перестановки в С++ - C++
Поменять местами элементы с четными и нечетными номерами

Перестановки - C++
Есть число которое складается из нулей и единиц. C клавиатуры вводится N - общее количество цифр и K - количество единиц. Найти и вивести...

те же перестановки - C++
Вот опять задачка на перестановки, если кому интересно, или кому просто не трудно сделать, буду очень признателен! Заранее огромное...

Перестановки без i - C++
Есть рекурсивная функция ,генерирующая перестановки.Требуется,чтобы на i месте(p) не стоял i.Причем проверять это надо не при...

перестановки с повторениями! - C++
Помогите! есть прога все считает правильно только не выводит значения с повторениями! помогите исправить! // mat_kkursa.cpp:...

15
dzrkot
zzzZZZ...
519 / 349 / 53
Регистрация: 11.09.2013
Сообщений: 2,004
17.10.2013, 22:29 #2
я мб ошибаюсь, но по-моему максимально возможное число перестановок будет n=6! (факториал).
А вот как сделать, не знаю, надо подумать) ...была мысль сделать функцию которая возвращает ссылку и принимает 2 ссылки на 2 элемента, меняя их значения местами, ну и как нить рекурсивно это заделать

Не по теме:

спасибо теперь я не усну)

0
SDmaN
54 / 51 / 2
Регистрация: 22.07.2011
Сообщений: 436
17.10.2013, 22:38  [ТС] #3
Нет. Как раз таки 6^n.
Возмьем не 6 символов, а 2 (AB) и n = 3. Т.е. всего комбинаций 2^3=8:
AAA
AAB
ABA
ABB
BAA
BAB
BBA
BBB
0
dzrkot
zzzZZZ...
519 / 349 / 53
Регистрация: 11.09.2013
Сообщений: 2,004
17.10.2013, 22:38 #4
можно типа функцию с 1 циклом, которая меняет местами *А с остальными, а потом в этой функции вызвать себя же но *(А+1) и так далее...
0
Убежденный
Системный программист
Эксперт С++
15637 / 7147 / 1131
Регистрация: 02.05.2013
Сообщений: 11,586
Записей в блоге: 1
Завершенные тесты: 1
17.10.2013, 22:40 #5
Если все-таки перестановки, тогда подойдет std::next_permutation.
И не надо ничего реализовывать.
0
dzrkot
zzzZZZ...
519 / 349 / 53
Регистрация: 11.09.2013
Сообщений: 2,004
17.10.2013, 22:45 #6
то что ты сделал это выборка вроде...яне помню, надо почитать))
для АBC:
ABC 1
АСВ 2
ВСА 3
ВАС 4
CAB 5
CBA 6

Статистика. Теория вероятностей

почитай теорвер про перестановки
0
SDmaN
54 / 51 / 2
Регистрация: 22.07.2011
Сообщений: 436
17.10.2013, 22:57  [ТС] #7
В моем случае символы в строке могут повторяться. Для ABC:
AAA
AAB
AAC
ABA
ABB
ABC
ACA
ACB
ACC
BAA
BAB
BAC
BBA
BBB
BBC
BCA
BCB
BCC
CAA
CAB
CAC
CBA
CBB
CBC
CCA
CCB
CCC

Добавлено через 6 минут
То есть размещения с повторениями.
0
-=ЮрА=-
Заблокирован
Автор FAQ
17.10.2013, 23:11 #8
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
 
int main()
{
    int i, j, k, n;
    const char data[] = "ABCDEF";
    n = sizeof(data) / sizeof(data[0]) - 1;
    for( i = 0; i < n; i++ )
    for( j = 0; j < n; j++ )
    for( k = 0; k < n; k++ )
        cout<<data[i]<<data[j]<<data[k]<<endl;
    cin.get();
    return 0;
}
Вывод
AAA
AAB
AAC
AAD
AAE
AAF
ABA
ABB
ABC
ABD
ABE
ABF
ACA
ACB
ACC
ACD
ACE
ACF
ADA
ADB
ADC
ADD
ADE
ADF...
http://codepad.org/u6xSdFEl
0
MrGluck
Модератор
Эксперт CЭксперт С++
7285 / 4446 / 650
Регистрация: 29.11.2010
Сообщений: 12,026
17.10.2013, 23:19 #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
#include <iostream>
#include <clocale>
#include <algorithm>
 
using namespace std;
 
int main()
{
    setlocale(LC_ALL, "");
    const int N = 4;
    int A[N]; // имеем множество A {1, ... N}
    int counter = 0; // счетчик числа перестановок
    for (int i = 0; i < N; i++) // заполняем множество
        A[i] = i + 1;
    // sort(A, A + N); // необходимо при вводе произвольных элементов
    do
    {
        for (int i=0; i < N; i++)
            cout << A[i] << ' ';
        cout << endl;
        counter++;
    } while (next_permutation(A, A + N));
    cout << "Всего перестановок: " << counter << endl;
    return 0;
}
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
56
57
#include <iostream>
#include <clocale>
 
using namespace std;
 
// вывод множества на экран
void print(const int *A, const int size);
// функция перестановки двух чисел
void swap(int &, int &);
// функция генерации следующей перестановки
void next_perm(int k, int *A, const int size, int &counter);
 
 
int main()
{
    setlocale(LC_ALL, "");
    const int N = 4;
    int A[N]; // имеем множество A {1, ... N}
    int counter = 0; // счетчик числа перестановок
    for (int i = 0; i < N; i++) // заполняем множество
        A[i] = i + 1;
    next_perm(0, A, N, counter);
    cout << "Всего перестановок: " << counter << endl;
    return 0;
}
 
void print(const int *A, const int size)
{
    for (int i=0; i < size; i++)
        cout << A[i] << ' ';
    cout << endl;
}
 
void swap(int &x, int &y)
{
    int tmp = x;
    x = y;
    y = tmp;
}
 
void next_perm(int k, int *A, const int size, int &counter)
{
    // если заполнилось
    if (k == size)
    {
        print(A, size);
        counter++;
        return;
    }
 
    for(int i = k; i < size; i++)
    {
        swap(A[k], A[i]);
        next_perm(k + 1, A, size, counter); // следующая перестановка
        swap(A[k], A[i]);
    }
}
0
SDmaN
54 / 51 / 2
Регистрация: 22.07.2011
Сообщений: 436
17.10.2013, 23:24  [ТС] #10
-=ЮрА=-, спасибо, но всегда размещает по 3. Как исправить, чтобы размещал по нужному количеству?
0
-=ЮрА=-
Заблокирован
Автор FAQ
17.10.2013, 23:31 #11
Цитата Сообщение от SDmaN Посмотреть сообщение
Как исправить, чтобы размещал по нужному количеству?
- сколько надо за раз элементов - столкьо и вложенных циклов, скажем если надо 5 элементов то надо ввести +2 цикла ниже цикла по к
0
Убежденный
Системный программист
Эксперт С++
15637 / 7147 / 1131
Регистрация: 02.05.2013
Сообщений: 11,586
Записей в блоге: 1
Завершенные тесты: 1
17.10.2013, 23:36 #12
Ок, раз пошла такая пьянка, моя версия

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
56
57
58
59
60
#include <string.h>
#include <iostream>
 
 
 
namespace
{
 
 
 
void show_state(char const *pCharset, size_t const *pState, size_t StateSize)
{
    for (size_t i = 0; i < StateSize; ++i)
    {
        std::cout << pCharset[pState[i]];
    }
 
    std::cout << std::endl;
}
 
 
 
bool increment_state(size_t *pState, size_t StateSize)
{
    for (size_t i = 0; i < StateSize; ++i)
    {
        if (++pState[i] < StateSize)
        {
            return true;
        }
 
        pState[i] = 0;
    }
 
    return false;
}
 
 
 
} // namespace
 
 
 
int main()
{
    char const *pCharset = "ABC";
 
    size_t const StateSize = strlen(pCharset);
    size_t *pState = new size_t[StateSize];
    memset(pState, 0, StateSize * sizeof (size_t));
 
    do
    {
        show_state(pCharset, pState, StateSize);
    } while (false != increment_state(pState, StateSize));
 
    delete [] pState;
 
    return 0;
}
0
MrGluck
Модератор
Эксперт CЭксперт С++
7285 / 4446 / 650
Регистрация: 29.11.2010
Сообщений: 12,026
17.10.2013, 23:37 #13
SDmaN, у меня код для любого количества (задается константой), надо лишь поменять массив на символьный и заполнить его значениями
0
SDmaN
54 / 51 / 2
Регистрация: 22.07.2011
Сообщений: 436
17.10.2013, 23:39  [ТС] #14
MrGluck, ваш код - перестановки, мне нужны размещения. Извините, тему неправильно назвал.
0
Убежденный
Системный программист
Эксперт С++
15637 / 7147 / 1131
Регистрация: 02.05.2013
Сообщений: 11,586
Записей в блоге: 1
Завершенные тесты: 1
17.10.2013, 23:48 #15
Цитата Сообщение от SDmaN Посмотреть сообщение
Нужно вывести все возможные комбинации перестановок этих символов по n.
А, извиняюсь, неправильно прочитал условие темы.
Исправленный вариант:

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
56
57
58
59
60
61
62
63
64
65
66
67
#include <string.h>
#include <iostream>
 
 
 
namespace
{
 
 
 
void show_state(char const *pCharset, size_t const *pState, size_t Count)
{
    for (size_t i = 0; i < Count; ++i)
    {
        std::cout << pCharset[pState[i]];
    }
 
    std::cout << std::endl;
}
 
 
 
bool increment_state(size_t *pState, size_t CharsetSize, size_t Count)
{
    for (size_t i = 0; i < Count; ++i)
    {
        if (++pState[i] < CharsetSize)
        {
            return true;
        }
 
        pState[i] = 0;
    }
 
    return false;
}
 
 
 
} // namespace
 
 
 
int main()
{
    // ---------------------------
    //
    // Входные данные.
 
    char const *pCharset = "AB";
    size_t const Count   = 3;
 
    // ----------------------------
 
    size_t const CharsetSize = strlen(pCharset);
    size_t *pState = new size_t[Count];
    memset(pState, 0, Count * sizeof (size_t));
 
    do
    {
        show_state(pCharset, pState, Count);
    } while (false != increment_state(pState, CharsetSize, Count));
 
    delete [] pState;
 
    return 0;
}
Вывод:
AAA
BAA
ABA
BBA
AAB
BAB
ABB
BBB
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.10.2013, 23:48
Привет! Вот еще темы с ответами:

Сдвиг перестановки. - C++
Думал алгоритм решения таков : находим минимальный элемент ставим его на первое место и сдвигаем последовательность. Но такое решение...

Инверсии и перестановки - C++
Ребят, помогите пожалуйста, сделать 2 задачки, буду очень вам признателен! Заранее огромное спасибо. 1.Дана перестановка. Наименьшее...

Перестановки с next_permutation - C++
Есть входные данные 9-12 цифр надо из них создать все возможные перестановки и отправить их в вектор. Задумка do { ...

Двойные перестановки - C++
Здравствуйте программисты.Нужна ваша помощь. Помогите написать программу простенькую, на C++ : двойные перестановки n1*m1 + n2*m2 Буду...


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

Или воспользуйтесь поиском по форуму:
15
Yandex
Объявления
17.10.2013, 23:48
Ответ Создать тему
Опции темы

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