Clasa a XI-a · Metoda backtrackingRead in English

Generarea aranjamentelor în C++

În engleză: Generating arrangements (k-permutations)

O(n)C++1763 de linii1 exemplu

Ideea

Afișează, în ordine lexicografică, toate aranjamentele de n elemente luate câte k: șiruri de k valori distincte din {1, ..., n}, în care ordinea contează. Este schema de la permutări, dar soluția se oprește la lungimea k. Numărul lor este A(n, k) = n! / (n - k)!.

Descrierea în engleză

Prints, in lexicographic order, all arrangements of n elements taken k at a time: sequences of k distinct values from {1, ..., n} where order matters. It is the permutation scheme, but the solution stops at length k. Their number is A(n, k) = n! / (n - k)!.

Complexitate
O(A(n, k) · k) timp, O(n) memorie
Clasa
Clasa a XI-a (Grade 11)

Exemple

Exemplul 1

Intrare

3 2

Ieșire așteptată

1 2
1 3
2 1
2 3
3 1
3 2

Codul C++

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

aranjamente.cpp
/*
 * Titlu: Generarea aranjamentelor
 * Clasa: 11
 * Capitol: Metoda backtracking
 * Descriere: Afișează, în ordine lexicografică, toate aranjamentele de n elemente luate
 *            câte k: șiruri de k valori distincte din {1, ..., n}, în care ordinea contează.
 *            Este schema de la permutări, dar soluția se oprește la lungimea k.
 *            Numărul lor este A(n, k) = n! / (n - k)!.
 * Complexitate: O(A(n, k) · k) timp, O(n) memorie
 *
 * Exemplu
 * Intrare: 3 2
 * Ieșire:
 * 1 2
 * 1 3
 * 2 1
 * 2 3
 * 3 1
 * 3 2
 */
#include <iostream>
using namespace std;

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

void afiseaza()
{
    for (int i = 1; i <= k; i++)
    {
        cout << x[i] << ' ';
    }
    cout << '\n';
}

void back(int poz)
{
    for (int v = 1; v <= n; v++)
    {
        if (!folosit[v])
        {
            x[poz] = v;
            folosit[v] = true;
            if (poz == k)
            {
                afiseaza();
            }
            else
            {
                back(poz + 1);
            }
            folosit[v] = false;
        }
    }
}

int main()
{
    cin >> n >> k;
    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.