Número de permutaciones únicas que comienzan con 1 de una string binaria

Posted on by Rudeus Greyrat

Dada una string binaria compuesta de 0 y 1. La tarea es encontrar el número de permutaciones únicas de la string que comienza con 1. 
Nota : dado que la respuesta puede ser muy grande, imprima la respuesta en módulo 10 9 + 7.
Ejemplos: 
 

Input : str ="10101001001"
Output : 210

Input : str ="101110011"
Output : 56

La idea es encontrar primero el conteo de 1 y el conteo de 0 en la string dada. Ahora, consideremos que la string tiene una longitud  L y consta de al menos un 1. Sean el número de 1  n y el número de 0  m . De n números de 1, tenemos que colocar un 1 al comienzo de la string, por lo que nos quedan n-1 1 y m 0, tenemos que permutar estos (n-1) 1 y m 0 de longitud (L-1) de la cuerda 
Por tanto, el número de permutaciones será: 
 

(L-1)! / ((n-1)!*(m)!)

A continuación se muestra la implementación de la idea anterior: 
 

C++

// C++ program to find number of unique permutations
// of a binary string starting with 1
 
#include <bits/stdc++.h>
using namespace std;
 
#define MAX 1000003
#define mod 1000000007
 
// Array to store factorial of i at
// i-th index
long long fact[MAX];
 
// Precompute factorials under modulo mod
// upto MAX
void factorial()
{
    // factorial of 0 is 1
    fact[0] = 1;
 
    for (int i = 1; i < MAX; i++) {
        fact[i] = (fact[i - 1] * i) % mod;
    }
}
 
// Iterative Function to calculate (x^y)%p in O(log y)
long long power(long long x, long long y, long long p)
{
    long long res = 1; // Initialize result
 
    x = x % p; // Update x if it is more than or
    // equal to p
 
    while (y > 0) {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;
 
        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}
 
// Function to find the modular inverse
long long inverse(int n)
{
 
    return power(n, mod - 2, mod);
}
 
// Function to find the number of permutation
// starting with 1 of a binary string
int countPermutation(string s)
{
    // Generate factorials upto MAX
    factorial();
 
    int length = s.length(), num1 = 0, num0;
    long long count = 0;
 
    // find number of 1's
    for (int i = 0; i < length; i++) {
        if (s[i] == '1')
            num1++;
    }
 
    // number of 0's
    num0 = length - num1;
 
    // Find the number of permutation of
    // string starting with 1 using the formulae:
    // (L-1)! / ((n-1)!*(m)!)
    count = (fact[length - 1] *
            inverse((fact[num1 - 1] *
                    fact[num0]) % mod)) % mod;
 
    return count;
}
 
// Driver code
int main()
{
    string str = "10101001001";
 
    cout << countPermutation(str);
 
    return 0;
}

Java

// Java program to find number of unique permutations
// of a binary string starting with 1
   
public class Improve {
     
    final static int MAX = 1000003 ;
    final static int mod = 1000000007 ;
     
    // Array to store factorial of i at
    // i-th index
    static long fact[] = new long [MAX];
     
    // Pre-compute factorials under modulo mod
    // upto MAX
    static void factorial()
    {
        // factorial of 0 is 1
        fact[0] = 1;
       
        for (int i = 1; i < MAX; i++) {
            fact[i] = (fact[i - 1] * i) % mod;
        }
    }
       
    // Iterative Function to calculate (x^y)%p in O(log y)
    static long power(long x, long y, long p)
    {
        long res = 1; // Initialize result
       
        x = x % p; // Update x if it is more than or
        // equal to p
       
        while (y > 0) {
            // If y is odd, multiply x with result
            if (y % 2 != 0)
                res = (res * x) % p;
       
            // y must be even now
            y = y >> 1; // y = y/2
            x = (x * x) % p;
        }
        return res;
    }
       
    // Function to find the modular inverse
    static long inverse(int n)
    {
       
        return power(n, mod - 2, mod);
    }
       
    // Function to find the number of permutation
    // starting with 1 of a binary string
    static int countPermutation(String s)
    {
        // Generate factorials upto MAX
        factorial();
       
        int length = s.length(), num1 = 0, num0;
        long count = 0;
       
        // find number of 1's
        for (int i = 0; i < length; i++) {
            if (s.charAt(i) == '1')
                num1++;
        }
       
        // number of 0's
        num0 = length - num1;
       
        // Find the number of permutation of
        // string starting with 1 using the formulae:
        // (L-1)! / ((n-1)!*(m)!)
        count = (fact[length - 1] * 
                inverse((int) ((fact[num1 - 1] * 
                        fact[num0]) % mod))) % mod;
       
        return (int) count;
    }
     
    // Driver code
    public static void main(String args[])
    {
           String str = "10101001001";
            
           System.out.println(countPermutation(str));
    }
    // This Code is contributed by ANKITRAI1
}

Python 3

# Python 3 program to find number
# of unique permutations of a
# binary string starting with 1
MAX = 1000003
mod = 1000000007
 
# Array to store factorial of
# i at i-th index
fact = [0] * MAX
 
# Precompute factorials under
# modulo mod upto MAX
def factorial():
     
    # factorial of 0 is 1
    fact[0] = 1
 
    for i in range(1, MAX):
        fact[i] = (fact[i - 1] * i) % mod
 
# Iterative Function to calculate
# (x^y)%p in O(log y)
def power(x, y, p):
     
    res = 1 # Initialize result
 
    x = x % p # Update x if it is
              # more than or equal to p
 
    while (y > 0) :
         
        # If y is odd, multiply
        # x with result
        if (y & 1):
            res = (res * x) % p
 
        # y must be even now
        y = y >> 1 # y = y/2
        x = (x * x) % p
     
    return res
 
# Function to find the modular inverse
def inverse( n):
    return power(n, mod - 2, mod)
 
# Function to find the number of
# permutation starting with 1 of
# a binary string
def countPermutation(s):
     
    # Generate factorials upto MAX
    factorial()
 
    length = len(s)
    num1 = 0
    count = 0
 
    # find number of 1's
    for i in range(length) :
        if (s[i] == '1'):
            num1 += 1
             
    # number of 0's
    num0 = length - num1
 
    # Find the number of permutation
    # of string starting with 1 using
    # the formulae: (L-1)! / ((n-1)!*(m)!)
    count = (fact[length - 1] *
            inverse((fact[num1 - 1] *
                     fact[num0]) % mod)) % mod
 
    return count
 
# Driver code
if __name__ =="__main__":
    s = "10101001001"
 
    print(countPermutation(s))
 
# This code is contributed
# by ChitraNayal

C#

// C# program to find number of
// unique permutations of a
// binary string starting with 1
using System;
     
class GFG
{
static int MAX = 1000003 ;
static int mod = 1000000007 ;
 
// Array to store factorial
// of i at i-th index
static long []fact = new long [MAX];
 
// Pre-compute factorials under
// modulo mod upto MAX
static void factorial()
{
    // factorial of 0 is 1
    fact[0] = 1;
     
    for (int i = 1; i < MAX; i++)
    {
        fact[i] = (fact[i - 1] * i) % mod;
    }
}
     
// Iterative Function to calculate
// (x^y)%p in O(log y)
static long power(long x,
                  long y, long p)
{
    long res = 1; // Initialize result
     
    x = x % p; // Update x if it is more
               // than or equal to p
     
    while (y > 0)
    {
        // If y is odd, multiply
        // x with result
        if (y % 2 != 0)
            res = (res * x) % p;
     
        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}
     
// Function to find the modular inverse
static long inverse(int n)
{
    return power(n, mod - 2, mod);
}
     
// Function to find the number of
// permutation starting with 1 of
// a binary string
static int countPermutation(string s)
{
    // Generate factorials upto MAX
    factorial();
     
    int length = s.Length, num1 = 0, num0;
    long count = 0;
     
    // find number of 1's
    for (int i = 0; i < length; i++)
    {
        if (s[i] == '1')
            num1++;
    }
     
    // number of 0's
    num0 = length - num1;
     
    // Find the number of permutation
    // of string starting with 1 using
    // the formulae: (L-1)! / ((n-1)!*(m)!)
    count = (fact[length - 1] *
             inverse((int) ((fact[num1 - 1] *
                    fact[num0]) % mod))) % mod;
     
    return (int) count;
}
 
// Driver code
public static void Main()
{
    string str = "10101001001";
         
    Console.WriteLine(countPermutation(str));
}
}
 
// This code is contributed
// by anuj_67

Javascript

<script>
 
// Javascript program to find number of unique permutations
// of a binary string starting with 1
 
var MAX = 1000003
var mod = 100000007
 
// Array to store factorial of i at
// i-th index
var fact = Array(MAX);
 
// Precompute factorials under modulo mod
// upto MAX
function factorial()
{
    // factorial of 0 is 1
    fact[0] = 1;
 
    for (var i = 1; i < MAX; i++) {
        fact[i] = (fact[i - 1] * i) % mod;
    }
}
 
// Iterative Function to calculate (x^y)%p in O(log y)
function power(x, y, p)
{
    var res = 1; // Initialize result
 
    x = x % p; // Update x if it is more than or
    // equal to p
 
    while (y > 0) {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;
 
        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}
 
// Function to find the modular inverse
function inverse(n)
{
 
    return power(n, mod - 2, mod);
}
 
// Function to find the number of permutation
// starting with 1 of a binary string
function countPermutation(s)
{
    // Generate factorials upto MAX
    factorial();
 
    var length = s.length, num1 = 0, num0;
    var count = 0;
 
    // find number of 1's
    for (var i = 0; i < length; i++) {
        if (s[i] == '1')
            num1++;
    }
 
    // number of 0's
    num0 = length - num1;
 
    // Find the number of permutation of
    // string starting with 1 using the formulae:
    // (L-1)! / ((n-1)!*(m)!)
    count = (fact[length - 1] *
            inverse((fact[num1 - 1] *
                    fact[num0]) % mod)) % mod;
 
    return count;
}
 
// Driver code
var str = "10101001001";
document.write( countPermutation(str));
 
</script>
Producción: 

210

 

Complejidad de tiempo: O(n), donde n es la longitud de la string.
 

Publicación traducida automáticamente

Artículo escrito por andrew1234 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 *