Genere todas las arrays ordenadas posibles a partir de elementos alternativos de dos arrays ordenadas dadas

Dadas dos arrays ordenadas A y B, genere todas las arrays posibles de modo que el primer elemento se tome de A, luego de B, luego de A y así sucesivamente en orden creciente hasta que se agoten las arrays. Las arrays generadas deben terminar con un elemento de B.
Por ejemplo 
 

 
A = {10, 15, 25}
B = {1, 5, 20, 30}

The resulting arrays are:
  10 20
  10 20 25 30
  10 30
  15 20
  15 20 25 30
  15 30
  25 30

Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
La idea es usar la recursividad. En la función recursiva, se pasa una bandera para indicar si el elemento actual en la salida debe tomarse de ‘A’ o ‘B’. A continuación se muestra la implementación de C++.
 

C++

#include<bits/stdc++.h>
using namespace std;
 
void printArr(int arr[], int n);
 
/* Function to generates and prints all sorted arrays from alternate elements of
   'A[i..m-1]' and 'B[j..n-1]'
   If 'flag' is true, then current element is to be included from A otherwise
   from B.
   'len' is the index in output array C[]. We print output  array  each time
   before including a character from A only if length of output array is
   greater than 0. We try than all possible combinations */
void generateUtil(int A[], int B[], int C[], int i, int j, int m, int n,
                  int len, bool flag)
{
    if (flag) // Include valid element from A
    {
        // Print output if there is at least one 'B' in output array 'C'
        if (len)
            printArr(C, len+1);
 
        // Recur for all elements of A after current index
        for (int k = i; k < m; k++)
        {
            if (!len)
            {
                /* this block works for the very first call to include
                     the first element in the output array */
                C[len] = A[k];
 
                // don't increment lem as B is included yet
                generateUtil(A, B, C, k+1, j, m, n, len, !flag);
            }
            else      /* include valid element from A and recur */
            {
                if (A[k] > C[len])
                {
                    C[len+1] = A[k];
                    generateUtil(A, B, C, k+1, j, m, n, len+1, !flag);
                }
            }
        }
    }
    else   /* Include valid element from B and recur */
    {
        for (int l = j; l < n; l++)
        {
            if (B[l] > C[len])
            {
                C[len+1] = B[l];
                generateUtil(A, B, C, i, l+1, m, n, len+1, !flag);
            }
        }
    }
}
 
/* Wrapper function */
void generate(int A[], int B[], int m, int n)
{
    int C[m+n];    /* output array */
    generateUtil(A, B, C, 0, 0, m, n, 0, true);
}
 
// A utility function to print an array
void printArr(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}
 
// Driver program
int main()
{
    int A[] = {10, 15, 25};
    int B[] = {5, 20, 30};
    int n = sizeof(A)/sizeof(A[0]);
    int m = sizeof(B)/sizeof(B[0]);
    generate(A, B, n, m);
    return 0;
}

Java

class GenerateArrays {
 
    /* Function to generates and prints all sorted arrays from alternate
       elements of 'A[i..m-1]' and 'B[j..n-1]'
       If 'flag' is true, then current element is to be included from A
       otherwise from B.
       'len' is the index in output array C[]. We print output array 
       each time before including a character from A only if length of
       output array is greater than 0. We try than all possible
       combinations */
    void generateUtil(int A[], int B[], int C[], int i, int j, int m, int n,
            int len, boolean flag)
    {
        if (flag) // Include valid element from A
        {
            // Print output if there is at least one 'B' in output array 'C'
            if (len != 0)
                printArr(C, len + 1);
 
            // Recur for all elements of A after current index
            for (int k = i; k < m; k++)
            {
                if (len == 0)
                {
                    /* this block works for the very first call to include
                    the first element in the output array */
                    C[len] = A[k];
 
                    // don't increment lem as B is included yet
                    generateUtil(A, B, C, k + 1, j, m, n, len, !flag);
                }
                 
                /* include valid element from A and recur */
                else if (A[k] > C[len])
                {
                        C[len + 1] = A[k];
                        generateUtil(A, B, C, k + 1, j, m, n, len + 1, !flag);
                }
            }
        }
         
        /* Include valid element from B and recur */
        else
        {
            for (int l = j; l < n; l++)
            {
                if (B[l] > C[len])
                {
                    C[len + 1] = B[l];
                    generateUtil(A, B, C, i, l + 1, m, n, len + 1, !flag);
                }
            }
        }
    }
 
    /* Wrapper function */
    void generate(int A[], int B[], int m, int n)
    {
        int C[] = new int[m + n];
      
        /* output array */
        generateUtil(A, B, C, 0, 0, m, n, 0, true);
    }
 
    // A utility function to print an array
    void printArr(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
        System.out.println("");
    }
 
    public static void main(String[] args)
    {
        GenerateArrays generate = new GenerateArrays();
        int A[] = {10, 15, 25};
        int B[] = {5, 20, 30};
        int n = A.length;
        int m = B.length;
        generate.generate(A, B, n, m);
    }
}
 
// This code has been contributed by Mayank Jaiswal

Python3

# A utility function to print an array
def printArr(arr,n):
 
    for i in range(n):
        print(arr[i] , " ",end="")
    print()
  
''' Function to generates and prints all
    sorted arrays from alternate elements of
   'A[i..m-1]' and 'B[j..n-1]'
   If 'flag' is true, then current element
   is to be included from A otherwise
   from B.
   'len' is the index in output array C[].
    We print output  array  each time
   before including a character from A
   only if length of output array is
   greater than 0. We try than all possible combinations '''
def generateUtil(A,B,C,i,j,m,n,len,flag):
 
    if (flag): # Include valid element from A
     
        # Print output if there is at
        # least one 'B' in output array 'C'
        if (len):
            printArr(C, len+1)
  
        # Recur for all elements of
        # A after current index
        for k in range(i,m):
         
            if ( not len):
             
                ''' this block works for the
                    very first call to include
                    the first element in the output array '''
                C[len] = A[k]
  
                # don't increment lem
                # as B is included yet
                generateUtil(A, B, C, k+1, j, m, n, len,  not flag)
             
            else: 
   
                # include valid element from A and recur
                if (A[k] > C[len]):
                 
                    C[len+1] = A[k]
                    generateUtil(A, B, C, k+1, j, m, n, len+1, not flag)
                 
     
    else: 
   
        # Include valid element from B and recur
        for l in range(j,n):
         
            if (B[l] > C[len]):
             
                C[len+1] = B[l]
                generateUtil(A, B, C, i, l+1, m, n, len+1, not flag)
             
 
# Wrapper function
def generate(A,B,m,n):
 
    C=[]    #output array
    for i in range(m+n+1):
        C.append(0)
    generateUtil(A, B, C, 0, 0, m, n, 0, True)
  
  
# Driver program
 
A = [10, 15, 25]
B = [5, 20, 30]
n = len(A)
m = len(B)
 
generate(A, B, n, m)
 
# This code is contributed
# by Anant Agarwal.

C#

// C# Program to generate all possible
// sorted arrays from alternate elements
// of two given sorted arrays
using System;
 
class GenerateArrays {
 
/* Function to generates and prints
   all sorted arrays from alternate
   elements of 'A[i..m-1]' and 'B[j..n-1]'
   If 'flag' is true, then current element
   is to be included from A otherwise
   from B.
   'len' is the index in output array
   C[]. We print output array each
   time before including a character
   from A only if length of output array
   is greater than 0. We try than all
   possible combinations */
   public virtual void generateUtil(int[] A, int[] B,
                                    int[] C, int i,
                                    int j, int m, int n,
                                    int len, bool flag) {
     
    // Include valid
    // element from A                                  
    if (flag)
    {
         
        // Print output if there is
        // at least one 'B' in
        // output array 'C'
        if (len != 0) {
             
            printArr(C, len + 1);
        }
 
        // Recur for all elements
        // of A after current index
        for (int k = i; k < m; k++) {
             
            if (len == 0) {
                 
                /* this block works for the
                   very first call to include
                   the first element in the
                   output array */
                C[len] = A[k];
 
                // don't increment lem
                // as B is included yet
                generateUtil(A, B, C, k + 1, j,
                             m, n, len, !flag);
            }
 
            // include valid element
            // from A and recur
            else if (A[k] > C[len]) {
                 
                C[len + 1] = A[k];
                generateUtil(A, B, C, k + 1, j,
                         m, n, len + 1, !flag);
            }
        }
    }
 
    // Include valid element
    // from B and recur
    else {
        for (int l = j; l < n; l++) {
            if (B[l] > C[len]) {
                C[len + 1] = B[l];
                generateUtil(A, B, C, i, l + 1,
                         m, n, len + 1, !flag);
            }
        }
    }
}
 
// Wrapper function
public virtual void generate(int[] A, int[] B,
                               int m, int n) {
    int[] C = new int[m + n];
 
    // output array
    generateUtil(A, B, C, 0, 0, m, n, 0, true);
}
 
// A utility function to print an array
public virtual void printArr(int[] arr, int n) {
     
    for (int i = 0; i < n; i++) {
        Console.Write(arr[i] + " ");
    }
    Console.WriteLine("");
}
 
// Driver Code
public static void Main(string[] args) {
     
    GenerateArrays generate = new GenerateArrays();
     
    int[] A = new int[] {10, 15, 25};
    int[] B = new int[] {5, 20, 30};
     
    int n = A.Length;
    int m = B.Length;
    generate.generate(A, B, n, m);
}
}
 
// This code is contributed by Shrikant13

PHP

<?php
 
/* Function to generates and prints all
sorted arrays from alternate elements of
'A[i..m-1]' and 'B[j..n-1]'
If 'flag' is true, then current element
is to be included from A otherwise from B.
'len' is the index in output array C[].
We print output array each time before
including a character from A only if length
of output array is greater than 0. We try
than all possible combinations */
function generateUtil(&$A, &$B, &$C, $i, $j,
                       $m, $n, $len, $flag)
{
    if ($flag) // Include valid element from A
    {
        // Print output if there is at least
        // one 'B' in output array 'C'
        if ($len)
            printArr($C, $len + 1);
 
        // Recur for all elements of A
        // after current index
        for ($k = $i; $k < $m; $k++)
        {
            if (!$len)
            {
                /* this block works for the very
                first call to include the first
                element in the output array */
                $C[$len] = $A[$k];
 
                // don't increment lem as B
                // is included yet
                generateUtil($A, $B, $C, $k + 1,
                             $j, $m, $n, $len, !$flag);
            }
            else     /* include valid element
                        from A and recur */
            {
                if ($A[$k] > $C[$len])
                {
                    $C[$len + 1] = $A[$k];
                    generateUtil($A, $B, $C, $k + 1, $j,
                                 $m, $n, $len + 1, !$flag);
                }
            }
        }
    }
    else /* Include valid element
            from B and recur */
    {
        for ($l = $j; $l < $n; $l++)
        {
            if ($B[$l] > $C[$len])
            {
                $C[$len + 1] = $B[$l];
                generateUtil($A, $B, $C, $i, $l + 1,
                             $m, $n, $len + 1, !$flag);
            }
        }
    }
}
 
/* Wrapper function */
function generate(&$A, &$B, $m, $n)
{
    $C = array_fill(0, ($m + $n), NULL); /* output array */
    generateUtil($A, $B, $C, 0, 0, $m, $n, 0, true);
}
 
// A utility function to print an array
function printArr(&$arr, $n)
{
    for ($i = 0; $i < $n; $i++)
        echo $arr[$i] . " ";
    echo "\n";
}
 
// Driver Code
$A = array(10, 15, 25);
$B = array(5, 20, 30);
$n = sizeof($A);
$m = sizeof($B);
generate($A, $B, $n, $m);
 
// This code is contributed by ChitraNayal
?>

Javascript

<script>
    /*
     * Function to generates and prints all sorted arrays from alternate elements of
     * 'A[i..m-1]' and 'B[j..n-1]' If 'flag' is true, then current element is to be
     * included from A otherwise from B. 'len' is the index in output array C. We
     * print output array each time before including a character from A only if
     * length of output array is greater than 0. We try than all possible
     * combinations
     */
    function generateUtil(A , B , C , i , j , m , n , len,  flag) {
        if (flag) // Include valid element from A
        {
            // Print output if there is at least one 'B' in output array 'C'
            if (len != 0)
                printArr(C, len + 1);
 
            // Recur for all elements of A after current index
            for (var k = i; k < m; k++) {
                if (len == 0) {
                    /*
                     * this block works for the very first call to include the first element in the
                     * output array
                     */
                    C[len] = A[k];
 
                    // don't increment lem as B is included yet
                    generateUtil(A, B, C, k + 1, j, m, n, len, !flag);
                }
 
                /* include valid element from A and recur */
                else if (A[k] > C[len]) {
                    C[len + 1] = A[k];
                    generateUtil(A, B, C, k + 1, j, m, n, len + 1, !flag);
                }
            }
        }
 
        /* Include valid element from B and recur */
        else {
            for (var l = j; l < n; l++) {
                if (B[l] > C[len]) {
                    C[len + 1] = B[l];
                    generateUtil(A, B, C, i, l + 1, m, n, len + 1, !flag);
                }
            }
        }
    }
 
    /* Wrapper function */
    function generate(A , B , m , n) {
        var C = Array(m + n).fill(0);
 
        /* output array */
        generateUtil(A, B, C, 0, 0, m, n, 0, true);
    }
 
    // A utility function to print an array
    function printArr(arr , n) {
        for (i = 0; i < n; i++)
            document.write(arr[i] + " ");
        document.write("<br/>");
    }
 
     
     
        var A = [ 10, 15, 25 ];
        var B = [ 5, 20, 30 ];
        var n = A.length;
        var m = B.length;
        generate(A, B, n, m);
 
// This code contributed by gauravrajput1
</script>

Producción: 
 

10 20
10 20 25 30
10 30
15 20
15 20 25 30
15 30
25 30

Complejidad del tiempo: O(N 2 )

Espacio auxiliar: O(M+N)
Este artículo es una contribución de Gaurav Ahirwar . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente\
 

Publicación traducida automáticamente

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