Рубрики

Подсчитать количество перестановок массива, не имеющего вложенного массива размером два или более из исходного массива

Для заданного массива различных целых чисел A задача состоит в том, чтобы подсчитать количество возможных перестановок заданного массива A [] так, чтобы перестановки не содержали подмассива размером 2 или более из исходного массива.

Примеры:

Input: A = [ 1, 3, 9 ]
Output: 3
All the permutation of [ 1, 3, 9 ] are : [ 1, 3, 9 ], [ 1, 9, 3 ], [ 3, 9, 1 ], [ 3, 1, 9 ], [ 9, 1, 3 ], [ 9, 3, 1 ]

Here [ 1, 3, 9 ], [ 9, 1, 3 ] are removed as they contain sub-array [ 1, 3 ] from original list
and [ 3, 9, 1 ] removed as it contains sub-array [3, 9] from original list so,
Following are the 3 arrays that satisfy the condition : [1, 9, 3], [3, 1, 9], [9, 3, 1]

Input : A = [1, 3, 9, 12]
Output :11

Наивный подход: переберите список всех перестановок и удалите те массивы, которые содержат любой подмассив [i, i + 1] из A.

Ниже приведена реализация вышеуказанного подхода:

# Python реализация подхода

  
# Импорт itertools

from itertools import permutations

  
# Функция, которая возвращает количество всех перестановок
# не имеет подмассива [i, i + 1]

def count(arr):

    z =[]

    perm = permutations(arr)

    for i in list(perm):

        z.append(list(i))

  

    q =[]

    for i in range(len(arr)-1):

        x, y = arr[i], arr[i + 1]

        for j in range(len(z)):

  

            # Нахождение индексов, где присутствует x

            if z[j].index(x)!= len(z[j])-1:

  

                # Если у присутствует в положении х + 1

                # добавить в список временных q

                if z[j][z[j].index(x)+1]== y:

                    q.append(z[j])

  

    # Удаление всех присутствующих списков

    # в z (список всех премий)

    for i in range(len(q)):

         if q[i] in z:

             z.remove(q[i])

    return len(z)

  
Код водителя

A =[1, 3, 9]

print(count(A))

Выход:

3

Эффективное решение: после принятия решения для меньшего размера массива мы можем наблюдать шаблон:

Следующий шаблон генерирует повторение:
Предположим, что длина массива A равна n, тогда:

count(0) = 1
count(1) = 1
count(n) = n * count(n-1) + (n-1) * count(n-2)

Ниже приведена реализация подхода:

C ++

// C ++ реализация подхода
#include<bits/stdc++.h>

using namespace std;

  
// Рекурсивная функция, которая возвращает
// подсчет на основе перестановок
// по длине массива.

int count(int n)

    if(n == 0)

        return 1;

    if(n == 1)

        return 1;

    else

        return (n * count(n - 1)) + 

              ((n - 1) * count(n - 2));

}

  
// Код драйвера

int main()

{

    int A[] = {1, 2, 3, 9};

      

    // длина массива

    int n = 4;

          

    // Вывести требуемый ответ

    cout << count(n - 1); 

          

    return 0;

}

  
// Этот код предоставлен Sanjit Prasad

Джава

// Java реализация подхода

import java.util.*;

  

class GFG

{

  
// Рекурсивная функция, которая возвращает
// подсчет на основе перестановок
// по длине массива.

static int count(int n)

    if(n == 0)

        return 1;

    if(n == 1)

        return 1;

    else

        return (n * count(n - 1)) + 

              ((n - 1) * count(n - 2));

}

  
// Код драйвера

public static void main(String[] args)

{

    int A[] = {1, 2, 3, 9};

      

    // длина массива

    int n = 4;

          

    // Вывести требуемый ответ

    System.out.println(count(n - 1)); 

}

  
// Этот код предоставлен PrinciRaj1992

python3

# Python реализация подхода

  
# Рекурсивная функция, которая возвращает
# количество перестановок на основе
# по длине массива.

  

def count(n):

    if n == 0:

        return 1

    if n == 1:

        return 1

    else:

        return (n * count(n-1)) + ((n-1) * count(n-2))

  
Код водителя

A =[1, 2, 3, 9]

print(count(len(A)-1))

C #

// C # реализация вышеуказанного подхода

using System;

  

class GFG

{

  
// Рекурсивная функция, которая возвращает
// подсчет на основе перестановок
// по длине массива.

static int count(int n)

    if(n == 0)

        return 1;

    if(n == 1)

        return 1;

    else

        return (n * count(n - 1)) + 

              ((n - 1) * count(n - 2));

}

  
// Код драйвера

public static void Main(String[] args)

{

    int []A = {1, 2, 3, 9};

      

    // длина массива

    int n = 4;

          

    // Вывести требуемый ответ

    Console.WriteLine(count(n - 1)); 

}
}

  
// Этот код предоставлен PrinciRaj1992

Выход:

11

Примечание: для повторения выше вы можете проверить oeis.org .

Рекомендуемые посты:

Подсчитать количество перестановок массива, не имеющего вложенного массива размером два или более из исходного массива

0.00 (0%) 0 votes