Генерация перестановок чисел от 1 до N

@Timurkanaz · Регистрация: 19.03.2019

Author24 — интернет-сервис помощи студентам

Данная программа выдает неверные данные при N=5 и более.Сдается мне что есть проблемы в сортировке. Работает по следующему алгоритму:

1.Необходимо просмотреть текущую перестановку справа налево и при этом следить за тем, чтобы каждый следующий элемент перестановки был не более чем предыдущий . Как только данное соотношение будет нарушено необходимо остановиться и отметить текущее число.

2.Снова просмотреть пройденный путь справа налево пока не дойдем до первого числа, которое больше чем отмеченное на предыдущем шаге.

3.Поменять местами два полученных элемента.

4.Теперь в части массива, которая размещена справа от элемента,найденного в первом пункте, надо отсортировать все числа в порядке возрастания. То есть необходимо эту часть просто перевернуть.

C++

#include <iostream>
 
using namespace std;
 
int main(){
 
 
    int n;
    setlocale(LC_ALL, "Russian");
 
 
    cout<<"Введите порядок числа: ";
    cin>>n;
    int a[n];
    int k;//флажок
    int o=1;//для нумерации перестановке в выводе
    
    
    for(int i=0;i<n;i++){
        a[i]=i+1;
    }
    
    
    cout<<"№"<<" "<<o<<" :";
    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }
    
    
        do  {
                int j=-1;// индекс для фиксации искомого номера элемента из пункта 1.
            k=0;
            for(int i=n-1;i>0;i--){
            
            if(a[i]>=a[i-1]){
                k=1;
                 j=i-1;
                break;
            } //зафиксировали
        
        }
            
        
        
            
            if(j!=-1){
            
            for(int i=n-1;i>=0;i--){
            if(a[i]>a[j]){
            
            
                int temp=0;
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
                cout<<"\n";
                break;
    
    } //Нашли первый элемент,больший элемента из п.1 и поменяли местами
        
}
        
                
                int m=1;
                for(int i=j+1;i<(n-1);i++){
 
                swap(a[i],a[n-m]);
                m++;
                    } //реверсируем часть массива,которая справа от элемента из п.1
            
                o++;
                cout<<"№"<<" "<<o<<" :";
                for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
                
                    } //Вывели перестановку
            }
            
 
                    
            
 
                                } while(k!=0);
                
        return 0;   }

@nalbe666 · 08.12.2019, 21:59

C

#include <stdio.h>
#include <stdbool.h>
 
void iter_swap(int* l, int* r) {
    if (*l != *r) {
        *l ^= *r; *r ^= *l; *l ^= *r;
    }
}
 
void reverse(int* begin, int* end) {
    if (begin < end - 1) {
        iter_swap(begin, end - 1);
        reverse(++begin, --end);
    }
}
 
bool next_permutation(int* begin, int* end) {
    int* next = end;
    if (begin == end || begin == --next) {
        return false;
    }
 
    while (true) {
        int* next1 = next;
        if (*--next < *next1) {
            int* mid = end;
            do {
                --mid;
            } while (*next >= *mid);
 
            iter_swap(next, mid);
            reverse(next1, end);
            return true;
        }
 
        if (next == begin) {
            reverse(begin, end);
            return false;
        }
    }
}
 
bool prev_permutation(int* begin, int* end) {
    int* next = end;
    if (begin == end || begin == --next) {
        return false;
    }
 
    while (true) {
        int* next1 = next;
        if (*next1 < *--next) {
            int* mid = end;
            do {
                --mid;
            } while (*mid >= *next);
 
            iter_swap(next, mid);
            reverse(next1, end);
            return true;
        }
 
        if (next == begin) {
            reverse(begin, end);
            return false;
        }
    }
}
 
int main() {
    int seq[] = { 1,2,3,4 };
 
    do {
        printf("%d %d %d %d\n", seq[0], seq[1], seq[2], seq[3]);
    } while (next_permutation(seq, seq + 4));
 
    return 0;
}

	08.12.2019, 21:59