All Permutations of an Array

Spread the love

The goal at hand is to publish every conceivable permutation of an array arr[].

Table of Contents

For instance:

Input: arr[] = {1, 2, 3}
Output: {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 2, 1}, {3, 1, 2}
Explanation: There are 6 possible permutations


Input: arr[] = {1, 3}
Output: {1, 3}, {3, 1}
Explanation: There are 2 possible permutations

C++

#include <bits/stdc++.h>
using namespace std;

// Function to find the possible permutations. 
// Initial value of idx is 0.
void permutations(vector<vector<int>>& res, vector<int> arr, int idx) {
  
    // Base case: if idx reaches the size of the array, 
     // add the permutation to the result
    if (idx == arr.size()) {
        res.push_back(arr);
        return;
    }

    // Permutations made by swapping each element
    // starting from index `idx`
    for (int i = idx; i < arr.size(); i++) {
      
        // Swapping
        swap(arr[idx], arr[i]);

        // Recursive call to create permutations 
        // for the next element
        permutations(res, arr, idx + 1);

        // Backtracking
        swap(arr[idx], arr[i]);
    }
}

// Function to get the permutations
vector<vector<int>> permute(vector<int>& arr) {
  
    // Declaring result variable
    vector<vector<int>> res;

    // Calling permutations with idx starting at 0
    permutations(res, arr, 0);
    return res;
}

// Driver Code
int main() {
    vector<int> arr = { 1, 2, 3 };
    vector<vector<int>> res = permute(arr);

    // Printing result
    for (auto x : res) {
        for (auto y : x) {
            cout << y << " ";
        }
        cout << endl;
    }

    return 0;
}

C

#include <stdio.h>

// Function to swap elements
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Function to find the possible permutations. 
// Initial value of idx is 0.
void permutations(int res[][100], int* arr, int idx, int size, int* resSize) {
  
    // Base case: if idx reaches the size of the array,
    // add the permutation to the result
    if (idx == size) {
        for (int i = 0; i < size; i++) {
            res[*resSize][i] = arr[i];
        }
        (*resSize)++;
        return;
    }

    // Permutations made by swapping each element
    // starting from index `idx`
    for (int i = idx; i < size; i++) {
      
        // Swapping
        swap(&arr[idx], &arr[i]);

        // Recursive call to create permutations
        permutations(res, arr, idx + 1, size, resSize);

        // Backtracking
        swap(&arr[idx], &arr[i]);
    }
}

// Function to get the permutations
void permute(int* arr, int size, int res[][100], int* resSize) {
    permutations(res, arr, 0, size, resSize);
}

// Driver code
int main() {
    int arr[] = { 1, 2, 3 };
    int res[100][100]; // 2D array to store permutations
    int resSize = 0;
    
    permute(arr, 3, res, &resSize);

    // Printing result
    for (int i = 0; i < resSize; i++) {
        for (int j = 0; j < 3; j++) {
            printf("%d ", res[i][j]);
        }
        printf("\n");
    }

    return 0;
}

Java

import java.util.ArrayList;
import java.util.List;

class GfG {

    // Function to find the possible permutations.
    static void permutations(List<List<Integer>> res, 
                                         int[] arr, int idx) {
      
        // Base case: if idx reaches the size of the array,
        // add the permutation to the result
        if (idx == arr.length) {
            res.add(convertArrayToList(arr));
            return;
        }

        // Permutations made by swapping each element
        // starting from index `idx`
        for (int i = idx; i < arr.length; i++) {
            // Swapping
            swap(arr, idx, i);

            // Recursive call to create permutations
            // for the next element
            permutations(res, arr, idx + 1);

            // Backtracking
            swap(arr, idx, i);
        }
    }

    // Function to get the permutations
    static List<List<Integer>> permute(int[] arr) {
      
        // Declaring result variable
        List<List<Integer>> res = new ArrayList<>();

        // Calling permutations with idx starting at 0
        permutations(res, arr, 0);
        return res;
    }

    // Helper method to swap elements in the array
    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // Helper method to convert array to list
    static List<Integer> convertArrayToList(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int num : arr) {
            list.add(num);
        }
        return list;
    }

    public static void main(String[] args) {
        int[] arr = { 1, 2, 3 };
        List<List<Integer>> res = permute(arr);

        for (List<Integer> x : res) {
            for (int y : x) {
                System.out.print(y + " ");
            }
            System.out.println();
        }
    }
}

Python

# Function to swap elements in the array
def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

# Function to find the possible permutations. 
# Initial value of idx is 0.
def permutations(res, arr, idx):
  
    # Base case: if idx reaches the size of the array,
    # add the permutation to the result
    if idx == len(arr):
        res.append(arr[:])
        return

    # Permutations made by swapping each element
    for i in range(idx, len(arr)):
        swap(arr, idx, i)
        permutations(res, arr, idx + 1)
        swap(arr, idx, i)  # Backtracking

# Function to get the permutations
def permute(arr):
    res = []
    permutations(res, arr, 0)
    return res

# Driver code
arr = [1, 2, 3]
res = permute(arr)

# Printing result
for perm in res:
    print(" ".join(map(str, perm)))

C#

using System;
using System.Collections.Generic;

public class GfG {

    // Function to swap elements in the array
    private static void Swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // Function to find the possible permutations.
    // Initial value of idx is 0.
    private static void Permutations(List<List<int>> res, int[] arr, int idx) {
        if (idx == arr.Length) {
            res.Add(new List<int>(arr));
            return;
        }

        for (int i = idx; i < arr.Length; i++) {
            Swap(arr, idx, i);
            Permutations(res, arr, idx + 1);
            Swap(arr, idx, i); // Backtracking
        }
    }

    // Function to get the permutations
    public static List<List<int>> Permute(int[] arr) {
        List<List<int>> res = new List<List<int>>();
        Permutations(res, arr, 0);
        return res;
    }

    // Driver code
    public static void Main() {
        int[] arr = {1, 2, 3};
        List<List<int>> res = Permute(arr);

        // Printing result
        foreach (List<int> perm in res) {
            Console.WriteLine(string.Join(" ", perm));
        }
    }
}

JavaScript

// Function to swap elements in the array
function swap(arr, i, j) {
    [arr[i], arr[j]] = [arr[j], arr[i]];
}

// Function to find the possible permutations.
// Initial value of idx is 0.
function permutations(res, arr, idx) {
    if (idx === arr.length) {
        res.push([...arr]);
        return;
    }

    for (let i = idx; i < arr.length; i++) {
        swap(arr, idx, i);
        permutations(res, arr, idx + 1);
        swap(arr, idx, i); // Backtracking
    }
}

// Function to get the permutations
function permute(arr) {
    const res = [];
    permutations(res, arr, 0);
    return res;
}

// Driver code
const arr = [1, 2, 3];
const res = permute(arr);

// Printing result
res.forEach(perm => {
    console.log(perm.join(' '));
});

Output