Número de permutaciones tales que la suma de elementos en el índice impar y el índice par son iguales

Dados N números, encuentre el número de permutaciones en las que la suma de los elementos en el índice impar y la suma de los elementos en el índice par son iguales. 
Ejemplos:

Entrada: 1 2 3 
Salida:
Las permutaciones son: 
1 3 2 suma en índice impar = 1+2 = 3, suma en índice par = 3 
2 3 1 suma en índice impar = 2+1 = 3, suma en índice par = 3
Entrada: 1 2 1 2 
Salida:
Las permutaciones son: 
1 2 2 1 
2 1 1 2 
2 2 1 1 

El enfoque del problema será usar next_permutation() en C++ STL, que ayuda a generar todas las permutaciones posibles de N números. Si la suma de los elementos del índice impar es igual a la suma de los elementos del índice par de la permutación generada, aumente el recuento. Cuando todas las permutaciones estén marcadas, imprima el conteo. 
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ program to find number of permutations
// such that sum of elements at odd index
// and even index are equal
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns the number of permutations
int numberOfPermutations(int a[], int n)
{
    int sumEven, sumOdd, c = 0;
 
    // iterate for all permutations
    do {
        // stores the sum of odd and even index elements
        sumEven = sumOdd = 0;
 
        // iterate for elements in permutation
        for (int i = 0; i < n; i++) {
 
            // if odd index
            if (i % 2)
                sumOdd += a[i];
            else
                sumEven += a[i];
        }
 
        // If condition holds
        if (sumOdd == sumEven)
            c++;
 
    } while (next_permutation(a, a + n));
 
    // return the number of permutations
    return c;
}
// Driver Code
int main()
{
 
    int a[] = { 1, 2, 3 };
    int n = sizeof(a) / sizeof(a[0]);
 
    // Calling Function
    cout << numberOfPermutations(a, n);
 
    return 0;
}

Java

// Java program to find number of permutations
// such that sum of elements at odd index
// and even index are equal
class GFG {
 
// Function that returns the number of permutations
    static int numberOfPermutations(int a[], int n) {
        int sumEven, sumOdd, c = 0;
 
        // iterate for all permutations
        do {
            // stores the sum of odd and even index elements
            sumEven = sumOdd = 0;
 
            // iterate for elements in permutation
            for (int i = 0; i < n; i++) {
 
                // if odd index
                if (i % 2 == 0) {
                    sumOdd += a[i];
                } else {
                    sumEven += a[i];
                }
            }
 
            // If condition holds
            if (sumOdd == sumEven) {
                c++;
            }
 
        } while (next_permutation(a));
 
        // return the number of permutations
        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;
    }
// Driver Code
 
    public static void main(String args[]) {
        int a[] = {1, 2, 3};
        int n = a.length;
        System.out.println(numberOfPermutations(a, n));
    }
}
/*This code is contributed by 29AjayKumar*/

Python3

# Python3 program to find number of permutations
# such that sum of elements at odd index
# and even index are equal
 
def next_permutation(arr):
 
    arrCount = len(arr);
     
    # the head of the suffix
    i = arrCount - 1;
     
    # find longest suffix
    while (i > 0 and arr[i] <= arr[i - 1]):
        i-=1;
     
    # are we at the last permutation already?
    if (i <= 0):
        return [False,arr];
     
    # get the pivot
    pivotIndex = i - 1;
     
    # find rightmost element that exceeds the pivot
    j = arrCount - 1;
    while (arr[j] <= arr[pivotIndex]):
        j-=1;
         
    # swap the pivot with j
    temp = arr[pivotIndex];
    arr[pivotIndex] = arr[j];
    arr[j] = temp;
     
    # reverse the suffix
    j = arrCount - 1;
    while (i < j):
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i+=1;
            j-=1;
 
    return [True,arr];
 
# Function that returns the number
# of permutations
def numberOfPermutations(a, n):
 
    sumEven=0;
    sumOdd=0;
    c = 0;
 
    # iterate for all permutations
    while (True):
         
        # stores the sum of odd and
        # even index elements
        sumEven = 0;
        sumOdd = 0;
 
        # iterate for elements in permutation
        for i in range(n):
 
            # if odd index
            if (i % 2):
                sumOdd += a[i];
            else:
                sumEven += a[i];
 
        # If condition holds
        if (sumOdd == sumEven):
            c+=1;
        xx=next_permutation(a);
        if(xx[0]==False):
            break;
        a=xx[1];
 
    # return the number of permutations
    return c;
 
# Driver Code
a = [1, 2, 3];
n = len(a);
 
# Calling Function
print(numberOfPermutations(a, n));
 
# This code is contributed by mits

C#

// C# program to find number of permutations
// such that sum of elements at odd index
// and even index are equal
using System;
 
public class GFG {
  
// Function that returns the number of permutations
    static int numberOfPermutations(int []a, int n) {
        int sumEven, sumOdd, c = 0;
  
        // iterate for all permutations
        do {
            // stores the sum of odd and even index elements
            sumEven = sumOdd = 0;
  
            // iterate for elements in permutation
            for (int i = 0; i < n; i++) {
  
                // if odd index
                if (i % 2 == 0) {
                    sumOdd += a[i];
                } else {
                    sumEven += a[i];
                }
            }
  
            // If condition holds
            if (sumOdd == sumEven) {
                c++;
            }
  
        } while (next_permutation(a));
  
        // return the number of permutations
        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;
    }
// Driver Code
  
    public static void Main() {
        int []a = {1, 2, 3};
        int n = a.Length;
        Console.WriteLine(numberOfPermutations(a, n));
    }
}
/*This code is contributed by 29AjayKumar*/

PHP

<?php
// PHP program to find number of permutations
// such that sum of elements at odd index
// and even index are equal
 
function next_permutation(&$input)
{
    $inputCount = count($input);
     
    // the head of the suffix
    $i = $inputCount - 1;
     
    // find longest suffix
    while ($i > 0 && $input[$i] <= $input[$i - 1])
    {
        $i--;
    }
     
    // are we at the last permutation already?
    if ($i <= 0)
    {
        return false;
    }
     
    // get the pivot
    $pivotIndex = $i - 1;
     
    // find rightmost element that exceeds the pivot
    $j = $inputCount - 1;
    while ($input[$j] <= $input[$pivotIndex])
    {
        $j--;
    }
         
    // swap the pivot with j
    $temp = $input[$pivotIndex];
    $input[$pivotIndex] = $input[$j];
    $input[$j] = $temp;
     
    // reverse the suffix
    $j = $inputCount - 1;
    while ($i < $j)
    {
            $temp = $input[$i];
            $input[$i] = $input[$j];
            $input[$j] = $temp;
            $i++;
            $j--;
    }
    return true;
}
 
// Function that returns the number
// of permutations
function numberOfPermutations($a, $n)
{
    $sumEven;
    $sumOdd;
    $c = 0;
 
    // iterate for all permutations
    do {
         
        // stores the sum of odd and
        // even index elements
        $sumEven = $sumOdd = 0;
 
        // iterate for elements in permutation
        for ($i = 0; $i < $n; $i++)
        {
 
            // if odd index
            if ($i % 2)
                $sumOdd += $a[$i];
            else
                $sumEven += $a[$i];
        }
 
        // If condition holds
        if ($sumOdd == $sumEven)
            $c++;
 
    } while (next_permutation($a));
 
    // return the number of permutations
    return $c;
}
 
// Driver Code
$a = array(1, 2, 3);
$n = count($a);
 
// Calling Function
echo numberOfPermutations($a, $n);
 
// This code is contributed by
// Rajput-Ji
?>

Javascript

<script>
 
// javascript program to find number of permutations
// such that sum of elements at odd index
// and even index are equal     // Function that returns the number of permutations
    function numberOfPermutations( a , n) {
        var sumEven, sumOdd, c = 0;
 
        // iterate for all permutations
        do {
            // stores the sum of odd and even index elements
            sumEven = sumOdd = 0;
 
            // iterate for elements in permutation
            for (var i = 0; i < n; i++) {
 
                // if odd index
                if (i % 2 == 0) {
                    sumOdd += a[i];
                } else {
                    sumEven += a[i];
                }
            }
 
            // If condition holds
            if (sumOdd == sumEven) {
                c++;
            }
 
        } while (next_permutation(a));
 
        // return the number of permutations
        return c;
    }
 
    function next_permutation(p) {
        for (var a = p.length - 2; a >= 0; --a) {
            if (p[a] < p[a + 1]) {
                for (var b = p.length - 1;; --b) {
                    if (p[b] > p[a]) {
                        var 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;
    }
    // Driver Code
 
     
        var a = [ 1, 2, 3 ];
        var n = a.length;
        document.write(numberOfPermutations(a, n));
 
// This code contributed by Princi Singh
</script>
Producción: 

2

 

Complejidad temporal: O(N! * N)  

Publicación traducida automáticamente

Artículo escrito por RohanDeoli y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *