Grade 11 · BacktrackingCitește în română

Generating arrangements (k-permutations)

Original: Generarea aranjamentelor

O(n)C++1763 lines1 example

The idea

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)!.

Original description (Romanian)

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)!.

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

Examples

Example 1

Input

3 2

Expected output

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

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

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;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.