Nombre de permutations d’un tableau dont chaque élément est un multiple ou un facteur de son index

Étant donné un entier, Nla tâche consiste à compter le nombre de façons de générer un tableau, arr[] consistant à N entiers tels que pour tout indice je(indexation de base 1), arr[i] est soit un facteur soit un multiple de je, ou les deux. La arr[] doivent être les permutations de tous les nombres de la plage [1, N].

Exemples:

Saisir: N=2
Production: 2
Explication:
Deux arrangements possibles sont {1, 2} et {2, 1}

Saisir: N=3
Production: 3
Explication:
Les 6 arrangements possibles sont {1, 2, 3}, {2, 1, 3}, {3, 2, 1}, {3, 1, 2}, {2, 3, 1} et {1, 3, 2}.
Parmi eux, les arrangements valides sont {1, 2, 3}, {2, 1, 3} et {3, 2, 1}.

Approcher: Le problème peut être résolu en utilisant Technique de retour en arrière et la notion de imprimer toutes les permutations en utilisant la récursivité. Suivez les étapes ci-dessous pour trouver la relation de récurrence :

  1. Parcourir la gamme [1, N].
  2. Pour l’indice actuel positionsi je % pos == 0 et je % pos == 0puis insérez i dans l’arrangement et utilisez le concept de Backtracking pour trouver des permutations valides.
  3. Retirer je.
  4. Répétez les étapes ci-dessus pour toutes les valeurs de la plage [1, N]et enfin, imprimer le nombre de permutations valides.

Voici la mise en œuvre de l’approche ci-dessus :

C++

#include <bits/stdc++.h>

using namespace std;

int findPermutation(unordered_set<int>& arr,

                    int N)

{

    int pos = arr.size() + 1;

    

    if (pos > N)

        return 1;

    int res = 0;

    for (int i = 1; i <= N; i++) {

        

        if (arr.find(i) == arr.end()) {

            

            if (i % pos == 0 or pos % i == 0) {

                

                arr.insert(i);

                

                res += findPermutation(arr, N);

                

                arr.erase(arr.find(i));

            }

        }

    }

    

    return res;

}

int main()

{

    int N = 5;

    unordered_set<int> arr;

    cout << findPermutation(arr, N);

    return 0;

}

Java

import java.util.*;

class GFG{

    

static int findPermutation(Set<Integer>arr,

                           int N)

{

    int pos = arr.size() + 1;

    

    if (pos > N)

        return 1;

    int res = 0;

    for(int i = 1; i <= N; i++)

    {

        

        

        if (! arr.contains(i))

        {

            

            

            if (i % pos == 0 || pos % i == 0)

            {

                

                

                arr.add(i);

                

                res += findPermutation(arr, N);

                

                arr.remove(i);

            }

        }

    }

    

    return res;

}

public static void main(String []args)

{

    int N = 5;

    Set<Integer> arr = new HashSet<Integer>();

    

    System.out.print(findPermutation(arr, N));

}

}

Python3

def findPermutation(arr, N):

    pos = len(arr) + 1

    

    if(pos > N):

        return 1

    res = 0

    for i in range(1, N + 1):

        

        if(i not in arr):

            

            if(i % pos == 0 or pos % i == 0):

                

                arr.add(i)

                

                res += findPermutation(arr, N)

                

                arr.remove(i)

    

    return res

N = 5

arr = set()

print(findPermutation(arr, N))

C#

using System;

using System.Collections.Generic;

class GFG{

    

static int findPermutation(HashSet<int>arr,

                           int N)

{

    int pos = arr.Count + 1;

    

    if (pos > N)

        return 1;

    int res = 0;

    for(int i = 1; i <= N; i++)

    {

        

        

        if (! arr.Contains(i))

        {

            

            

            if (i % pos == 0 || pos % i == 0)

            {

                

                

                arr.Add(i);

                

                res += findPermutation(arr, N);

                

                arr.Remove(i);

            }

        }

    }

    

    return res;

}

public static void Main(String []args)

{

    int N = 5;

    HashSet<int> arr = new HashSet<int>();

    

    Console.Write(findPermutation(arr, N));

}

}

Javascript

<script>

function findPermutation(arr, N)

{

    var pos = arr.size + 1;

    

    if (pos > N)

        return 1;

    var res = 0;

    for(var i = 1; i <= N; i++)

    {

        

        

        if (!arr.has(i))

        {

            

            

            if (i % pos == 0 || pos % i == 0)

            {

                

                

                arr.add(i);

                

                res += findPermutation(arr, N);

                

                arr.delete(i);

            }

        }

    }

    

    return res;

}

var N = 5;

var arr = new Set();

document.write(findPermutation(arr, N));

</script>

Complexité temporelle : O(N×N!)
Espace Auxiliaire : SUR)

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Aller en haut