子阵列/子串
null
子阵列是一个 相接的 阵列的一部分。位于另一个数组中的数组。例如，考虑数组[1, 2, 3，4 ]，有10个非空子数组。子阵是（1）、（2）、（3）、（4）、（1,2）、（2,3）、（3,4）、（1,2,3）、（2,3,4）和（1,2,3,4）。通常，对于大小为n的数组/字符串，有 n*（n+1）/2 非空子阵列/子字符串。
如何生成所有子阵列？ 我们可以运行两个嵌套循环，外循环选择起始元素，内循环将选择元素右侧的所有元素视为子数组的结束元素。
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" ; subArray(arr, n); return 0; } |
JAVA
// Java program toto 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 ( "" ,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 toto 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 "" ; } } } // Driver Code $arr = array (1, 2, 3, 4); $n = sizeof( $arr ); echo "All Non-empty Subarrays" ; subArray( $arr , $n ); // This code is contributed by m_kit ?> |
Javascript
<script> // Javascript program toto 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> |
输出：
All Non-empty Subarrays1 1 2 1 2 3 1 2 3 4 2 2 3 2 3 4 3 3 4 4
时间复杂度：0（n^3）
空间复杂度：0（1）
子序列 子序列是可以通过移除零个或多个元素而从另一个序列派生的序列，而不改变其余元素的顺序。 对于同一个例子，有15个子序列。它们是（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）、（1,3,4）、（2,3,4）、（1,2,4）、（1,3,4）。更一般地说，对于大小为n的序列，我们可以( 2. N -1 )共有非空子序列。 要区分的字符串示例： 考虑字符串“GeksFoeGekes”和“GKS”。“gks”是“Geeksforgeks”的子序列，但不是子字符串。“极客”既是子序列又是子阵列。每个子阵列都是一个子序列。更具体地说， 子序列是子串的推广。
子数组或子字符串始终是连续的，但子序列不必是连续的。也就是说，子序列不需要占据原始序列中的连续位置。但我们可以说，连续子序列和子阵列都是相同的。
如何生成所有子序列？ 我们可以使用 发电机组的算法 用于生成所有子序列。
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" ; 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 "" ; } } // Driver Code $arr = array (1, 2, 3, 4); $n = sizeof( $arr ); echo "All Non-empty Subsequences" ; 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> |
输出：
All Non-empty Subsequences1 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
时间复杂度：0（n*（2^n））
空间复杂度：0（1） 本文由 哈希特·古普塔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
