Рубрики

Перестановка графов такая, что последовательность не убывает

Для заданного массива arr [] целых чисел задача состоит в том, чтобы найти число перестановок массива, чтобы перестановка находилась в возрастающем порядке, т.е. arr [0] ≤ arr [1] ≤ arr [2] ≤… ≤ arr [n — 1] .

Примеры:

Input: arr[] = {1, 2, 1}
Output: 2
1, 1, 2 and 1, 1, 2 are the only valid permutations.

Input: arr[] = {5, 4, 4, 5}
Output: 4

Подход: Последовательность должна быть не нисходящая т.е. обр [0] ≤ обр [1] ≤ обр [2] ≤ … ≤ обр [п — 1].
Сначала отсортируйте массив, а затем сфокусируйтесь на блоке, где все элементы равны, так как эти элементы можно переставить в P! пути, где P размер этого блока.
Перестановка этого блока не будет нарушать данное условие. Теперь найдите все блоки, в которых все элементы равны, и умножьте ответ этого отдельного блока на окончательный ответ, чтобы получить общее количество возможных перестановок.

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

C ++

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

using namespace std;

  
#define N 20

  
// Для хранения факториалов

int fact[N];

  
// Функция для обновления массива fact []
// такой факт [i] = i!

void pre()

{

  

    // 0! = 1

    fact[0] = 1;

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

  

        // я! = я * (я - 1)!

        fact[i] = i * fact[i - 1];

    }

}

  
// Функция для возврата счета
// возможных перестановок

int CountPermutation(int a[], int n)

{

  

    // Для сохранения результата

    int ways = 1;

  

    // Сортировать массив

    sort(a, a + n);

  

    // Начальный размер блока

    int size = 1;

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

  

        // Увеличить размер блока

        if (a[i] == a[i - 1]) {

            size++;

        }

        else {

  

            // Обновляем результат для

            // предыдущий блок

            ways *= fact[size];

  

            // Сбросить размер до 1

            size = 1;

        }

    }

  

    // Обновляем результат для

    // последний блок

    ways *= fact[size];

  

    return ways;

}

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

int main()

{

  

    int a[] = { 1, 2, 4, 4, 2, 4 };

    int n = sizeof(a) / sizeof(a[0]);

  

    // Предварительный расчет факториалов

    pre();

  

    cout << CountPermutation(a, n);

  

    return 0;

}

Джава

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

import java.util.Arrays; 

import java.io.*;

  

class GFG 

{

static int N = 20;

  
// Для хранения факториалов

static int []fact=new int[N];

  
// Функция для обновления массива fact []
// такой факт [i] = i!

static void pre()

{

  

    // 0! = 1

    fact[0] = 1;

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

    {

  

        // я! = я * (я - 1)!

        fact[i] = i * fact[i - 1];

    }

}

  
// Функция для возврата счета
// возможных перестановок

static int CountPermutation(int a[], int n)

{

  

    // Для сохранения результата

    int ways = 1;

  

    // Сортировать массив

    Arrays.sort(a);

  

    // Начальный размер блока

    int size = 1;

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

    {

  

        // Увеличить размер блока

        if (a[i] == a[i - 1]) 

        {

            size++;

        }

        else

        {

  

            // Обновляем результат для

            // предыдущий блок

            ways *= fact[size];

  

            // Сбросить размер до 1

            size = 1;

        }

    }

  

    // Обновляем результат для

    // последний блок

    ways *= fact[size];

  

    return ways;

}

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

public static void main (String[] args) 

{

    int a[] = { 1, 2, 4, 4, 2, 4 };

    int n = a.length;

      

    // Предварительный расчет факториалов

    pre();

      

    System.out.println (CountPermutation(a, n));

}
}

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

python3

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

N = 20

  
# Хранить факториалы

fact = [0] * N; 

  
# Функция для обновления массива fact []
# такой факт [я] = я!

def pre() :

  

    № 0! = 1

    fact[0] = 1

    for i in range(1, N):

  

        # я! = я * (я - 1)!

        fact[i] = i * fact[i - 1]; 

  
# Функция для возврата счета
Количество возможных перестановок

def CountPermutation(a, n): 

  

    # Чтобы сохранить результат

    ways = 1

  

    # Сортировать массив

    a.sort();

  

    # Начальный размер блока

    size = 1

    for i in range(1, n):

  

        # Увеличить размер блока

        if (a[i] == a[i - 1]):

            size += 1

          

        else :

  

            # Обновить результат для

            # предыдущий блок

            ways *= fact[size]; 

  

            # Сбросить размер до 1

            size = 1

  

    # Обновить результат для

    # последний блок

    ways *= fact[size]; 

  

    return ways; 

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

if __name__ == "__main__"

  

    a = [ 1, 2, 4, 4, 2, 4 ]; 

    n = len(a); 

  

    # Предварительный расчет факториалов

    pre(); 

  

    print(CountPermutation(a, n)); 

      
# Этот код предоставлен AnkitRai01

C #

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

using System;

  

class GFG

{

      

static int N = 20;

  
// Для хранения факториалов

static int []fact = new int[N];

  
// Функция для обновления массива fact []
// такой факт [i] = i!

static void pre()

{

  

    // 0! = 1

    fact[0] = 1;

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

    {

  

        // я! = я * (я - 1)!

        fact[i] = i * fact[i - 1];

    }

}

  
// Функция для возврата счета
// возможных перестановок

static int CountPermutation(int []a, int n)

{

  

    // Для сохранения результата

    int ways = 1;

  

    // Сортировать массив

    Array.Sort(a);

  

    // Начальный размер блока

    int size = 1;

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

    {

  

        // Увеличить размер блока

        if (a[i] == a[i - 1]) 

        {

            size++;

        }

        else

        {

  

            // Обновляем результат для

            // предыдущий блок

            ways *= fact[size];

  

            // Сбросить размер до 1

            size = 1;

        }

    }

  

    // Обновляем результат для

    // последний блок

    ways *= fact[size];

  

    return ways;

}

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

static public void Main ()

{

    int []a = { 1, 2, 4, 4, 2, 4 };

    int n = a.Length;

      

    // Предварительный расчет факториалов

    pre();

      

    Console.Write(CountPermutation(a, n));

}
}

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

Выход:

12

Сложность времени: O (N * logN)

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

Перестановка графов такая, что последовательность не убывает

0.00 (0%) 0 votes