Рубрики

Количество перестановок, в которых сумма элементов с нечетным индексом и четным индексом равна

Учитывая N чисел, найдите количество перестановок, в которых сумма элементов с нечетным индексом и сумма элементов с четным индексом равны.

Примеры:

Input: 1 2 3
Output: 2
The permutations are:
1 3 2 sum at odd index = 1+2 = 3, sum at even index = 3
2 3 1 sum at odd index = 2+1 = 3, sum at even index = 3

Input: 1 2 1 2
Output: 3
The permutations are:
1 2 2 1
2 1 1 2
2 2 1 1

Подход к проблеме будет заключаться в использовании next_permutation () в C ++ STL, который помогает генерировать все возможные перестановки из N чисел. Если сумма нечетных элементов индекса равна сумме четных элементов индекса сгенерированной перестановки, то увеличьте количество. Когда все перестановки проверены, выведите счетчик.

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

C ++

// C ++ программа для поиска количества перестановок
// такая, что сумма элементов по нечетному индексу
// и даже индекс равны
#include <bits/stdc++.h>

using namespace std;

  
// Функция, которая возвращает количество перестановок

int numberOfPermutations(int a[], int n)

{

    int sumEven, sumOdd, c = 0;

  

    // итерация для всех перестановок

    do {

        // хранит сумму нечетных и четных элементов индекса

        sumEven = sumOdd = 0;

  

        // итерация для элементов в перестановке

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

  

            // если нечетный индекс

            if (i % 2)

                sumOdd += a[i];

            else

                sumEven += a[i];

        }

  

        // Если условие выполнено

        if (sumOdd == sumEven)

            c++;

  

    } while (next_permutation(a, a + n));

  

    // возвращаем количество перестановок

    return c;

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

int main()

{

  

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

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

  

    // вызов функции

    cout << numberOfPermutations(a, n);

  

    return 0;

}

Джава

// Java-программа для поиска количества перестановок
// такая, что сумма элементов по нечетному индексу
// и даже индекс равны

class GFG {

  
// Функция, которая возвращает количество перестановок

    static int numberOfPermutations(int a[], int n) {

        int sumEven, sumOdd, c = 0;

  

        // итерация для всех перестановок

        do {

            // хранит сумму нечетных и четных элементов индекса

            sumEven = sumOdd = 0;

  

            // итерация для элементов в перестановке

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

  

                // если нечетный индекс

                if (i % 2 == 0) {

                    sumOdd += a[i];

                } else {

                    sumEven += a[i];

                }

            }

  

            // Если условие выполнено

            if (sumOdd == sumEven) {

                c++;

            }

  

        } while (next_permutation(a));

  

        // возвращаем количество перестановок

        return c;

    }

  

    static boolean next_permutation(int[] p) {

        for (int a = p.length - 2; a >= 0; --a) {

            if (p[a] < p[a + 1]) {

                for (int b = p.length - 1;; --b) {

                    if (p[b] > p[a]) {

                        int t = p[a];

                        p[a] = p[b];

                        p[b] = t;

                        for (++a, b = p.length - 1; a < b; ++a, --b) {

                            t = p[a];

                            p[a] = p[b];

                            p[b] = t;

                        }

                        return true;

                    }

                }

            }

        }

        return false;

    }

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

  

    public static void main(String args[]) {

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

        int n = a.length;

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

    }

}
/ * Этот код предоставлен 29AjayKumar * /

python3

# Python3 программа для поиска количества перестановок
# такое что сумма элементов по нечетному индексу
# и даже индекс равны

  

def next_permutation(arr):

  

    arrCount = len(arr);

      

    # глава суффикса

    i = arrCount - 1;

      

    # найти самый длинный суффикс

    while (i > 0 and arr[i] <= arr[i - 1]):

        i-=1;

      

    # мы уже на последней перестановке?

    if (i <= 0):

        return [False,arr];

      

    # получить точку опоры

    pivotIndex = i - 1;

      

    # найти самый правый элемент, который превышает точку поворота

    j = arrCount - 1;

    while (arr[j] <= arr[pivotIndex]):

        j-=1;

          

    # поменять точку с j

    temp = arr[pivotIndex];

    arr[pivotIndex] = arr[j];

    arr[j] = temp;

      

    # поменять суффикс

    j = arrCount - 1;

    while (i < j):

            temp = arr[i];

            arr[i] = arr[j];

            arr[j] = temp;

            i+=1;

            j-=1;

  

    return [True,arr];

  
# Функция, которая возвращает номер
Количество перестановок

def numberOfPermutations(a, n):

  

    sumEven=0;

    sumOdd=0;

    c = 0;

  

    # повторять для всех перестановок

    while (True): 

          

        # хранит сумму нечетного и

        # четные элементы индекса

        sumEven = 0;

        sumOdd = 0;

  

        # повторять для элементов в перестановке

        for i in range(n):

  

            # если нечетный индекс

            if (i % 2):

                sumOdd += a[i];

            else:

                sumEven += a[i];

  

        # Если условие выполнено

        if (sumOdd == sumEven):

            c+=1;

        xx=next_permutation(a);

        if(xx[0]==False):

            break;

        a=xx[1];

  

    # вернуть количество перестановок

    return c;

  
Код водителя

a = [1, 2, 3];

n = len(a);

  
# Вызов функции

print(numberOfPermutations(a, n));

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

C #

// C # программа для поиска количества перестановок
// такая, что сумма элементов по нечетному индексу
// и даже индекс равны

using System; 

  

public class GFG {

   
// Функция, которая возвращает количество перестановок

    static int numberOfPermutations(int []a, int n) {

        int sumEven, sumOdd, c = 0;

   

        // итерация для всех перестановок

        do {

            // хранит сумму нечетных и четных элементов индекса

            sumEven = sumOdd = 0;

   

            // итерация для элементов в перестановке

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

   

                // если нечетный индекс

                if (i % 2 == 0) {

                    sumOdd += a[i];

                } else {

                    sumEven += a[i];

                }

            }

   

            // Если условие выполнено

            if (sumOdd == sumEven) {

                c++;

            }

   

        } while (next_permutation(a));

   

        // возвращаем количество перестановок

        return c;

    }

   

    static bool next_permutation(int[] p) {

        for (int a = p.Length - 2; a >= 0; --a) {

            if (p[a] < p[a + 1]) {

                for (int b = p.Length - 1;; --b) {

                    if (p[b] > p[a]) {

                        int t = p[a];

                        p[a] = p[b];

                        p[b] = t;

                        for (++a, b = p.Length - 1; a < b; ++a, --b) {

                            t = p[a];

                            p[a] = p[b];

                            p[b] = t;

                        }

                        return true;

                    }

                }

            }

        }

        return false;

    }

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

   

    public static void Main() {

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

        int n = a.Length;

        Console.WriteLine(numberOfPermutations(a, n));

    }

}
/ * Этот код предоставлен 29AjayKumar * /

PHP

<?php
// PHP программа для поиска количества перестановок
// такая, что сумма элементов по нечетному индексу
// и даже индекс равны

  

function next_permutation(&$input)

{

    $inputCount = count($input);

      

    // глава суффикса

    $i = $inputCount - 1;

      

    // найти самый длинный суффикс

    while ($i > 0 && $input[$i] <= $input[$i - 1]) 

    {

        $i--;

    }

      

    // мы уже на последней перестановке?

    if ($i <= 0) 

    {

        return false;

    }

      

    // получить точку опоры

    $pivotIndex = $i - 1;

      

    // найти самый правый элемент, который превышает точку поворота

    $j = $inputCount - 1;

    while ($input[$j] <= $input[$pivotIndex]) 

    {

        $j--;

    }

          

    // меняем точку с j

    $temp = $input[$pivotIndex];

    $input[$pivotIndex] = $input[$j];

    $input[$j] = $temp;

      

    // инвертировать суффикс

    $j = $inputCount - 1;

    while ($i < $j

    {

            $temp = $input[$i];

            $input[$i] = $input[$j];

            $input[$j] = $temp;

            $i++;

            $j--;

    }

    return true;

}

  
// Функция, которая возвращает число
// перестановок

function numberOfPermutations($a, $n)

{

    $sumEven;

    $sumOdd;

    $c = 0;

  

    // итерация для всех перестановок

    do {

          

        // хранит сумму нечетного и

        // четные элементы индекса

        $sumEven = $sumOdd = 0;

  

        // итерация для элементов в перестановке

        for ($i = 0; $i < $n; $i++) 

        {

  

            // если нечетный индекс

            if ($i % 2)

                $sumOdd += $a[$i];

            else

                $sumEven += $a[$i];

        }

  

        // Если условие выполнено

        if ($sumOdd == $sumEven)

            $c++;

  

    } while (next_permutation($a));

  

    // возвращаем количество перестановок

    return $c;

}

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

$a = array(1, 2, 3);

$n = count($a);

  
// вызов функции

echo numberOfPermutations($a, $n);

  
// Этот код предоставлен
// Раджпут-Джи
?>

Выход:

2

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

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

Количество перестановок, в которых сумма элементов с нечетным индексом и четным индексом равна

0.00 (0%) 0 votes