Рубрики

Subarray / Substring vs Subsequence и программы для их генерации

Подмассив / Substring

Подбарьер является непрерывной частью массива. Массив, который находится внутри другого массива. Например, рассмотрим массив [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 ++ код для генерации всех возможных подмассивов / subArrays

    Сложность - O (n ^ 3) * /

#include<bits/stdc++.h>

using namespace std;

  
// Печатает все подмассивы в arr [0..n-1]

void subArray(int arr[], int n)

{

    // Выберите начальную точку

    for (int i=0; i <n; i++)

    {

        // Выбрать конечную точку

        for (int j=i; j<n; j++)

        {

            // Выводим подмассив между текущим запуском

            // и конечные точки

            for (int k=i; k<=j; k++)

                cout << arr[k] << " ";

  

            cout << endl;

        }

    }

}

  
// Драйвер программы

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-программа для генерации всех возможных подмассивов / subArrays
// Сложность - O (n ^ 3) * /

  

class Test

{

    static int arr[] = new int[]{1, 2, 3, 4};

      

    // Печатает все подмассивы в arr [0..n-1]

    static void subArray( int n)

    {

        // Выберите начальную точку

        for (int i=0; i <n; i++)

        {

            // Выбрать конечную точку

            for (int j=i; j<n; j++)

            {

                // Выводим подмассив между текущим запуском

                // и конечные точки

                for (int k=i; k<=j; k++)

                    System.out.print(arr[k]+" ");

            }

        }

    }

      

    // Метод драйвера для проверки вышеуказанной функции

    public static void main(String[] args) 

    {

        System.out.println("All Non-empty Subarrays");

        subArray(arr.length);

          

    }

}

python3

# Python3 код для генерации всего возможного
# subarrays / subArrays
# Сложность - O (n ^ 3)

  
# Печатает все подмассивы в arr [0..n-1]

def subArray(arr, n):

  

    # Выберите начальную точку

    for i in range(0,n):

  

        # Выберите конечную точку

        for j in range(i,n):

  

            # Печать подрешетки между

            # текущий старт

            # и конечные точки

            for k in range(i,j+1):

                print (arr[k],end=" ")

  

            print ("\n",end="")

  

              
# Драйверная программа

arr = [1, 2, 3, 4]

n = len(arr)

print ("All Non-empty Subarrays")

  
subArray(arr, n);

  
# Этот код предоставлен Shreyanshi.

C #

// C # программа для генерации всего
// возможные подмассивы / subArrays
// Сложность - O (n ^ 3)

using System;

  

class GFG

    static int []arr = new int[]{1, 2, 3, 4};

      

    // Печатает все подмассивы в arr [0..n-1]

    static void subArray( int n)

    {

          

        // Выберите начальную точку

        for (int i = 0; i < n; i++)

        {

              

            // Выбрать конечную точку

            for (int j = i; j < n; j++)

            {

                  

                // Выводим подмассив между текущими

                // начальная и конечная точки

                for (int k = i; k <= j; k++)

                    Console.Write(arr[k]+" ");

                    Console.WriteLine("");

            }

        }

    }

      

    // Код драйвера

    public static void Main() 

    {

        Console.WriteLine("All Non-empty Subarrays");

        subArray(arr.Length);

          

    }

  
}

  
// Этот код предоставлен Sam007.

PHP

<?php
// PHP код для генерации всего возможного
// сложность subarrays / subArrays - O (n ^ 3)

  
// Печатает все подмассивы
// в обр [0..n-1]

function subArray($arr, $n)

{

      

    // Выберите начальную точку

    for ($i = 0; $i < $n; $i++)

    {

          

        // Выбрать конечную точку

        for ($j = $i; $j < $n; $j++)

        {

              

            // Печать подмассива между

            // текущий старт

            // и конечные точки

            for ($k = $i; $k <= $j; $k++)

                echo $arr[$k] , " ";

  

            echo "\n";

        }

    }

}

  

    // Код драйвера

    $arr= array(1, 2, 3, 4);

    $n = sizeof($arr);

    echo "All Non-empty Subarrays\n";

    subArray($arr, $n);

      
// Этот ocde предоставлен m_kit
?>

Выход:

All Non-empty Subarrays
1 
1 2 
1 2 3 
1 2 3 4 
2 
2 3 
2 3 4 
3 
3 4 
4 

подпоследовательности
Подпоследовательность — это последовательность, которая может быть получена из другой последовательности нулем или несколькими элементами без изменения порядка оставшихся элементов.
Для того же примера есть 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), (2,3,4), (1,2,3,4). В более общем смысле, мы можем сказать, что для последовательности размером n мы можем иметь ( 2 n -1 ) непустых подпоследовательностей в общей сложности.

Пример строки для дифференциации:
рассмотрим строки «geeksforgeeks» и «gks». «Gks» — это подпоследовательность «geeksforgeeks», но не подстрока. «Гики» — это и подпоследовательность, и подмассив. Каждый подмассив является подпоследовательностью. Более конкретно, Подпоследовательность является обобщением подстроки.

Как генерировать все подпоследовательности?
Мы можем использовать алгоритм для генерации мощности для генерации всех подпоследовательностей.

C ++

/ * C ++ код для генерации всех возможных подпоследовательностей.

    Сложность времени O (n * 2 ^ n) * /

#include<bits/stdc++.h>

using namespace std;

  

void printSubsequences(int arr[], int n)

{

    / * Количество подпоследовательностей равно (2 ** n -1) * /

    unsigned int opsize = pow(2, n);

  

    / * Запуск от счетчика 000..1 до 111..1 * /

    for (int counter = 1; counter < opsize; counter++)

    {

        for (int j = 0; j < n; j++)

        {

            / * Проверить, установлен ли j-й бит в счетчике

                Если установлено, то вывести j-й элемент из arr [] * /

            if (counter & (1<<j))

                cout << arr[j] << " ";

        }

        cout << endl;

    }

}

  
// Драйвер программы

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-код для генерации всех возможных подпоследовательностей.

    Сложность времени O (n * 2 ^ n) * /

  

import java.math.BigInteger;

  

class Test

{

    static int arr[] = new int[]{1, 2, 3, 4};

      

    static void printSubsequences(int n)

    {

        / * Количество подпоследовательностей равно (2 ** n -1) * /

        int opsize = (int)Math.pow(2, n);

       

        / * Запуск от счетчика 000..1 до 111..1 * /

        for (int counter = 1; counter < opsize; counter++)

        {

            for (int j = 0; j < n; j++)

            {

                / * Проверить, установлен ли j-й бит в счетчике

                    Если установлено, то вывести j-й элемент из arr [] * /

        

                if (BigInteger.valueOf(counter).testBit(j))

                    System.out.print(arr[j]+" ");

            }

            System.out.println();

        }

    }

      

    // Метод драйвера для проверки вышеуказанной функции

    public static void main(String[] args) 

    {

        System.out.println("All Non-empty Subsequences");

        printSubsequences(arr.length);

    }

}

python3

# Python 3 код для генерации всего
# возможные подпоследовательности.
# Сложность времени O (n * 2 ^ n)

import math

  

def printSubsequences(arr, n) :

  

    Количество подпоследовательностей равно (2 ** n -1)

    opsize = math.pow(2, n)

  

    # Запуск от счетчика 000..1 до 111..1

    for counter in range( 1, (int)(opsize)) :

        for j in range(0, n) :

              

            # Проверьте, если J-й бит в счетчике

            # установлено Если установлено, выведите jth

            # элемент из arr []

            if (counter & (1<<j)) :

                print( arr[j], end =" ")

          

        print()

  
# Драйверная программа

arr = [1, 2, 3, 4]

n = len(arr)

print( "All Non-empty Subsequences")

  
printSubsequences(arr, n)

  
# Этот код предоставлен Никитой Тивари.

PHP

<?php
// PHP-код для генерации всего
// возможные подпоследовательности.
// Сложность времени O (n * 2 ^ n)

  

function printSubsequences($arr, $n)

{

    // Количество подпоследовательностей

    // есть (2 ** n -1)

    $opsize = pow(2, $n);

  

    / * Беги от счетчика

    От 000..1 до 111..1 * /

    for ($counter = 1; 

         $counter < $opsize

         $counter++)

    {

        for ( $j = 0; $j < $n; $j++)

        {

             / * Проверить, включен ли j-й бит

                счетчик установлен

                Если установлено, то выведите jth

                элемент из arr [] * /

            if ($counter & (1 << $j))

                echo $arr[$j], " ";

        }

        echo "\n";

    }

}

  
// Код драйвера

$arr = array (1, 2, 3, 4);

$n = sizeof($arr);

  

echo "All Non-empty Subsequences\n";

  

printSubsequences($arr, $n);

      
// Этот код предоставлен ajit
?>

Выход:

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

Эта статья предоставлена Харшитом Гуптой . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Subarray / Substring vs Subsequence и программы для их генерации

0.00 (0%) 0 votes