Subarreglo/Substring
Un subarreglo es una parte contigua de un arreglo. Una array que está dentro de otra array. Por ejemplo, considere la array [1, 2, 3, 4], hay 10 sub-arrays no vacías. Los subarreglos son (1), (2), (3), (4), (1,2), (2,3), (3,4), (1,2,3), (2,3, 4) y (1,2,3,4). En general, para una array/string de tamaño n, hay n*(n+1)/2 subarreglos/substrings no vacíos.
¿Cómo generar todos los subarreglos?
Podemos ejecutar dos bucles anidados, el bucle exterior elige el elemento inicial y el bucle interior considera todos los elementos a la derecha de los elementos seleccionados como elementos finales del subarreglo.
C++
/* C++ code to generate all possible subarrays/subArrays
Complexity- O(n^3) */
#include<bits/stdc++.h>
using namespace std;
// Prints all subarrays in arr[0..n-1]
void subArray(int arr[], int n)
{
// Pick starting point
for (int i=0; i <n; i++)
{
// Pick ending point
for (int j=i; j<n; j++)
{
// Print subarray between current starting
// and ending points
for (int k=i; k<=j; k++)
cout << arr[k] << " ";
cout << endl;
}
}
}
// Driver program
int main()
{
int arr[] = {1, 2, 3, 4};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "All Non-empty Subarrays\n";
subArray(arr, n);
return 0;
}
Java
// Java program to generate all possible subarrays/subArrays
// Complexity- O(n^3) */
class Test
{
static int arr[] = new int[]{1, 2, 3, 4};
// Prints all subarrays in arr[0..n-1]
static void subArray( int n)
{
// Pick starting point
for (int i=0; i <n; i++)
{
// Pick ending point
for (int j=i; j<n; j++)
{
// Print subarray between current starting
// and ending points
for (int k=i; k<=j; k++)
System.out.print(arr[k]+" ");
}
}
}
// Driver method to test the above function
public static void main(String[] args)
{
System.out.println("All Non-empty Subarrays");
subArray(arr.length);
}
}
Python3
# Python3 code to generate all possible
# subarrays/subArrays
# Complexity- O(n^3)
# Prints all subarrays in arr[0..n-1]
def subArray(arr, n):
# Pick starting point
for i in range(0,n):
# Pick ending point
for j in range(i,n):
# Print subarray between
# current starting
# and ending points
for k in range(i,j+1):
print (arr[k],end=" ")
print ("\n",end="")
# Driver program
arr = [1, 2, 3, 4]
n = len(arr)
print ("All Non-empty Subarrays")
subArray(arr, n);
# This code is contributed by Shreyanshi.
C#
// C# program to generate all
// possible subarrays/subArrays
// Complexity- O(n^3)
using System;
class GFG
{
static int []arr = new int[]{1, 2, 3, 4};
// Prints all subarrays in arr[0..n-1]
static void subArray( int n)
{
// Pick starting point
for (int i = 0; i < n; i++)
{
// Pick ending point
for (int j = i; j < n; j++)
{
// Print subarray between current
// starting and ending points
for (int k = i; k <= j; k++)
Console.Write(arr[k]+" ");
Console.WriteLine("");
}
}
}
// Driver Code
public static void Main()
{
Console.WriteLine("All Non-empty Subarrays");
subArray(arr.Length);
}
}
// This code is contributed by Sam007.
PHP
<?php
// PHP code to generate all possible
// subarrays/subArrays Complexity- O(n^3)
// Prints all subarrays
// in arr[0..n-1]
function subArray($arr, $n)
{
// Pick starting point
for ($i = 0; $i < $n; $i++)
{
// Pick ending point
for ($j = $i; $j < $n; $j++)
{
// Print subarray between
// current starting
// and ending points
for ($k = $i; $k <= $j; $k++)
echo $arr[$k] , " ";
echo "\n";
}
}
}
// Driver Code
$arr= array(1, 2, 3, 4);
$n = sizeof($arr);
echo "All Non-empty Subarrays\n";
subArray($arr, $n);
// This code is contributed by m_kit
?>
Javascript
<script>
// Javascript program to generate all
// possible subarrays/subArrays
// Complexity- O(n^3)
let arr = [1, 2, 3, 4];
// Prints all subarrays in arr[0..n-1]
function subArray(n)
{
// Pick starting point
for(let i = 0; i < n; i++)
{
// Pick ending point
for(let j = i; j < n; j++)
{
// Print subarray between current
// starting and ending points
for(let k = i; k <= j; k++)
document.write(arr[k] + " ");
document.write("</br>");
}
}
}
// Driver code
document.write("All Non-empty Subarrays" + "</br>");
subArray(arr.length);
// This code is contributed by suresh07
</script>
Producción:
All Non-empty Subarrays 1 1 2 1 2 3 1 2 3 4 2 2 3 2 3 4 3 3 4 4
Complejidad de tiempo: 0 (n ^ 3)
Complejidad espacial: 0(1)
Subsecuencia
Una subsecuencia es una secuencia que se puede derivar de otra secuencia eliminando cero o más elementos, sin cambiar el orden de los elementos restantes.
Para el mismo ejemplo, hay 15 subsecuencias. Ellos son (1), (2), (3), (4), (1,2), (1,3), (1,4), (2,3), (2,4), (3 ,4), (1,2,3), (1,2,4), (1,3,4), (2,3,4), (1,2,3,4). Más generalmente, podemos decir que para una secuencia de tamaño n, podemos tener ( 2 n -1 ) subsecuencias no vacías en total.
Un ejemplo de string para diferenciar: Considere las strings «geeksforgeeks» y «gks». «gks» es una subsecuencia de «geeksforgeeks», pero no una substring. “geeks” es a la vez una subsecuencia y un subarreglo. Todo subarreglo es una subsecuencia. Más específicamente,La subsecuencia es una generalización de substring.
Un subarreglo o substring siempre será contiguo, pero una subsecuencia no necesita ser contigua. Es decir, no se requiere que las subsecuencias ocupen posiciones consecutivas dentro de las secuencias originales. Pero podemos decir que tanto la subsecuencia contigua como el subarreglo son lo mismo.
¿Cómo generar todas las subsecuencias?
Podemos usar un algoritmo para generar un conjunto de potencia para la generación de todas las subsecuencias.
C++
/* C++ code to generate all possible subsequences.
Time Complexity O(n * 2^n) */
#include<bits/stdc++.h>
using namespace std;
void printSubsequences(int arr[], int n)
{
/* Number of subsequences is (2**n -1)*/
unsigned int opsize = pow(2, n);
/* Run from counter 000..1 to 111..1*/
for (int counter = 1; counter < opsize; counter++)
{
for (int j = 0; j < n; j++)
{
/* Check if jth bit in the counter is set
If set then print jth element from arr[] */
if (counter & (1<<j))
cout << arr[j] << " ";
}
cout << endl;
}
}
// Driver program
int main()
{
int arr[] = {1, 2, 3, 4};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "All Non-empty Subsequences\n";
printSubsequences(arr, n);
return 0;
}
Java
/* Java code to generate all possible subsequences.
Time Complexity O(n * 2^n) */
import java.math.BigInteger;
class Test
{
static int arr[] = new int[]{1, 2, 3, 4};
static void printSubsequences(int n)
{
/* Number of subsequences is (2**n -1)*/
int opsize = (int)Math.pow(2, n);
/* Run from counter 000..1 to 111..1*/
for (int counter = 1; counter < opsize; counter++)
{
for (int j = 0; j < n; j++)
{
/* Check if jth bit in the counter is set
If set then print jth element from arr[] */
if (BigInteger.valueOf(counter).testBit(j))
System.out.print(arr[j]+" ");
}
System.out.println();
}
}
// Driver method to test the above function
public static void main(String[] args)
{
System.out.println("All Non-empty Subsequences");
printSubsequences(arr.length);
}
}
Python3
# Python3 code to generate all # possible subsequences. # Time Complexity O(n * 2 ^ n) import math def printSubsequences(arr, n) : # Number of subsequences is (2**n -1) opsize = math.pow(2, n) # Run from counter 000..1 to 111..1 for counter in range( 1, (int)(opsize)) : for j in range(0, n) : # Check if jth bit in the counter # is set If set then print jth # element from arr[] if (counter & (1<<j)) : print( arr[j], end =" ") print() # Driver program arr = [1, 2, 3, 4] n = len(arr) print( "All Non-empty Subsequences") printSubsequences(arr, n) # This code is contributed by Nikita Tiwari.
C#
// C# code to generate all possible subsequences.
// Time Complexity O(n * 2^n)
using System;
class GFG{
static void printSubsequences(int[] arr, int n)
{
// Number of subsequences is (2**n -1)
int opsize = (int)Math.Pow(2, n);
// Run from counter 000..1 to 111..1
for(int counter = 1; counter < opsize; counter++)
{
for(int j = 0; j < n; j++)
{
// Check if jth bit in the counter is set
// If set then print jth element from arr[]
if ((counter & (1 << j)) != 0)
Console.Write(arr[j] + " ");
}
Console.WriteLine();
}
}
// Driver Code
static void Main()
{
int[] arr = { 1, 2, 3, 4 };
int n = arr.Length;
Console.WriteLine("All Non-empty Subsequences");
printSubsequences(arr, n);
}
}
// This code is contributed by divyesh072019
PHP
<?php
// PHP code to generate all
// possible subsequences.
// Time Complexity O(n * 2^n)
function printSubsequences($arr, $n)
{
// Number of subsequences
// is (2**n -1)
$opsize = pow(2, $n);
/* Run from counter
000..1 to 111..1*/
for ($counter = 1;
$counter < $opsize;
$counter++)
{
for ( $j = 0; $j < $n; $j++)
{
/* Check if jth bit in
the counter is set
If set then print jth
element from arr[] */
if ($counter & (1 << $j))
echo $arr[$j], " ";
}
echo "\n";
}
}
// Driver Code
$arr = array (1, 2, 3, 4);
$n = sizeof($arr);
echo "All Non-empty Subsequences\n";
printSubsequences($arr, $n);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript code to generate all possible subsequences.
// Time Complexity O(n * 2^n)
function printSubsequences(arr, n)
{
// Number of subsequences is (2**n -1)
let opsize = parseInt(Math.pow(2, n), 10);
// Run from counter 000..1 to 111..1
for(let counter = 1; counter < opsize; counter++)
{
for(let j = 0; j < n; j++)
{
// Check if jth bit in the counter is set
// If set then print jth element from arr[]
if ((counter & (1 << j)) != 0)
document.write(arr[j] + " ");
}
document.write("</br>");
}
}
let arr = [ 1, 2, 3, 4 ];
let n = arr.length;
document.write("All Non-empty Subsequences" + "</br>");
printSubsequences(arr, n);
// This code is contributed by divyeshrabadiya07.
</script>
Producción:
All Non-empty Subsequences 1 2 1 2 3 1 3 2 3 1 2 3 4 1 4 2 4 1 2 4 3 4 1 3 4 2 3 4 1 2 3 4
Complejidad de tiempo: 0(n*(2^n))
Complejidad espacial: 0(1)
Este artículo es una contribución de Harshit Gupta . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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