Clasa a XI-a · Metoda backtrackingRead in English

Permutări cu vecini de parități diferite în C++

În engleză: Permutations with neighbours of alternating parity

ExponențialăC++1761 de linii1 exemplu

Ideea

Afișează permutările mulțimii {1, ..., n} în care oricare două elemente vecine au parități diferite (unul par, celălalt impar). Față de generarea permutărilor apare o condiție de continuare în plus: valoarea de pe poziția k trebuie să aibă altă paritate decât x[k - 1]. Verificând-o imediat, tăiem devreme ramurile care nu pot duce la soluții.

Descrierea în engleză

Prints the permutations of the set {1, ..., n} in which any two neighbouring elements have different parities (one even, the other odd). Compared with generating permutations there is one extra continuation condition: the value at position k must have a different parity from x[k - 1]. Checking it right away prunes early the branches that cannot lead to solutions.

Complexitate
O(n! · n) în cel mai rău caz, practic mult mai puțin
Clasa
Clasa a XI-a (Grade 11)

Exemple

Exemplul 1

Intrare

4

Ieșire așteptată

1 2 3 4
1 4 3 2
2 1 4 3
2 3 4 1
3 2 1 4
3 4 1 2
4 1 2 3
4 3 2 1

Codul C++

Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.

permutari-paritati-alternante.cpp
/*
 * Titlu: Permutări cu vecini de parități diferite
 * Clasa: 11
 * Capitol: Metoda backtracking
 * Descriere: Afișează permutările mulțimii {1, ..., n} în care oricare două elemente
 *            vecine au parități diferite (unul par, celălalt impar). Față de generarea
 *            permutărilor apare o condiție de continuare în plus: valoarea de pe poziția k
 *            trebuie să aibă altă paritate decât x[k - 1]. Verificând-o imediat, tăiem
 *            devreme ramurile care nu pot duce la soluții.
 * Complexitate: O(n! · n) în cel mai rău caz, practic mult mai puțin
 *
 * Exemplu
 * Intrare: 4
 * Ieșire:
 * 1 2 3 4
 * 1 4 3 2
 * 2 1 4 3
 * 2 3 4 1
 * 3 2 1 4
 * 3 4 1 2
 * 4 1 2 3
 * 4 3 2 1
 */
#include <iostream>
using namespace std;

int n, x[20];
bool folosit[20];

void back(int k)
{
    for (int v = 1; v <= n; v++)
    {
        if (!folosit[v] && (k == 1 || v % 2 != x[k - 1] % 2))
        {
            x[k] = v;
            folosit[v] = true;
            if (k == n)
            {
                for (int i = 1; i <= n; i++)
                {
                    cout << x[i] << ' ';
                }
                cout << '\n';
            }
            else
            {
                back(k + 1);
            }
            folosit[v] = false;
        }
    }
}

int main()
{
    cin >> n;
    back(1);
    return 0;
}

Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.