Рубрики

Распечатать все последовательности заданной длины

Математика

Если даны два целых числа k и n, напишите функцию, которая печатает все последовательности длины k, состоящие из чисел 1,2..n. Вам нужно распечатать эти последовательности в отсортированном порядке.

Примеры:

Input: k = 2, n = 3

Output: 
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

Input:  k = 3, n = 4

Output: 
1 1 1
1 1 2
1 1 3
1 1 4
1 2 1
.....
.....
4 3 4
4 4 1
4 4 2
4 4 3
4 4 4

Метод 1 (простой и итеративный):
Простая идея напечатать все последовательности в отсортированном порядке — начать с {1 1… 1} и продолжать увеличивать последовательность, пока последовательность не становится {nn… n}. Ниже приводится подробный процесс.

1) Создайте выходной массив arr [] размера k. Инициализируйте массив как {1, 1… 1}.
2) Распечатать массив arr [].
3) Обновите массив arr [], чтобы он стал непосредственным преемником (подлежащим печати) самого себя. Например, непосредственным преемником {1, 1, 1} является {1, 1, 2}, непосредственным преемником {1, 4, 4} является {2, 1, 1} и непосредственным преемником {4, 4, 3 } есть {4 4 4}.
4) Повторите шаги 2 и 3, пока существует последующий массив. Другими словами, хотя выходной массив arr [] не становится {n, n .. n}

Теперь давайте поговорим о том, как изменить массив так, чтобы он содержал непосредственный преемник. По определению, непосредственный преемник должен иметь те же первые p членов и больший (p + 1) -й член. В исходном массиве (p + 1) -й член (или arr [p]) меньше n и всех членов после arr [p], т. Е. Arr [p + 1], arr [p + 2],… arr [ k-1] — это n.
Чтобы найти непосредственного преемника, мы находим точку p в ранее напечатанном массиве. Чтобы найти точку p, мы начинаем с крайней правой стороны и продолжаем двигаться, пока не найдем число arr [p] такое, что arr [p] будет меньше n (или не n). Как только мы находим такую точку, мы увеличиваем ее arr [p] на 1 и делаем все элементы после arr [p] равными 1, т. Е. Делаем arr [p + 1] = 1, arr [p + 2] = 1. . arr [k-1] = 1. Ниже приведены подробные шаги для получения немедленного преемника arr [].

1) Начните с самого правого члена arr [k-1] и двигайтесь влево. Найдите первый элемент arr [p], который не совпадает с n.
2) Увеличение обр [р] на 1
3) Начиная с arr [p + 1] до arr [k-1], установите значение всех слагаемых как 1.

C ++

// Программа CPP вышеуказанного подхода
#include<stdio.h>

  
/ * Вспомогательная функция, которая печатает заданный arr [] длины size * /

void printArray(int arr[], int size)

{

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

        printf("%d ", arr[i]);

    printf("\n");

    return;

}

  
/ * Эта функция возвращает 0, если больше нет последовательностей для печати, в противном случае

   изменяет arr [] так, чтобы arr [] содержал следующую последовательность для печати * /

int getSuccessor(int arr[], int k, int n)

{

    / * начать с самой правой стороны и найти первое число меньше n * /

    int p = k - 1;

    while (arr[p] == n)

        p--;

  

    / * Если в массиве все числа n, преемника нет, вернуть 0 * /

    if (p < 0)

        return 0;

  

    / * Обновить arr [], чтобы оно содержало преемник * /

    arr[p] = arr[p] + 1;

    for(int i = p + 1; i < k; i++)

        arr[i] = 1;

  

    return 1;

}

  
/ * Основная функция, которая печатает все последовательности от 1, 1, ..1 до n, n, ..n * /

void printSequences(int n, int k)

{

    int *arr = new int[k];

  

    / * Инициализировать текущую последовательность как первую последовательность для печати * /

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

        arr[i] = 1;

  

    / * Цикл прерывается, когда больше нет преемников для печати * /

    while(1)

    {

        / * Распечатать текущую последовательность * /

        printArray(arr, k);

  

        / * Обновить arr [], чтобы он содержал следующую последовательность для печати. И если

           нет больше последовательностей, чем разорвать цикл * /

        if(getSuccessor(arr, k, n) == 0)

          break;

    }

  

    delete(arr); // освобождаем динамически размещаемый массив

    return;

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

    int n = 3;

    int k = 2;

    printSequences(n, k);

    return 0;

}

Джава

// JAVA программа вышеуказанного подхода

  

class GFG 

{

  

    / * Вспомогательная функция, которая печатает заданный arr [] длины size * /

    static void printArray(int arr[], int size) 

    {

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

        {

            System.out.printf("%d ", arr[i]);

        }

        System.out.printf("\n");

        return;

    }

  

    / * Эта функция возвращает 0, если есть

    нет больше последовательностей для печати, в противном случае

    изменяет arr [] так, чтобы arr [] содержал

    следующая последовательность для печати * /

    static int getSuccessor(int arr[], int k, int n) 

    {

        / * начать с правой стороны и

        найти первое число меньше n * /

        int p = k - 1;

        while (arr[p] == n)

        {

            p--;

            if (p < 0)

            {

                break;

            }

        }

  

        / * Если все числа в массиве n

        тогда преемника нет, вернуть 0 * /

        if (p < 0)

        {

            return 0;

        }

  

        / * Обновить arr [], чтобы оно содержало преемник * /

        arr[p] = arr[p] + 1;

        for (int i = p + 1; i < k; i++) 

        {

            arr[i] = 1;

        }

        return 1;

    }

  

    / * Основная функция, которая печатает все

    последовательности от 1, 1, ..1 до n, n, ..n * /

    static void printSequences(int n, int k) 

    {

        int[] arr = new int[k];

  

        / * Инициализировать текущую последовательность как

        первая последовательность для печати * /

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

        {

            arr[i] = 1;

        }

  

        / * Цикл прерывается, когда есть

        больше нет преемников для печати * /

        while (true) 

        {

            / * Распечатать текущую последовательность * /

            printArray(arr, k);

  

            / * Обновить arr [], чтобы оно содержало

            следующая последовательность для печати. И если

            тогда больше нет последовательностей

            разорвать петлю * /

            if (getSuccessor(arr, k, n) == 0)

            {

                break;

            }

        }

    }

  

    / * Код водителя * /

    public static void main(String[] args) 

    {

        int n = 3;

        int k = 2;

        printSequences(n, k);

    }

}

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

C #

// C # программа вышеуказанного подхода

using System;

  

class GFG 

{

  

    / * Утилита, которая печатает

    заданный [] arr длины size * /

    static void printArray(int []arr, int size) 

    {

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

        {

            Console.Write("{0} ", arr[i]);

        }

        Console.Write("\n");

        return;

    }

  

    / * Эта функция возвращает 0, если есть

    нет больше последовательностей для печати, в противном случае

    изменяет [] arr так, чтобы [] arr содержал

    следующая последовательность для печати * /

    static int getSuccessor(int []arr, int k, int n) 

    {

        / * начать с правой стороны и

        найти первое число меньше n * /

        int p = k - 1;

        while (arr[p] == n)

        {

            p--;

            if (p < 0)

            {

                break;

            }

        }

  

        / * Если все числа в массиве n

        тогда преемника нет, вернуть 0 * /

        if (p < 0)

        {

            return 0;

        }

  

        / * Обновить [] arr, чтобы оно содержало преемника * /

        arr[p] = arr[p] + 1;

        for (int i = p + 1; i < k; i++) 

        {

            arr[i] = 1;

        }

        return 1;

    }

  

    / * Основная функция, которая печатает все

    последовательности от 1, 1, ..1 до n, n, ..n * /

    static void printSequences(int n, int k) 

    {

        int[] arr = new int[k];

  

        / * Инициализировать текущую последовательность как

        первая последовательность для печати * /

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

        {

            arr[i] = 1;

        }

  

        / * Цикл прерывается, когда есть

        больше нет преемников для печати * /

        while (true) 

        {

            / * Распечатать текущую последовательность * /

            printArray(arr, k);

  

            / * Обновить [] arr, чтобы оно содержало

            следующая последовательность для печати. И если

            тогда больше нет последовательностей

            разорвать петлю * /

            if (getSuccessor(arr, k, n) == 0)

            {

                break;

            }

        }

    }

  

    / * Код водителя * /

    public static void Main(String[] args) 

    {

        int n = 3;

        int k = 2;

        printSequences(n, k);

    }

}

  
// Этот код предоставлен Rajput-Ji

Выход:

1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

Сложность времени: Есть всего n ^ k последовательностей. Печать последовательности и поиск ее преемника занимают O (k) времени. Таким образом, временная сложность вышеописанной реализации составляет O (k * n ^ k).

Метод 2 (хитрый и рекурсивный)
Рекурсивная функция printSeptionsRecur генерирует и печатает все последовательности длиной k. Идея состоит в том, чтобы использовать еще один параметр index. Функция printSeptionsRecur хранит все термины в arr [] sane до индексации, обновляет значение по индексу и рекурсивно вызывает себя для получения дополнительных терминов после индексации.

C ++

// C ++ программа вышеуказанного подхода
#include<stdio.h>

  
/ * Вспомогательная функция, которая печатает заданный arr [] длины size * /

void printArray(int arr[], int size)

{

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

        printf("%d ", arr[i]);

    printf("\n");

    return;

}

  
/ * Основная функция, которая рекурсивно генерирует и печатает все последовательности

  длина к * /

void printSequencesRecur(int arr[], int n, int k, int index)

{

   int i;

   if (k == 0)

   {

     printArray(arr, index);

   }

   if (k > 0)

   {

      for(i = 1; i<=n; ++i)

      {

        arr[index] = i;

        printSequencesRecur(arr, n, k-1, index+1);

      }

   }

}

  

  
/ * Функция, которая использует printSeptionsRecur () для печати всех последовательностей

   от 1, 1, ..1 до n, n, ..n * /

void printSequences(int n, int k)

{

    int *arr = new int[k];

    printSequencesRecur(arr, n, k, 0);

  

    delete(arr); // освобождаем динамически размещаемый массив

    return;

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

    int n = 3;

    int k = 2;

    printSequences(n, k);

    return 0;

}

Джава

// Java-программа вышеуказанного подхода

  

class GfG {

  
/ * Вспомогательная функция, которая печатает заданный arr [] длины size * /

static void printArray(int arr[], int size) 

{ 

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

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

System.out.println();

    return; 

} 

  
/ * Основная функция, которая рекурсивно генерирует и печатает все последовательности
длина к * /

static void printSequencesRecur(int arr[], int n, int k, int index) 

{ 

int i; 

if (k == 0) 

{ 

    printArray(arr, index); 

} 

if (k > 0) 

{ 

    for(i = 1; i<=n; ++i) 

    { 

        arr[index] = i; 

        printSequencesRecur(arr, n, k-1, index+1); 

    } 

} 
} 

  

  
/ * Функция, которая использует printSeptionsRecur () для печати всех последовательностей
от 1, 1, ..1 до n, n, ..n * /

static void printSequences(int n, int k) 

{ 

    int arr[] = new int[k]; 

    printSequencesRecur(arr, n, k, 0); 

  

return ;

} 

  
/ * Программа драйвера для проверки вышеуказанных функций * /

public static void main(String[] args) 

{ 

    int n = 3; 

    int k = 2; 

    printSequences(n, k); 

} 
} 

python3

# Python3 программа вышеуказанного подхода

  
# Сервисная функция, которая печатает
# данное значение [] размера длины

def printArray(arr, size):

  

    for i in range(size): 

        print(arr[i], end = " "); 

    print("");

    return; 

  
# Основная функция, которая рекурсивно
# генерирует и печатает все последовательности
№ длины k

def printSequencesRecur(arr, n, k, index):

    if (k == 0):

        printArray(arr, index); 

  

    if (k > 0):

        for i in range(1, n + 1): 

            arr[index] = i; 

            printSequencesRecur(arr, n, k - 1,

                                    index + 1); 

  
# Функция, которая использует printSeptionsRecur () для
# печатает все последовательности от 1, 1, ..1 до n, n, ..n

def printSequences(n, k): 

    arr = [0] * n; 

    printSequencesRecur(arr, n, k, 0); 

  

    return;

  
Код водителя

n = 3; 

k = 2; 

printSequences(n, k); 

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

C #

// C # программа вышеуказанного подхода

using System;

  

class GFG 

{

  
/ * Утилита, которая печатает данный
arr [] длины size * /

static void printArray(int []arr, int size) 

{ 

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

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

    Console.WriteLine();

    return; 

} 

  
/ * Основная функция, которая рекурсивно генерирует
и печатает все последовательности длиной k * /

static void printSequencesRecur(int []arr, int n, 

                                int k, int index) 

{ 

    int i; 

    if (k == 0) 

    { 

        printArray(arr, index); 

    } 

    if (k > 0) 

    { 

        for(i = 1; i<=n; ++i) 

        { 

            arr[index] = i; 

            printSequencesRecur(arr, n, k - 1, index + 1); 

        } 

    } 

} 

  

  
/ * Функция, которая использует printSeptionsRecur () для
печатает все последовательности от 1, 1, ..1 до n, n, ..n * /

static void printSequences(int n, int k) 

{ 

    int[] arr = new int[k]; 

    printSequencesRecur(arr, n, k, 0); 

  

    return;

} 

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

public static void Main() 

{ 

    int n = 3; 

    int k = 2; 

    printSequences(n, k); 

} 
} 

  
// Этот код добавлен
// Аканкша Рай

PHP

<?php
// PHP программа вышеуказанного подхода

  
/ * Утилита, которая печатает
заданная arr [] длины size * /

function printArray($arr, $size) 

{ 

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

        echo $arr[$i] . " "; 

    echo "\n";

    return; 

} 

  
/ * Основная функция, которая рекурсивно генерирует
и печатает все последовательности длиной k * /

function printSequencesRecur($arr, $n, $k, $index) 

{ 

    if ($k == 0) 

    { 

        printArray($arr, $index); 

    } 

    if ($k > 0) 

    { 

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

        { 

            $arr[$index] = $i; 

            printSequencesRecur($arr, $n, 

                                $k - 1, $index + 1); 

        } 

    } 

} 

  

  
/ * Функция, которая использует printSeptionsRecur () для
печатает все последовательности от 1, 1, ..1 до n, n, ..n * /

function printSequences($n, $k) 

{ 

    $arr = array(); 

    printSequencesRecur($arr, $n, $k, 0); 

  

    return;

} 

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

$n = 3; 

$k = 2; 

printSequences($n, $k); 

  
// Этот код добавлен
// Аканкша Рай
?>


Выход:

1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

Сложность времени: есть n ^ k последовательностей, и печать последовательности занимает O (k) время. Таким образом, сложность времени O (k * n ^ k).

Спасибо mopurizwarriors за предложенный выше метод. Как предлагает alphayoung , мы можем избежать использования массивов для небольших последовательностей, которые могут помещаться в целое число. Ниже приводится реализация для того же.

С

// C программа вышеуказанного подхода
/ * Основная функция, которая генерирует и печатает все последовательности длиной k * /

void printSeqRecur(int num, int pos, int k, int n)

{

    if (pos == k) {

        printf("%d \n", num);

        return;

    }

    for (int i = 1; i <= n; i++) {

        printSeqRecur(num * 10 + i, pos + 1, k, n);

    }

}

  
/ * Функция, которая использует printSeptionsRecur () для печати всех последовательностей

   от 1, 1, ..1 до n, n, ..n * /

void printSequences(int k, int n)

{

    printSeqRecur(0, 0, k, n);

}

Джава

// Java-программа вышеуказанного подхода

  
/ * Основная функция, которая генерирует и печатает все последовательности длиной k * /

static void printSeqRecur(int num, int pos, int k, int n) 

{ 

    if (pos == k) { 

        System.out.print(num + " "); 

        return; 

    } 

    for (int i = 1; i <= n; i++) { 

        printSeqRecur(num * 10 + i, pos + 1, k, n); 

    } 

} 

  
/ * Функция, которая использует printSeptionsRecur () для печати всех последовательностей
от 1, 1, ..1 до n, n, ..n * /

static void printSequences(int k, int n) 

{ 

    printSeqRecur(0, 0, k, n); 

} 

python3

# Python программа вышеуказанного подхода
# Мы использовали номер вместо
# массивы для предотвращения линейного времени
# требуется для печати каждой строки

def printSeqRecur ( num , n, k ):

    if n == 0: # если общие цифры станут равными

                # к n, распечатать номер и вернуть

        print(num )

        return

          

    for _ in range(1, k + 1):

        printSeqRecur (num * 10 + _, n - 1, k) 

  
Код водителя

if __name__ == "__main__":

    k = 3 # длина k-арной строки

    n = 2 # строка может принимать значения

          # от 1,2,3 ... n

    printSeqRecur(0, n, k)

  
# Этот код добавлен
# Шивам Пурохит

C #

// C # программа вышеуказанного подхода

  
/ * Основная функция, которая генерирует
и печатает все последовательности длиной k * /

static void printSeqRecur(int num, int pos,

                            int k, int n) 

{ 

    if (pos == k) 

    { 

        Console.Write(num + " "); 

        return; 

    } 

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

    { 

        printSeqRecur(num * 10 + i, pos + 1, k, n); 

    } 

} 

  
/ * Функция, которая использует printSengthRecur ()
печатать все последовательности от 1, 1, ..1 до n, n, ..n * /

static void printSequences(int k, int n) 

{ 

    printSeqRecur(0, 0, k, n); 

}

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

PHP

<?php
// PHP программа вышеуказанного подхода
// Мы использовали номер вместо
// массивы для предотвращения линейного времени
// требуется напечатать каждую строку

function printSeqRecur ($num ,$n, $k)

{

    if ($n == 0)

    { 

        # if total digits become equal

        # to n, print the number and return

        print($num . "\n");

        return;

    }

          

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

        printSeqRecur($num * 10 + 

                      $i, $n - 1, $k); 

}

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

$k = 3; // длина k-арной строки

$n = 2; // строка может принимать значения

        // из 1,2,3 ... n

printSeqRecur(0, $n, $k);

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


Ссылки:
Алгоритмы и программирование: проблемы и решения Александр Шен

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

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

Распечатать все последовательности заданной длины

0.00 (0%) 0 votes