Recuento de permutaciones de un Array que tiene cada elemento como múltiplo o factor de su índice

Dado un número entero, N , la tarea es contar el número de formas de generar una array, arr[] que consta de N enteros tales que para cada índice i (indexación basada en 1), arr[i] es un factor o un múltiplo de i , o ambos. El arr[] debe ser las permutaciones de todos los números del rango [1, N] .

Ejemplos:

Entrada: N=2
Salida: 2
Explicación:
Dos arreglos posibles son {1, 2} y {2, 1}

Entrada: N=3
Salida: 3
Explicación:
Los 6 arreglos posibles son {1, 2, 3}, {2, 1, 3}, {3, 2, 1}, {3, 1, 2}, {2, 3, 1} y {1, 3, 2}.
Entre ellos, los arreglos válidos son {1, 2, 3}, {2, 1, 3} y {3, 2, 1}.

Enfoque : El problema se puede resolver usando la técnica de Backtracking y el concepto de imprimir todas las permutaciones usando la recursividad. Siga los pasos a continuación para encontrar la relación de recurrencia:

1. Atraviesa el rango [1, N] .
2. Para el índice actual pos , si i % pos == 0 e i % pos == 0 , entonces inserte i en el arreglo y use el concepto de Backtracking para encontrar permutaciones válidas.
3. Quitar yo .
4. Repita los pasos anteriores para todos los valores en el rango [1, N] y, finalmente, imprima el recuento de permutaciones válidas.

A continuación se muestra la implementación del enfoque anterior:

// 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

<script>
 
// 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();
 
document.write(findPermutation(arr, N));
 
// This code is contributed by importantly
 
</script>

10

Complejidad temporal: O(N×N!)
Espacio auxiliar: O(N)