Question

CS 400 Assignment 5
Recursive/Backtracking: Generating Permutations

WRITE CODE IN C++ PROGRAMMING LANGUAGE WITH COMMENTS INCLUDED

Description: 
Mimic the code for N-queen problem (https://introcs.cs.princeton.edu/java/23recursion/Queens.java.html),
develop a program that generates all permutations for the set {1, 2, 3, 4, 5}.
The output should contain all 5! = 120 permutations. 

Output Sample: 
P#1: 1 2 3 4 5 
P#2: 1 2 3 5 4
P#3: 1 2 4 3 5
...
P#120: 5 4 3 2 1

Hint:
- Thoroughly study the N-queen problem first. 
- The code for N-queen is very close to the code generating permutations, just some helper functions away. 
- Keep the structure of the enumerate() function. You may change the function head to take in the array size. 
- Implement printPermutation() function and use it to replace printQueens().
- Implement isConsistent() function for permutation check. This check should be easier than N-queen consistent check. 

File_name: 
- permutation.cpp

Grading: 
- compilable and meaningful attemps: 20 points. 
- structure of enumerate(): 30 points
- helper functions: 40 points.
- comments, file names and indentation: 10 points. 

Answer 1

#include <iostream>

using namespace std;

void printPermutation(int q[], int n) {
        for(int i=0; i<n; i++) {
                cout << q[i] << " ";
        }
        cout << endl;
}

bool isValid(int q[], int k, int n) {
        int counts[n+1];
        for(int i=0; i<=n; i++) {
                counts[i] = 0;
        }
        for(int i=0; i<k; i++) {
                if(counts[q[i]] > 0) {
                        return false;
                }
                counts[q[i]] += 1;
        }
        return true;
}

void enumerate(int q[], int n, int k) {
        if (k == n) printPermutation(q, n);
        else {
            for (int i = 1; i <= n; i++) {
                q[k] = i;
                if(isValid(q, k+1, n)) {
                        enumerate(q, n, k+1);
                }
            }
        }
}  

int main() {
        int n;
        cout << "Enter n: ";
        cin >> n;

        int data[n];
        enumerate(data, n, 0);
}

**************************************************

Thanks for your question. We try our best to help you with detailed answers, But in any case, if you need any modification or have a query/issue with respect to above answer, Please ask that in the comment section. We will surely try to address your query ASAP and resolve the issue.

Please consider providing a thumbs up to this question if it helps you. by Doing that, You will help other students, who are facing similar issue.