Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.60/15: Рейтинг темы: голосов - 15, средняя оценка - 4.60
2 / 2 / 1
Регистрация: 18.03.2014
Сообщений: 147

Перечисление перестановок порядка n в лексикографическом порядке

30.03.2015, 09:23. Показов 2951. Ответов 1
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
1. Выбор начальной перестановки π = (π1, π2, …, πn) = (1, 2, …, n).

Например, π = (2, 6, 5, 8, 7, 4, 3, 1).

2. Просмотр перестановки π справа налево.

Поиск самой правой позиции i такой, что πi< πi+1. π = (2, 6, 5, 8, 7, 4, 3, 1).

Если это невозможно, то конец перебора (выдана последняя наибольшая перестановка).

3. Поиск πj – наименьшего (min)элемента справа от πi такого, что πj> πi.

4. Транспозиция (обмен) элементов πj и πi. В результате πi+1 > πi+2 > …> πn.

После транспозиции элементов πj и πi получается -(2, 6, 7, 8, 5, 4, 3, 1),

5.Начиная с позиции i+1 изменение элементов перестановки на πn, πn-1,…,
πi+1. после изменения мест конечных элементов приходим к следующей в
лексикографическом порядке перестановке (2, 6, 7, 1, 3, 4, 5, 8).
Переход к 2.
Если перечислять перестановки порядка 5 с самого начала, то последовательно
получим (1, 2, 3, 4, 5), (1, 2, 3, 5, 4), (1, 2, 4, 3, 5), (1, 2, 4, 5, 3) и т. д.

Но к п.5 сделал быструю сортировку и дальше - "(1, 2, 3, 4, 5), (1, 2, 3, 5, 4), (1, 2, 4, 3, 5), (1, 2, 4, 5, 3)" - не могу понять как это реализовывается, просто у меня код на этом зацикливается, как мне сделать данный пункт?

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <valarray>
#include <vector>
 
using namespace std;
 
void quickSort(int l, int r, int array[10])
{
    int x = array[l + (r - l) / 2];
    //запись эквивалентна (l+r)/2, 
    //но не вызввает переполнения на больших данных
    int i = l;
    int j = r;
    //код в while обычно выносят в процедуру particle
    while (i <= j)
    {
        while (array[i] > x) i++;
        while (array[j] < x) j--;
        if (i <= j)
        {
            swap(array[i], array[j]);
            i++;
            j--;
        }
    }
    if (i<r)
        quickSort(i, r, array);
 
    if (l<j)
        quickSort(l, j, array);
}
void SwapMass(int Value1, int Value2, int Mass[10], int count, int count2)
{
    int DitarminateValue;
    DitarminateValue = Value1;
    Value1 = Value2;
    Value2 = DitarminateValue;
    Mass[count] = Value1;
    Mass[count2] = Value2;
}
 
 
int main()
{
    int Value[10] = { 1, 7, 2, 5, 8, 6, 4, 3, 1 };
    int i = 9;
    int MinimalElement;
    vector<int> Vec;
    for (int count = i; count >= 0; count--) // пока не пройдем все числа
    {
        bool metka = false;
        if (Value[count] < Value[count + 1]) // 5 < 8?  (1 итерация) 
        {
            Vec.clear();
            for (int j = i; j != count; j--)
            {
                Vec.push_back(Value[j]); //заносим (5, 8, 6, 4, 3, 1)
            }
            if (Vec.size() < 2)
            {
                SwapMass(Value[count], Value[count + 1], Value, count, count + 1);
                count = i;
            }
            else
            {
                sort(Vec.begin(), Vec.end()); // 1, 3 , 4 , 5 , 6 , 8
                size_t EndVectorElement = (Vec.size() - 1); // 8
                int MinimalElement = min(Vec[EndVectorElement], Vec[EndVectorElement - 1]); //min(6,8) = 6
                for (int k = i; k != count; k--)
                {
                    if (Value[k] == MinimalElement) // ищем индекс в котором находим нашу 6-ку
                    {
                        SwapMass(Value[count], Value[k], Value, count, k); // меняем ее местами с 5 -ой
                        quickSort(count + 1, 9, Value); // и после 6 все сотрируем последовательно
                        //быструю сортировку позаимстовал у автора, ссылка на быструю сортировку
                        //http://cybern.ru/qsort-cpp.html
                        metka = true;
                    }
                }
                if (metka == true)
                {
                    count = i;
                }
            }
        }
    }
    for (int count = 0; count != 10; count++)
    {
        cout << Value[count] << endl;
    }
    getchar();
}
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
30.03.2015, 09:23
Ответы с готовыми решениями:

Алгоритм генерации перестановок в лексикографическом порядке
У меня проблема. Нужно перебрать все лексикографически следующие перестановки. Вот мой код. Одна перестановка делается, а дальше я не знаю,...

Число перестановок в лексикографическом порядке
Здравствуйте! Как решать такие задачи, ниже? Очень прошу помощи. Все перестановки 7 чисел (1;2;3;4;5;6;7) упорядочены в...

Перечисление перестановок с повторениями
Помогите исправить ошибку. У меня проблема в том, что повторяются комбинации несколько раз. Вот сама программа: Sub ыыфа() Dim A(10,...

1
2 / 2 / 1
Регистрация: 18.03.2014
Сообщений: 147
02.04.2015, 13:35  [ТС]
что, неужели никто не знает? это же вроде как просто, но я упустил какую-то деталь при последнем обмене чисел в пункте 5?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
02.04.2015, 13:35
Помогаю со студенческими работами здесь

По перестановке определить его номер в лексикографическом перечислении всех перестановок множества
По перестановке определить его номер в лексикографическом перечислении всех перестановок множества {1,2,…,n}. Формат входных данных: ...

Привести в лексикографическом порядке (в порядке возрастания) все r-размещения с повторениями из элементов множества {1,2, .. n}
Нужно составить программу с указанными входными данными и результатами. Задано натуральное число n, которое имеет такое ограничение...

Отсортировать в лексикографическом порядке
Здравствуйте! Возникли сложности с задачей, сам до конца не могу разобраться что не так, программа компилируется, но на этапе ввода слов...

Сортировка в лексикографическом порядке
Здравствуйте. Помогите с программой. 1. С использованием структур написать программу, в которой вводится список слов и их определений....

Сравнение массивов в лексикографическом порядке
Pomogite kto 4em mozhet. Sam pytalsja, polu4ilsja - bred! Вводятся 2 массива одинакового размера. Какой из них больше, если...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Новые блоги и статьи
Ритм жизни
kumehtar 27.02.2026
Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .
SDL3 для Web (WebAssembly): Сборка SDL3 и Box2D из исходников с помощью CMake и Emscripten
8Observer8 27.02.2026
Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru