Count of permutations of an Array having each element as a multiple or a factor of its index
Given an integer, N, the task is to count the number of ways to generate an array, arr[] of consisting of N integers such that for every index i(1-based indexing), arr[i] is either a factor or a multiple of i, or both. The arr[] must be the permutations of all the numbers from the range [1, N].
Examples:
Input: N=2
Output: 2
Explanation:
Two possible arrangements are {1, 2} and {2, 1}Input: N=3
Output: 3
Explanation:
The 6 possible arrangements are {1, 2, 3}, {2, 1, 3}, {3, 2, 1}, {3, 1, 2}, {2, 3, 1} and {1, 3, 2}.
Among them, the valid arrangements are {1, 2, 3}, {2, 1, 3} and {3, 2, 1}.
Approach: The problem can be solved using Backtracking technique and the concept of print all permutations using recursion. Follow the steps below to find the recurrence relation:
- Traverse the range [1, N].
- For the current index pos, if i % pos == 0 and i % pos == 0, then insert i into the arrangement and use the concept of Backtracking to find valid permutations.
- Remove i.
- Repeat the above steps for all values in the range [1, N], and finally, print the count of valid permutations.
Below is the implementation of the above approach:
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the count of
// desired permutations
int findPermutation(unordered_set<int>& arr,
int N)
{
int pos = arr.size() + 1;
// Base case
if (pos > N)
return 1;
int res = 0;
for (int i = 1; i <= N; i++) {
// If i has not been inserted
if (arr.find(i) == arr.end()) {
// Backtrack
if (i % pos == 0 or pos % i == 0) {
// Insert i
arr.insert(i);
// Recur to find valid permutations
res += findPermutation(arr, N);
// Remove i
arr.erase(arr.find(i));
}
}
}
// Return the final count
return res;
}
// Driver Code
int main()
{
int N = 5;
unordered_set<int> arr;
cout << findPermutation(arr, N);
return 0;
}
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to find the count of
// desired permutations
static int findPermutation(Set<Integer>arr,
int N)
{
int pos = arr.size() + 1;
// Base case
if (pos > N)
return 1;
int res = 0;
for(int i = 1; i <= N; i++)
{
// If i has not been inserted
if (! arr.contains(i))
{
// Backtrack
if (i % pos == 0 || pos % i == 0)
{
// Insert i
arr.add(i);
// Recur to find valid permutations
res += findPermutation(arr, N);
// Remove i
arr.remove(i);
}
}
}
// Return the final count
return res;
}
// Driver Code
public static void main(String []args)
{
int N = 5;
Set<Integer> arr = new HashSet<Integer>();
System.out.print(findPermutation(arr, N));
}
}
// This code is contributed by chitranayal
# Python3 program to implement
# the above approach
# Function to find the count of
# desired permutations
def findPermutation(arr, N):
pos = len(arr) + 1
# Base case
if(pos > N):
return 1
res = 0
for i in range(1, N + 1):
# If i has not been inserted
if(i not in arr):
# Backtrack
if(i % pos == 0 or pos % i == 0):
# Insert i
arr.add(i)
# Recur to find valid permutations
res += findPermutation(arr, N)
# Remove i
arr.remove(i)
# Return the final count
return res
# Driver Code
N = 5
arr = set()
# Function call
print(findPermutation(arr, N))
# This code is contributed by Shivam Singh
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the count of
// desired permutations
static int findPermutation(HashSet<int>arr,
int N)
{
int pos = arr.Count + 1;
// Base case
if (pos > N)
return 1;
int res = 0;
for(int i = 1; i <= N; i++)
{
// If i has not been inserted
if (! arr.Contains(i))
{
// Backtrack
if (i % pos == 0 || pos % i == 0)
{
// Insert i
arr.Add(i);
// Recur to find valid permutations
res += findPermutation(arr, N);
// Remove i
arr.Remove(i);
}
}
}
// Return the readonly count
return res;
}
// Driver Code
public static void Main(String []args)
{
int N = 5;
HashSet<int> arr = new HashSet<int>();
Console.Write(findPermutation(arr, N));
}
}
// This code is contributed by gauravrajput1
// Javascript program to implement
// the above approach
// Function to find the count of
// desired permutations
function findPermutation(arr, N)
{
var pos = arr.size + 1;
// Base case
if (pos > N)
return 1;
var res = 0;
for(var i = 1; i <= N; i++)
{
// If i has not been inserted
if (!arr.has(i))
{
// Backtrack
if (i % pos == 0 || pos % i == 0)
{
// Insert i
arr.add(i);
// Recur to find valid permutations
res += findPermutation(arr, N);
// Remove i
arr.delete(i);
}
}
}
// Return the final count
return res;
}
// Driver Code
var N = 5;
var arr = new Set();
console.log(findPermutation(arr, N));
// This code is contributed by importantly
Output
10
Time Complexity: O(N×N!)
Auxiliary Space: O(N)
Using Brute Force in python:
Approach:
The first approach is to generate all possible permutations of the array and check if each element is a multiple or a factor of its index. We can do this using a recursive function to generate permutations and then checking each permutation.
- Define a function is_valid(arr) that takes an array arr and checks if each element is a multiple or a factor of its index. It returns True if all elements satisfy this condition, otherwise False.
- Define a recursive function generate_permutations(arr, l, r, valid_permutations) that generates all possible permutations of the array arr from index l to index r. For each permutation, it checks if it is valid using the function is_valid(arr). If a valid permutation is found, it is added to the list valid_permutations.
- Define a function count_permutations(n) that creates an array arr of size n, initializes it with values 1 to n, and calls the function generate_permutations() with arr, 0, n-1, and an empty list valid_permutations. It then returns the length of valid_permutations.
Call the function count_permutations() with the input n and print the result.
#include <iostream>
#include <vector>
using namespace std;
// Function to check if the given array is valid
bool isValid(vector<int>& arr)
{
for (int i = 0; i < arr.size(); i++) {
if (arr[i] % (i + 1) != 0
&& (i + 1) % arr[i] != 0) {
return false;
}
}
return true;
}
// Function to generate permutations recursively
void generatePermutations(
vector<int>& arr, int l, int r,
vector<vector<int> >& validPermutations)
{
if (l == r) {
if (isValid(arr)) {
validPermutations.push_back(arr);
}
}
else {
for (int i = l; i <= r; i++) {
swap(arr[l], arr[i]);
generatePermutations(arr, l + 1, r,
validPermutations);
swap(arr[l], arr[i]);
}
}
}
// Function to count valid permutations
int countPermutations(int n)
{
vector<int> arr;
for (int i = 0; i < n; i++) {
arr.push_back(i + 1);
}
vector<vector<int> > validPermutations;
generatePermutations(arr, 0, n - 1, validPermutations);
return validPermutations.size();
}
// Main function
int main()
{
cout << countPermutations(2) << endl; // Output: 2
cout << countPermutations(3) << endl; // Output: 3
return 0;
}
import java.util.ArrayList;
import java.util.List;
public class Permutations {
// Function to check if the given array is valid
static boolean isValid(int[] arr)
{
for (int i = 0; i < arr.length; i++) {
if (arr[i] % (i + 1) != 0
&& (i + 1) % arr[i] != 0) {
return false;
}
}
return true;
}
// Function to generate permutations recursively
static void
generatePermutations(int[] arr, int l, int r,
List<int[]> validPermutations)
{
if (l == r) {
if (isValid(arr)) {
validPermutations.add(arr.clone());
}
}
else {
for (int i = l; i <= r; i++) {
swap(arr, l, i);
generatePermutations(arr, l + 1, r,
validPermutations);
swap(arr, l, i);
}
}
}
// Utility function to swap two elements in an array
static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Function to count valid permutations
static int countPermutations(int n)
{
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = i + 1;
}
List<int[]> validPermutations = new ArrayList<>();
generatePermutations(arr, 0, n - 1,
validPermutations);
return validPermutations.size();
}
public static void main(String[] args)
{
System.out.println(
countPermutations(2)); // Output: 2
System.out.println(
countPermutations(3)); // Output: 3
}
}
def is_valid(arr):
for i in range(len(arr)):
if arr[i] % (i+1) != 0 and (i+1) % arr[i] != 0:
return False
return True
def generate_permutations(arr, l, r, valid_permutations):
if l == r:
if is_valid(arr):
valid_permutations.append(arr[:])
else:
for i in range(l, r+1):
arr[l], arr[i] = arr[i], arr[l]
generate_permutations(arr, l+1, r, valid_permutations)
arr[l], arr[i] = arr[i], arr[l]
def count_permutations(n):
arr = [i+1 for i in range(n)]
valid_permutations = []
generate_permutations(arr, 0, n-1, valid_permutations)
return len(valid_permutations)
print(count_permutations(2)) # Output: 2
print(count_permutations(3)) # Output: 3
// Function to check if the given array is valid
function isValid(arr) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] % (i + 1) !== 0 && (i + 1) % arr[i] !== 0) {
return false;
}
}
return true;
}
// Function to generate permutations recursively
function generatePermutations(arr, l, r, validPermutations) {
if (l === r) {
if (isValid(arr)) {
validPermutations.push([...arr]);
}
} else {
for (let i = l; i <= r; i++) {
swap(arr, l, i);
generatePermutations(arr, l + 1, r, validPermutations);
swap(arr, l, i);
}
}
}
// Utility function to swap two elements in an array
function swap(arr, i, j) {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// Function to count valid permutations
function countPermutations(n) {
let arr = [];
for (let i = 0; i < n; i++) {
arr.push(i + 1);
}
let validPermutations = [];
generatePermutations(arr, 0, n - 1, validPermutations);
return validPermutations.length;
}
// Main function
function main() {
console.log(countPermutations(2)); // Output: 2
console.log(countPermutations(3)); // Output: 3
}
// Call the main function
main();
Output
2 3
Time Complexity: O(n!)
Space Complexity: O(n!)
Using Dynamic Programming:
Approach:
- Initialize a 2D array dp to store the count of permutations. Each cell dp[i][j] represents the count of permutations with i elements and j numbers selected.
- Initialize the base case dp[0][0] = 1.
- Fill the dp array using dynamic programming. Iterate over the range [1, N] for the number of elements and [0, N] for the selected numbers.
- For each element i, iterate over the range [1, min(i, j)] to represent selecting each number up to i or j, whichever is smaller.
- Increment dp[i][j] by dp[i – 1][j – k] for permutations including the current number i, where k represents the selected number.
- Increment dp[i][j] by dp[i – 1][j] for permutations excluding the current number i.
- Sum up the counts of all valid permutations stored in dp[N].
- Return the count of valid permutations.
#include <iostream>
#include <vector>
using namespace std;
int countPermutations(int N)
{
// Initialize a 2D vector to store the count of
// permutations
vector<vector<int> > dp(N + 1, vector<int>(N + 1, 0));
// Initialize the base case
dp[0][0] = 1;
// Fill the dp array using dynamic programming
for (int i = 1; i <= N; ++i) {
for (int j = 0; j <= N; ++j) {
for (int k = 1; k <= i; ++k) {
// If either i is divisible by k or k is
// divisible by i, update dp[i][j]
if (i % k == 0 || k % i == 0) {
dp[i][j] += dp[i - 1][j - 1];
}
}
}
}
// Sum up the counts of all valid permutations
int count = 0;
for (int j = 1; j <= N; ++j) {
count += dp[N][j];
}
return count;
}
int main()
{
// Test cases
cout << countPermutations(2) << endl; // Output: 2
return 0;
}
import java.util.*;
public class Main {
/**
* This method calculates the number of permutations of
* the set {1, 2, ..., N} where each permutation has the
* property that for every i in the permutation, i % k
* == 0 or k % i == 0 for all k in {1, 2, ..., N}.
*
* @param N the size of the set from which to generate
* permutations.
* @return the number of valid permutations.
*/
public static int countPermutations(int N)
{
// Initialize a 2D array (dp table) to store the
// count of permutations.
int[][] dp = new int[N + 1][N + 1];
// Base case: one permutation of the empty set.
dp[0][0] = 1;
// Fill the dp array using dynamic programming.
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= N; j++) {
for (int k = 1; k <= i; k++) {
// If either i is divisible by k or k is
// divisible by i, update dp[i][j].
if (i % k == 0 || k % i == 0) {
dp[i][j] += (j > 0)
? dp[i - 1][j - 1]
: 0;
}
}
}
}
// Sum up the counts of all valid permutations.
int count = 0;
for (int j = 1; j <= N; j++) {
count += dp[N][j];
}
return count;
}
public static void main(String[] args)
{
// Test cases
System.out.println(
countPermutations(2)); // Output: 2
}
}
def countPermutations(N):
# Initialize a 2D array to store the count of permutations
dp = [[0] * (N + 1) for _ in range(N + 1)]
# Initialize the base case
dp[0][0] = 1
# Fill the dp array using dynamic programming
for i in range(1, N + 1):
for j in range(N + 1):
for k in range(1, i + 1):
if i % k == 0 or k % i == 0:
dp[i][j] += dp[i - 1][j - 1]
# Sum up the counts of all valid permutations
count = sum(dp[N][1:])
return count
# Test cases
print(countPermutations(2)) # Output: 2
/**
* This function calculates the number of permutations of the set {1, 2, ..., N}
* where each permutation has the property that for every i in the permutation,
* i % k === 0 or k % i === 0 for all k in {1, 2, ..., N}.
*
* @param {number} N - the size of the set from which to generate permutations.
* @returns {number} - the number of valid permutations.
*/
function countPermutations(N) {
// Initialize a 2D array (dp table) to store the count of permutations.
let dp = new Array(N + 1).fill(0).map(() => new Array(N + 1).fill(0));
// Base case: one permutation of the empty set.
dp[0][0] = 1;
// Fill the dp array using dynamic programming.
for (let i = 1; i <= N; i++) {
for (let j = 0; j <= N; j++) {
for (let k = 1; k <= i; k++) {
// If either i is divisible by k or k is divisible by i, update dp[i][j].
if (i % k === 0 || k % i === 0) {
dp[i][j] += (j > 0) ? dp[i - 1][j - 1] : 0;
}
}
}
}
// Sum up the counts of all valid permutations.
let count = 0;
for (let j = 1; j <= N; j++) {
count += dp[N][j];
}
return count;
}
// Test case
console.log(countPermutations(2)); // Output: 2
Output
2
Time Complexity: O(n^3)
Space Complexity: O(n^2)