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

Не могу найти ошибку в коде, генерирующего всевозможные перестановки - C++

Восстановить пароль Регистрация
 
FasterHarder
1 / 1 / 0
Регистрация: 28.04.2015
Сообщений: 55
18.04.2016, 08:58     Не могу найти ошибку в коде, генерирующего всевозможные перестановки #1
Всем привет!
Условие задачи: задано множество, состоящие из натуральных чисел от 1 до n с шагом 1. Например: {1, 2, 3, 4, 5}. Получить всевозможные перестановки заданного множества в лексикографическом порядке с использованием рекурсии.

C++ (Qt)
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
    using namespace std;
    void swap(int *pv, int pi, int pj);
    //--------------------------------------------------
    void printSet(int *pv, int pn)
    {
        for(int i = 0; i < pn; i++)
            cout << pv[i];
        cout << "\t";
    }
    //--------------------------------------------------
    void permute(int *pv, int pi, int pn)
    {
        if(pi == pn)
            printSet(pv, pn);
        else
        {
            for(int j = pi; j < pn; j++)
            {
                swap(pv, pi, j);
                permute(pv, pi + 1, pn);
                swap(pv, pi, j);
            }
        }
    }
    void swap(int *pv, int pi, int pj)
    {
        int tmp = pv[pi];
        pv[pi] = pv[pj];
        pv[pj] = tmp;
    }
    void main()
    {
        int *v = new int[5];
        for(int i = 0; i < 5; i++)
            v[i] = i + 1;
        permute(v, 0, 5);
        delete []v;
    }
После выполнения программа выдает всевозможные перестановки корректно, но кое-где сбивается лексикографический порядок.
Например, идет последовательность (из 5 элементов): 12345, 12354, 12435, 12453, 12543, 12534!! Последнее слагаемое должно идти раньше предыдущего. И таких нестыковок множество.

Подскажите, где проблема в коде, которая нарушает лексикографический порядок.
Буду признателен.

P.S. кстати из инета достаточно много ссылок по реализации данного алгоритма на данный форум, но:
1. Либо сделано итерационно, а не рекурсионно
2. Не соблюдается лексикографический порядок
3. Либо с использованием стандартной функции (типа next_permutation), а мне нужно с нуля этот велосипед сделать
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.04.2016, 08:58     Не могу найти ошибку в коде, генерирующего всевозможные перестановки
Посмотрите здесь:

Не могу найти ошибку в коде C++
Не могу найти ошибку в коде C++
C++ Не могу найти ошибку в коде :(
C++ Не могу найти ошибку в коде
Не могу найти ошибку в коде C++
Не могу найти ошибку в коде C++
C++ Не могу найти ошибку в коде
C++ Не могу найти ошибку в коде

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
RQdan
65 / 65 / 17
Регистрация: 26.10.2013
Сообщений: 198
18.04.2016, 11:20     Не могу найти ошибку в коде, генерирующего всевозможные перестановки #2
FasterHarder, это не ошибка, просто так организована работа цикла
Цитата Сообщение от FasterHarder Посмотреть сообщение
C++
1
2
3
4
5
6
for(int j = pi; j < pn; j++)
 {
 swap(pv, pi, j);
 permute(pv, pi + 1, pn);
 swap(pv, pi, j);
 }
Чтобы сделать так, как Вам необходимо, нужно не просто менять два элемента местами, а сдвигать все элементы в массиве от pi до j на единицу, причем элемент за идексом j переставляется на индекс pi.
Соответственно, после функции необходио возвращать все назад.

Это будет сложнее теперешней реализации - вопрос в том, стоит ли овчинка выделки.
Babysitter
 Аватар для Babysitter
78 / 103 / 34
Регистрация: 23.11.2015
Сообщений: 315
Завершенные тесты: 1
18.04.2016, 14:03     Не могу найти ошибку в коде, генерирующего всевозможные перестановки #3
в общем, просто позора пост. думал сейчас потренеруюсь - сяду напишу, а сходу не написалось, времени мало было. в итоге для правильного порядка пришлось set доставать, делать жутко медленные вставки в вектор и на каждой итерации выбрасывать на свалку предыдущий сет.

удалять этого монстра все равно жалко, так что выкину сюда.
как люди до auto писали обмен местами содержимого двух итераторов?
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 <algorithm>
#include <iostream>
#include <vector>
#include <set>
 
typedef std::vector<int> Seq;
typedef std::set< Seq > SeqVec;
 
template <class Forward>
void tswap(Forward x, Forward y)
{
    auto tmp = *x;
    *x = *y;
    *y = tmp;
}
 
template <class Random>
void permute(Random beg, Random end, SeqVec& out)
{
    if (end - beg == 1)
    {
        out.emplace(Seq{ *beg });
        return;
    }
    tswap(min_element(beg, end), beg);
    permute(beg + 1, end, out);
    SeqVec result;
    for (Seq s : out)
    {
        for (size_t i = 0; i <= s.size(); ++i)
        {
            Seq tmp = s;
            tmp.insert(tmp.begin() + i, *beg);
            result.emplace(tmp);
        }
    }
    out = result;
}
 
int main()
{
    Seq v{ 5, 4, 3, 2, 1 };
    SeqVec result;
    permute(v.begin(), v.end(), result);
    for (auto i : result)
    {
        for (auto j : i)
            std::cout << j;
        std::cout << "\n";
    }
    return 0;
}
Добавлено через 14 минут
а, ну да. если сет уже есть, то пузырек на восходящей рекурсии не нужен тем более.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <class Random>
void permute(Random beg, Random end, SeqVec& out)
{
    if (end - beg == 1)
    {
        out.emplace(Seq{ *beg });
        return;
    }
    permute(beg + 1, end, out);
    SeqVec result;
    for (Seq s : out)
    {
        for (size_t i = 0; i <= s.size(); ++i)
        {
            Seq tmp = s;
            tmp.insert(tmp.begin() + i, *beg);
            result.emplace(tmp);
        }
    }
    out = result;
}
Yandex
Объявления
18.04.2016, 14:03     Не могу найти ошибку в коде, генерирующего всевозможные перестановки
Ответ Создать тему
Опции темы

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