Given an array arr[] of integers having N elements and a non-weighted undirected graph having N nodes and M edges. The edges are represented as a list, the task is to count the number of permutations of the array, for which every node of the array, Vi [1 ≤ i ≤ N-1], there exists an edge between the nodes Vi and Vi+1 in the given graph.
Examples:
Input: N = 3, M = 2, arr = {1, 2, 3}, graph = {{3, 1}, {1, 2}}
Output: 2
Explanation: All possible permutations of the array are as follows:
- {1, 2, 3}: There is an edge between 1 and 2 in the graph but not between 2 and 3.
- {2, 1, 3}: There is an edge between (2, 1) and (1, 3) in the graph.
- {3, 1, 2}: There is an edge between (3, 1) and (1, 2) in the graph.
Out of the 3 possible permutations, 2 satisfies the given conditions. Therefore, the answer is 2.
Input: N = 2, M = 1, arr = {1, 1}, graph = {{1, 2}}
Output: 0
Explanation: There is no such permutation of the array that follows the given conditions.
Approach: To solve the problem using Dynamic Programming + Bitmasking follow the below idea:
We will be trying to calculate the count of permutations which is ending at node arr[i] and where all elements are considered. We will find such count for all i from 0 to N and in the end will add all such count of permutations in our answer. Here In our mask if jth setbit is on this implies node arr[j] is already considered in our permutation till now. We will be using dynamic programming with bitmasking as there could be possibility that we have considered the same set of elements up to now in our permutation and it is ending at a same node so to stop recalculation we will store such values.
Steps that were to follow the above approach:
- Create a 2d array, dp, and initialize it with 0. Here dp[i][j] is used to store the number of permutations that end at the node arr[i] and all the array indices corresponding to the set bits in the number j have been visited.
- Create a 2d array, adj, and initialize it with 0. Here if adj[i][j] is 1 then there is an edge between node i and j else there isn’t.
- Update the value of dp to 1 in case of j=1<<i as there will be one permutation ending at i and of size 1.
- Run three loops, the first loop will be for all possible values of the mask, In the second loop we will be iterating, i, over 0 to N, and in the third loop, we will be iterating, j, over 0 to N. Second loop will be inside first and third will be inside second.
- Now inside the third loop if there is an edge between i and j and i do not equal to j as well as arr[i] and arr[j] are not equal and if j is already not taken in the mask then we will update our dp[i][mask]
- dp[i][mask] += dp[j][mask ^ (1 << i)]
- Now inside the third loop if there is an edge between i and j and i do not equal to j as well as arr[i] and arr[j] are not equal and if j is already not taken in the mask then we will update our dp[i][mask]
- Initialize ans variable with 0.
- Run a loop for i equals 0 to N where we will be adding dp[i][mask] in ans where dp[i][mask] is the count of all permutations that ends at node arr[i] and all elements are considered i.e.
mask = (1 << N) – 1. - Return ans.
Below is the code to implement the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Define the countPermutations function// that takes in N, M, arr, and// graph as argumentslong long int countPermutations(int N, int M, vector<int> arr, vector<vector<int> > graph){ // Create a 2D vector dp of size Nx2^N // and initialize all values to 0 vector<vector<long long int> > dp( N, vector<long long int>(1 << N, 0)); // Set the base cases where each // element i is used on its own, // represented by a bitmask with // only the ith bit set to 1 for (int i = 0; i < N; i++) { dp[i][1 << i] = 1; } // Create an adjacency matrix adj of // size NxN to represent the edges // in the graph vector<vector<int> > adj(N, vector<int>(N, 0)); for (vector<int> edge : graph) { // Set the corresponding entries // in the adjacency matrix to 1 to // represent the edges in the graph adj[edge[0] - 1][edge[1] - 1] = 1; adj[edge[1] - 1][edge[0] - 1] = 1; } // Loop over all possible bitmasks // of length N for (int bitmask = 1; bitmask < (1 << N); bitmask++) { // Loop over all elements i // in the bitmask for (int i = 0; i < N; i++) { // Check if element i is used // in the bitmask if ((1 & (bitmask >> i))) { // Loop over all other // elements j in the // bitmask for (int j = 0; j < N; j++) { // Check if element j // is adjacent to element // i in the graph, has a // different value in arr, // and is also used in // the bitmask if (j != i && arr[j] != arr[i] && (1 & (bitmask >> j)) && adj[arr[i] - 1][arr[j] - 1]) { // update the count // of permutations that // end with element i // and have the same set // of used elements as // the current bitmask // by adding the count of // permutations that end // with element j and // have the set of used // elements represented // by the bitmask with // the ith bit flipped // from 1 to 0 dp[i][bitmask] += dp[j][bitmask ^ (1 << i)]; } } } } } // Sum up the counts of permutations // that end with each element i and // have used all N elements, // represented by the bitmask with // all N bits set to 1 long long int ans = 0; for (int i = 0; i < N; i++) { ans += dp[i][(1 << N) - 1]; } // Return the total count of required // permutations return ans;}// Driver's codeint main(){ // set the values of N, M, arr, // and graph int N = 3, M = 2; vector<int> arr = { 1, 2, 3 }; vector<vector<int> > graph = { { 3, 1 }, { 1, 2 } }; // Call the countPermutations function // with the given arguments and // print the result long long int ans = countPermutations(N, M, arr, graph); cout << ans;} |
Java
// Java code to implement the approachimport java.util.*;public class GFG{ // Define the countPermutations function // that takes in N, M, arr, and // graph as arguments public static long countPermutations(int N, int M, List<Integer> arr, List<List<Integer> > graph) { // Create a 2D vector dp of size Nx2^N // and initialize all values to 0 List<List<Long> > dp = new ArrayList<>(); for (int i = 0; i < N; i++) { List<Long> row = new ArrayList<>(); for (int j = 0; j < (1 << N); j++) { row.add(0L); } dp.add(row); } // Set the base cases where each // element i is used on its own, // represented by a bitmask with // only the ith bit set to 1 for (int i = 0; i < N; i++) { dp.get(i).set(1 << i, 1L); } // Create an adjacency matrix adj of // size NxN to represent the edges // in the graph int[][] adj = new int[N][N]; for (List<Integer> edge : graph) { // Set the corresponding entries // in the adjacency matrix to 1 to // represent the edges in the graph int u = edge.get(0) - 1; int v = edge.get(1) - 1; adj[u][v] = 1; adj[v][u] = 1; } // Loop over all possible bitmasks // of length N for (int bitmask = 1; bitmask < (1 << N); bitmask++) { // Loop over all elements i // in the bitmask for (int i = 0; i < N; i++) { // Check if element i is used // in the bitmask if ((bitmask & (1 << i)) != 0) { // Loop over all other // elements j in the // bitmask for (int j = 0; j < N; j++) { // Check if element j // is adjacent to element // i in the graph, has a // different value in arr, // and is also used in // the bitmask if (j != i && arr.get(j) != arr.get(i) && (bitmask & (1 << j)) != 0 && adj[arr.get(i) - 1] [arr.get(j) - 1] == 1) { // update the count // of permutations that // end with element i // and have the same set // of used elements as // the current bitmask // by adding the count of // permutations that end // with element j and // have the set of used // elements represented // by the bitmask with // the ith bit flipped // from 1 to 0 dp.get(i).set( bitmask, dp.get(i).get(bitmask) + dp.get(j).get( bitmask ^ (1 << i))); } } } } } // Sum up the counts of permutations // that end with each element i and // have used all N elements, // represented by the bitmask with // all N bits set to 1 long ans = 0; for (int i = 0; i < N; i++) { ans += dp.get(i).get((1 << N) - 1); } // Return the total count of required // permutations return ans; } // Driver's code public static void main(String[] args) { // set the values of N, M, arr, // and graph int N = 3; int M = 2; List<Integer> arr = new ArrayList<>(Arrays.asList(1, 2, 3)); List<List<Integer> > graph = new ArrayList<>(); graph.add(new ArrayList<>(Arrays.asList(3, 1))); graph.add(new ArrayList<>(Arrays.asList(1, 2))); // Call the countPermutations function // with the given arguments and // print the result long ans = countPermutations(N, M, arr, graph); System.out.println(ans); }} |
Python3
# Python code to implement the approach# Define the countPermutations function# that takes in N, M, arr, and# graph as argumentsdef countPermutations(N, M, arr, graph): # Create a 2D list dp of size Nx2^N # and initialize all values to 0 dp = [[0]*(1 << N) for _ in range(N)] # Set the base cases where each # element i is used on its own, # represented by a bitmask with # only the ith bit set to 1 for i in range(N): dp[i][1 << i] = 1 # Create an adjacency matrix adj of # size NxN to represent the edges # in the graph adj = [[0]*N for _ in range(N)] for edge in graph: # Set the corresponding entries # in the adjacency matrix to 1 to # represent the edges in the graph adj[edge[0] - 1][edge[1] - 1] = 1 adj[edge[1] - 1][edge[0] - 1] = 1 # Loop over all possible bitmasks # of length N for bitmask in range(1, 1 << N): # Loop over all elements i # in the bitmask for i in range(N): # Check if element i is used # in the bitmask if (1 & (bitmask >> i)): # Loop over all other # elements j in the # bitmask for j in range(N): # Check if element j # is adjacent to element # i in the graph, has a # different value in arr, # and is also used in # the bitmask if j != i and arr[j] != arr[i] and (1 & (bitmask >> j)) and adj[arr[i] - 1][arr[j] - 1]: # Update the count # of permutations that # end with element i # and have the same set # of used elements as # the current bitmask # by adding the count of # permutations that end # with element j and # have the set of used # elements represented # by the bitmask with # the ith bit flipped # from 1 to 0 dp[i][bitmask] += dp[j][bitmask ^ (1 << i)] # Sum up the counts of permutations # that end with each element i and # have used all N elements, # represented by the bitmask with # all N bits set to 1 ans = 0 for i in range(N): ans += dp[i][(1 << N) - 1] # Return the total count of required # permutations return ans# Driver's code# set the values of N, M, arr,# and graphN, M = 3, 2arr = [1, 2, 3]graph = [[3, 1], [1, 2]]# Call the countPermutations function# with the given arguments and# print the resultans = countPermutations(N, M, arr, graph)print(ans) |
C#
using System;using System.Collections.Generic;public class GFG { static long CountPermutations(int N, int M, List<int> arr, List<List<int> > graph) { // Create a 2D list dp of size Nx2^N and initialize // all values to 0 List<List<long> > dp = new List<List<long> >(); for (int i = 0; i < N; i++) { dp.Add(new List<long>()); for (int j = 0; j < (1 << N); j++) { dp[i].Add(0); } } // Set the base cases where each element i is used // on its own, represented by a bitmask with only // the ith bit set to 1 for (int i = 0; i < N; i++) { dp[i][1 << i] = 1; } // Create an adjacency matrix adj of size NxN to // represent the edges in the graph int[, ] adj = new int[N, N]; foreach(List<int> edge in graph) { // Set the corresponding entries in the // adjacency matrix to 1 to represent the edges // in the graph adj[edge[0] - 1, edge[1] - 1] = 1; adj[edge[1] - 1, edge[0] - 1] = 1; } // Loop over all possible bitmasks of length N for (int bitmask = 1; bitmask < (1 << N); bitmask++) { // Loop over all elements i in the bitmask for (int i = 0; i < N; i++) { // Check if element i is used in the bitmask if ((1 & (bitmask >> i)) != 0) { // Loop over all other elements j in the // bitmask for (int j = 0; j < N; j++) { // Check if element j is adjacent to // element i in the graph, has a // different value in arr, and is // also used in the bitmask if (j != i && arr[j] != arr[i] && (1 & (bitmask >> j)) != 0 && adj[arr[i] - 1, arr[j] - 1] != 0) { // update the count of // permutations that end with // element i and have the same // set of used elements as the // current bitmask by adding the // count of permutations that // end with element j and have // the set of used elements // represented by the bitmask // with the ith bit flipped from // 1 to 0 dp[i][bitmask] += dp[j] [bitmask ^ (1 << i)]; } } } } } // Sum up the counts of permutations that end with // each element i and have used all N elements, // represented by the bitmask with all N bits set to // 1 long ans = 0; for (int i = 0; i < N; i++) { ans += dp[i][(1 << N) - 1]; } // Return the total count of required permutations return ans; } static public void Main() { // set the values of N, M, arr, // and graph int N = 3, M = 2; List<int> arr = new List<int>() { 1, 2, 3 }; List<List<int> > graph = new List<List<int> >() { new List<int>() { 3, 1 }, new List<int>() { 1, 2 } }; // Call the CountPermutations function // with the given arguments and // print the result long ans = CountPermutations(N, M, arr, graph); Console.WriteLine(ans); }} |
Javascript
// Javascript code to implement the approach// Define the countPermutations function// that takes in N, M, arr, and// graph as argumentsfunction countPermutations(N, M, arr, graph) {// Create a 2D array dp of size Nx2^N// and initialize all values to 0let dp = Array.from(Array(N), () => Array(1 << N).fill(0));// Set the base cases where each// element i is used on its own,// represented by a bitmask with// only the ith bit set to 1for (let i = 0; i < N; i++) { dp[i][1 << i] = 1;}// Create an adjacency matrix adj of// size NxN to represent the edges// in the graphlet adj = Array.from(Array(N), () => Array(N).fill(0));for (let edge of graph) { // Set the corresponding entries // in the adjacency matrix to 1 to // represent the edges in the graph adj[edge[0] - 1][edge[1] - 1] = 1; adj[edge[1] - 1][edge[0] - 1] = 1;}// Loop over all possible bitmasks// of length Nfor (let bitmask = 1; bitmask < (1 << N); bitmask++) { // Loop over all elements i // in the bitmask for (let i = 0; i < N; i++) { // Check if element i is used // in the bitmask if (1 & (bitmask >> i)) { // Loop over all other // elements j in the // bitmask for (let j = 0; j < N; j++) { // Check if element j // is adjacent to element // i in the graph, has a // different value in arr, // and is also used in // the bitmask if (j != i && arr[j] != arr[i] && (1 & (bitmask >> j)) && adj[arr[i] - 1][arr[j] - 1]) { // update the count // of permutations that // end with element i // and have the same set // of used elements as // the current bitmask // by adding the count of // permutations that end // with element j and // have the set of used // elements represented // by the bitmask with // the ith bit flipped // from 1 to 0 dp[i][bitmask] += dp[j][bitmask ^ (1 << i)]; } } } }}// Sum up the counts of permutations// that end with each element i and// have used all N elements,// represented by the bitmask with// all N bits set to 1let ans = 0;for (let i = 0; i < N; i++) { ans += dp[i][(1 << N) - 1];}// Return the total count of required// permutationsreturn ans;}// Driver's codelet N = 3, M = 2;let arr = [1, 2, 3];let graph = [[3, 1], [1, 2]];// Call the countPermutations function// with the given arguments and// print the resultlet ans = countPermutations(N, M, arr, graph);console.log(ans); |
Output
2
Time Complexity: O(N^2).
Auxiliary Space: O(N*2N).
Related Articles:
- Introduction to Dynamic Programming – Data Structures and Algorithm Tutorials
- What is Bitmasking?
- Introduction to Graphs – Data Structure and Algorithm Tutorials
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
