Generate All Permutations of Array in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Permutations for Small Array

What is the output of the following C++ code that generates all permutations of the array [1, 2]?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> arr = {1, 2};
    do {
        for (int x : arr) std::cout << x << ' ';
        std::cout << '\n';
    } while (std::next_permutation(arr.begin(), arr.end()));
    return 0;
}

A 1 2 \n

B 1 2 \n2 1 \n

C 2 1 \n1 2 \n

D 2 1 \n

💡 Hint

Remember that std::next_permutation generates permutations in lexicographical order starting from the current arrangement.

The array starts as [1, 2], which is the first permutation. next_permutation generates the next lexicographical permutation, which is [2, 1]. After that, it returns false and stops.

❓ Predict Output

intermediate

Number of Permutations for Array of Size 3

How many permutations will be printed by the following code for the array [1, 2, 3]?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> arr = {1, 2, 3};
    int count = 0;
    do {
        count++;
    } while (std::next_permutation(arr.begin(), arr.end()));
    std::cout << count << '\n';
    return 0;
}

A 6

B 1

C 9

D 3

💡 Hint

The number of permutations of n distinct elements is n factorial (n!).

For 3 elements, the number of permutations is 3! = 3 × 2 × 1 = 6.

🔧 Debug

advanced

Why Does This Permutation Code Fail to Print All Permutations?

Consider this code snippet intended to print all permutations of [1, 2, 3]. Why does it not print all permutations?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> arr = {1, 2, 3};
    while (std::next_permutation(arr.begin(), arr.end())) {
        for (int x : arr) std::cout << x << ' ';
        std::cout << '\n';
    }
    return 0;
}

A It prints permutations in reverse order, which is incorrect.

B It prints duplicates because next_permutation is called twice per loop.

C It misses the first permutation because it does not print before calling next_permutation.

D It causes an infinite loop because the condition never becomes false.

💡 Hint

Think about what the initial arrangement is and when printing happens.

The code only prints after calling next_permutation, so the initial arrangement [1, 2, 3] is never printed. To print all permutations, print before calling next_permutation or use a do-while loop.

🧠 Conceptual

advanced

Understanding Permutation Generation Algorithm

Which of the following best describes how std::next_permutation generates the next permutation?

A It sorts the array in ascending order every time to generate the next permutation.

B It swaps the first and last elements of the array to generate the next permutation.

C It randomly shuffles the array to produce a new permutation each time.

D It finds the rightmost element that is smaller than its next element, swaps it with the smallest element larger than it to the right, then reverses the suffix after the original position.

💡 Hint

Think about how lexicographical order is maintained when generating permutations.

std::next_permutation works by finding the longest non-increasing suffix, swapping the pivot with the next larger element, then reversing the suffix to get the next lexicographically greater permutation.

🚀 Application

expert

Permutations with Duplicate Elements Count

Given the array [1, 2, 2], how many unique permutations will be generated by std::next_permutation if the array is sorted initially?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> arr = {1, 2, 2};
    int count = 0;
    do {
        count++;
    } while (std::next_permutation(arr.begin(), arr.end()));
    std::cout << count << '\n';
    return 0;
}

A 3

B 6

C 4

D 2

💡 Hint

Consider the formula for permutations of multiset: n! divided by factorials of duplicates.

The array has 3 elements with one duplicate '2'. Number of unique permutations = 3! / 2! = 6 / 2 = 3.

Practice

1. What does the process of generating all permutations of an array mean?

easy

A. Listing all possible orders of the array elements

B. Sorting the array in ascending order

C. Finding the maximum element in the array

D. Removing duplicate elements from the array

Solution

1. Step 1: Understand permutations

   Permutations are all possible ways to arrange elements in order.

2. Step 2: Apply to array elements

   Generating all permutations means listing every possible order of the array elements.

3. Final Answer:

   Listing all possible orders of the array elements -> Option A

4. Quick Check:

   Permutations = all orders [OK]

Hint: Permutations = all possible orders of elements [OK]

Common Mistakes:

• Confusing permutations with sorting
• Thinking permutations remove duplicates
• Assuming permutations find max or min

2. Which of the following C++ function signatures is correct for a recursive function generating all permutations of an integer array arr with size n</> and current index start?

easy

A. void permute(int arr[], int start, int n)

B. int permute(int arr[], int n, int start)

C. void permute(int arr[], int n)

D. int permute(int arr[], int start)

Solution

1. Step 1: Check parameter order and types

   The function needs the array, current index (start), and total size (n) to generate permutations recursively.

2. Step 2: Validate return type and parameters

   It should return void (no value) and have parameters (int arr[], int start, int n) in that order.

3. Final Answer:

   void permute(int arr[], int start, int n) -> Option A

4. Quick Check:

   Correct signature = void permute(arr, start, n) [OK]

Hint: Recursive permute needs array, start index, and size [OK]

Common Mistakes:

• Wrong parameter order
• Incorrect return type
• Missing current index parameter

3. What will be the output of the following C++ code snippet?

void permute(int arr[], int start, int n) {
  if (start == n) {
    for (int i = 0; i < n; i++) std::cout << arr[i] << ' ';
    std::cout << '\n';
    return;
  }
  for (int i = start; i < n; i++) {
    std::swap(arr[start], arr[i]);
    permute(arr, start + 1, n);
    std::swap(arr[start], arr[i]);
  }
}

int main() {
  int arr[] = {1, 2};
  permute(arr, 0, 2);
  return 0;
}

medium

A. 2 1 \n 1 2 \n

B. 1 2 \n 2 1 \n

C. 1 2 \n 1 2 \n

D. No output

Solution

1. Step 1: Trace first call with arr = {1, 2}

   Start = 0, n = 2. Swap arr[0] with arr[0] (no change), call permute with start=1.

2. Step 2: Trace second call with start=1

   Swap arr[1] with arr[1] (no change), call permute with start=2 which prints "1 2".

3. Step 3: Backtrack and swap arr[0] with arr[1]

   Array becomes {2, 1}, call permute with start=1 again.

4. Step 4: At start=1 again, swap arr[1] with arr[1], call permute with start=2 prints "2 1".

5. Final Answer:

   1 2 \n 2 1 \n -> Option B

6. Quick Check:

   All permutations of {1,2} printed [OK]

Hint: Swap and backtrack to print all orders [OK]

Common Mistakes:

• Not swapping back after recursion
• Printing before base case
• Incorrect loop range

4. Identify the error in the following code snippet for generating permutations of array arr of size n:

void permute(int arr[], int start, int n) {
  if (start == n) {
    for (int i = 0; i < n; i++) std::cout << arr[i] << ' ';
    std::cout << '\n';
    return;
  }
  for (int i = 0; i < n; i++) {
    std::swap(arr[start], arr[i]);
    permute(arr, start + 1, n);
    std::swap(arr[start], arr[i]);
  }
}

medium

A. Function should return int, not void

B. Base case condition should be start == n - 1

C. Swap should be done only once outside the loop

D. Loop should start from i = start, not 0

Solution

1. Step 1: Analyze the for loop range

   The loop swaps arr[start] with arr[i]. If i starts at 0 always, it swaps elements already fixed in previous recursion steps.

2. Step 2: Correct loop start index

   Loop should start from i = start to avoid repeating swaps and ensure correct permutations.

3. Final Answer:

   Loop should start from i = start, not 0 -> Option D

4. Quick Check:

   Loop from start to n fixes correct elements [OK]

Hint: Start loop from current index to avoid duplicate swaps [OK]

Common Mistakes:

• Starting loop from 0 causes repeated permutations
• Changing base case incorrectly
• Misplacing swap calls

5. Given an array arr = {1, 2, 2}, how many unique permutations will a correct C++ program generate if it avoids duplicates?

hard

A. 2

B. 6

C. 3

D. 4

Solution

1. Step 1: Calculate total permutations without duplicates

   For 3 elements with two 2's, total permutations = 3! / 2! = 3.

2. Step 2: List unique permutations

   They are {1,2,2}, {2,1,2}, {2,2,1} -- total 3 unique permutations.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   3! / 2! = 3 unique permutations [OK]

Hint: Divide factorial by duplicates factorial for unique count [OK]

Common Mistakes:

• Counting duplicates as unique permutations
• Using 3! = 6 without division
• Ignoring repeated elements