c语言 permutation

Of course! In C, generating permutations is a classic problem that is elegantly solved using recursion and backtracking.

Let's break it down.

What is a Permutation?

A permutation is an arrangement of all the elements of a set in a specific order. For a set with n distinct elements, there are n! (n factorial) permutations.

Example: For the set {1, 2, 3}, the permutations are: {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}

The Core Idea: Backtracking

The most intuitive way to generate permutations is to think of it like building a tree.

1. Choose: Pick an element that hasn't been used yet to be the first element of your permutation.
2. Explore: Recursively generate all permutations of the remaining elements.
3. Un-choose (Backtrack): After the recursive call returns, "un-choose" the element you picked. This means you put it back into the pool of available elements so it can be used in a different position later.

This "choose, explore, un-choose" pattern is the essence of backtracking.

Implementation in C

We need a way to keep track of which elements have been used. A simple boolean array is perfect for this. We'll also need a temporary array to build the current permutation and a function to print it once it's complete.

Here is a complete, well-commented C program that generates all permutations of a set of integers.

Code

#include <stdio.h>
#include <stdbool.h> // For the 'bool' type
// A function to swap two integers
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
// Recursive function to generate permutations
// arr[]:      The array of elements to permute
// size:       The total number of elements in the array
// current:    The current position we are filling in the permutation
// used[]:     A boolean array to track which elements have been used
// permutation:An array to store the current permutation being built
void generatePermutations(int arr[], int size, int current, bool used[], int permutation[]) {
    // Base Case: If the current position is equal to the size,
    // it means we have filled the permutation array completely.
    // We have found a valid permutation, so print it.
    if (current == size) {
        for (int i = 0; i < size; i++) {
            printf("%d ", permutation[i]);
        }
        printf("\n");
        return;
    }
    // Recursive Step:
    // Iterate through all elements of the original array
    for (int i = 0; i < size; i++) {
        // If the element at index 'i' has not been used yet...
        if (!used[i]) {
            // 1. CHOOSE:
            //    Mark it as used.
            used[i] = true;
            //    Place it in the current position of our permutation.
            permutation[current] = arr[i];
            // 2. EXPLORE:
            //    Recursively call the function to fill the next position.
            generatePermutations(arr, size, current + 1, used, permutation);
            // 3. UN-CHOOSE (BACKTRACK):
            //    This is the most crucial step. After the recursive call returns,
            //    we need to "undo" our choice so that this element can be used
            //    in other positions in future iterations of the loop.
            used[i] = false;
        }
    }
}
int main() {
    int arr[] = {1, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    // Arrays to help with the generation process
    bool used[n];      // To keep track of used elements, initialized to false
    int permutation[n]; // To store the current permutation
    // Initialize the 'used' array
    for (int i = 0; i < n; i++) {
        used[i] = false;
    }
    printf("All permutations of {1, 2, 3} are:\n");
    generatePermutations(arr, n, 0, used, permutation);
    return 0;
}

How to Compile and Run

1. Save the code as a file, e.g., permutations.c.
2. Open a terminal or command prompt.
3. Compile the code using a C compiler like GCC:

   gcc permutations.c -o permutations

4. Run the executable:

   ./permutations

Expected Output

All permutations of {1, 2, 3} are:
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1 

Alternative Method: Heap's Algorithm (In-place)

Heap's algorithm is another famous method for generating permutations. Its main advantage is that it generates the permutations in-place, meaning it doesn't require extra arrays for used flags or permutation. It's generally more efficient in terms of memory.

It works by swapping elements in the original array. The logic is slightly different but equally elegant.

Code for Heap's Algorithm

#include <stdio.h>
// A function to swap two integers
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
// Heap's Algorithm for generating permutations (in-place)
// arr[]: The array to permute
// n:     The size of the array
// k:     The size of the subset to generate permutations for
void heapPermute(int arr[], int n, int k) {
    // Base case: if k is 1, we have a complete permutation, so print it.
    if (k == 1) {
        for (int i = 0; i < n; i++) {
            printf("%d ", arr[i]);
        }
        printf("\n");
    } else {
        // Generate permutations for k by swapping the k-th element
        // with every element from 0 to k-1.
        for (int i = 0; i < k; i++) {
            heapPermute(arr, n, k - 1);
            // If k is odd, swap the first and last elements
            if (k % 2 == 1) {
                swap(&arr[0], &arr[k - 1]);
            }
            // If k is even, swap the i-th and last elements
            else {
                swap(&arr[i], &arr[k - 1]);
            }
        }
    }
}
int main() {
    int arr[] = {1, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("All permutations of {1, 2, 3} using Heap's Algorithm:\n");
    // We start by permuting the whole array, so k = n
    heapPermute(arr, n, n);
    return 0;
}

Expected Output (Same as before)

All permutations of {1, 2, 3} using Heap's Algorithm:
1 2 3 
2 1 3 
3 1 2 
1 3 2 
2 3 1 
3 2 1 

(Note: The order of permutations might differ, but the set of permutations will be identical.)

Summary

For most programming interviews and learning purposes, the backtracking approach is the one you should be comfortable with, as it demonstrates a fundamental problem-solving technique.