Dados dos enteros positivos n y k, imprima todas las secuencias crecientes de longitud k tal que los elementos en cada secuencia sean de los primeros n números naturales.
Ejemplos:
Input: k = 2, n = 3
Output: 1 2
1 3
2 3
Input: k = 5, n = 5
Output: 1 2 3 4 5
Input: k = 3, n = 5
Output: 1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
Recomendamos enfáticamente minimizar el navegador y probarlo usted mismo primero.
Es una buena pregunta recursiva. La idea es crear una array de longitudes k. La array almacena la secuencia actual. Para cada posición en la array, verificamos el elemento anterior y, uno por uno, colocamos todos los elementos mayores que el elemento anterior. Si no hay ningún elemento anterior (primera posición), ponemos todos los números del 1 al n.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to print all increasing sequences of
// length 'k' such that the elements in every sequence
// are from first 'n' natural numbers.
#include<iostream>
using namespace std;
// A utility function to print contents of arr[0..k-1]
void printArr(int arr[], int k)
{
for (int i=0; i<k; i++)
cout << arr[i] << " ";
cout << endl;
}
// A recursive function to print all increasing sequences
// of first n natural numbers. Every sequence should be
// length k. The array arr[] is used to store current
// sequence.
void printSeqUtil(int n, int k, int &len, int arr[])
{
// If length of current increasing sequence becomes k,
// print it
if (len == k)
{
printArr(arr, k);
return;
}
// Decide the starting number to put at current position:
// If length is 0, then there are no previous elements
// in arr[]. So start putting new numbers with 1.
// If length is not 0, then start from value of
// previous element plus 1.
int i = (len == 0)? 1 : arr[len-1] + 1;
// Increase length
len++;
// Put all numbers (which are greater than the previous
// element) at new position.
while (i<=n)
{
arr[len-1] = i;
printSeqUtil(n, k, len, arr);
i++;
}
// This is important. The variable 'len' is shared among
// all function calls in recursion tree. Its value must be
// brought back before next iteration of while loop
len--;
}
// This function prints all increasing sequences of
// first n natural numbers. The length of every sequence
// must be k. This function mainly uses printSeqUtil()
void printSeq(int n, int k)
{
int arr[k]; // An array to store individual sequences
int len = 0; // Initial length of current sequence
printSeqUtil(n, k, len, arr);
}
// Driver program to test above functions
int main()
{
int k = 3, n = 7;
printSeq(n, k);
return 0;
}
Java
// Java program to print all
// increasing sequences of
// length 'k' such that the
// elements in every sequence
// are from first 'n'
// natural numbers.
class GFG {
// A utility function to print
// contents of arr[0..k-1]
static void printArr(int[] arr, int k)
{
for (int i = 0; i < k; i++)
System.out.print(arr[i] + " ");
System.out.print("\n");
}
// A recursive function to print
// all increasing sequences
// of first n natural numbers.
// Every sequence should be
// length k. The array arr[] is
// used to store current sequence
static void printSeqUtil(int n, int k,
int len, int[] arr)
{
// If length of current increasing
// sequence becomes k, print it
if (len == k)
{
printArr(arr, k);
return;
}
// Decide the starting number
// to put at current position:
// If length is 0, then there
// are no previous elements
// in arr[]. So start putting
// new numbers with 1.
// If length is not 0,
// then start from value of
// previous element plus 1.
int i = (len == 0) ? 1 : arr[len - 1] + 1;
// Increase length
len++;
// Put all numbers (which are
// greater than the previous
// element) at new position.
while (i <= n)
{
arr[len - 1] = i;
printSeqUtil(n, k, len, arr);
i++;
}
// This is important. The
// variable 'len' is shared among
// all function calls in recursion
// tree. Its value must be
// brought back before next
// iteration of while loop
len--;
}
// This function prints all
// increasing sequences of
// first n natural numbers.
// The length of every sequence
// must be k. This function
// mainly uses printSeqUtil()
static void printSeq(int n, int k)
{
// An array to store
// individual sequences
int[] arr = new int[k];
// Initial length of
// current sequence
int len = 0;
printSeqUtil(n, k, len, arr);
}
// Driver Code
static public void main (String[] args)
{
int k = 3, n = 7;
printSeq(n, k);
}
}
// This code is contributed by Smitha.
Python3
# Python3 program to print all # increasing sequences of length # 'k' such that the elements in # every sequence are from first # 'n' natural numbers. # A utility function to # print contents of arr[0..k-1] def printArr(arr, k): for i in range(k): print(arr[i], end = " "); print(); # A recursive function to print # all increasing sequences of # first n natural numbers. Every # sequence should be length k. # The array arr[] is used to # store current sequence. def printSeqUtil(n, k,len1, arr): # If length of current # increasing sequence # becomes k, print it if (len1 == k): printArr(arr, k); return; # Decide the starting number # to put at current position: # If length is 0, then there # are no previous elements # in arr[]. So start putting # new numbers with 1. If length # is not 0, then start from value # of previous element plus 1. i = 1 if(len1 == 0) else (arr[len1 - 1] + 1); # Increase length len1 += 1; # Put all numbers (which are greater # than the previous element) at # new position. while (i <= n): arr[len1 - 1] = i; printSeqUtil(n, k, len1, arr); i += 1; # This is important. The variable # 'len' is shared among all function # calls in recursion tree. Its value # must be brought back before next # iteration of while loop len1 -= 1; # This function prints all increasing # sequences of first n natural numbers. # The length of every sequence must be # k. This function mainly uses printSeqUtil() def printSeq(n, k): arr = [0] * k; # An array to store # individual sequences len1 = 0; # Initial length of # current sequence printSeqUtil(n, k, len1, arr); # Driver Code k = 3; n = 7; printSeq(n, k); # This code is contributed by mits
C#
// C# program to print all
// increasing sequences of
// length 'k' such that the
// elements in every sequence
// are from first 'n'
// natural numbers.
using System;
class GFG {
// A utility function to print
// contents of arr[0..k-1]
static void printArr(int[] arr, int k)
{
for (int i = 0; i < k; i++)
Console.Write(arr[i] + " ");
Console.WriteLine();
}
// A recursive function to print
// all increasing sequences
// of first n natural numbers.
// Every sequence should be
// length k. The array arr[] is
// used to store current sequence
static void printSeqUtil(int n, int k,
int len, int[] arr)
{
// If length of current increasing
// sequence becomes k, print it
if (len == k)
{
printArr(arr, k);
return;
}
// Decide the starting number
// to put at current position:
// If length is 0, then there
// are no previous elements
// in arr[]. So start putting
// new numbers with 1.
// If length is not 0,
// then start from value of
// previous element plus 1.
int i = (len == 0) ? 1 : arr[len - 1] + 1;
// Increase length
len++;
// Put all numbers (which are
// greater than the previous
// element) at new position.
while (i <= n)
{
arr[len - 1] = i;
printSeqUtil(n, k, len, arr);
i++;
}
// This is important. The
// variable 'len' is shared among
// all function calls in recursion
// tree. Its value must be
// brought back before next
// iteration of while loop
len--;
}
// This function prints all
// increasing sequences of
// first n natural numbers.
// The length of every sequence
// must be k. This function
// mainly uses printSeqUtil()
static void printSeq(int n, int k)
{
// An array to store
// individual sequences
int[] arr = new int[k];
// Initial length of
// current sequence
int len = 0;
printSeqUtil(n, k, len, arr);
}
// Driver Code
static public void Main ()
{
int k = 3, n = 7;
printSeq(n, k);
}
}
// This code is contributed by Ajit.
PHP
<?php
// PHP program to print all
// increasing sequences of
// length 'k' such that the
// elements in every sequence
// are from first 'n' natural
// numbers.
// A utility function to
// print contents of arr[0..k-1]
function printArr($arr, $k)
{
for ($i = 0; $i < $k; $i++)
echo $arr[$i], " ";
echo "\n";
}
// A recursive function to
// print all increasing
// sequences of first n
// natural numbers. Every
// sequence should be length
// k. The array arr[] is used
// to store current sequence.
function printSeqUtil($n, $k,
$len, $arr)
{
// If length of current
// increasing sequence
// becomes k, print it
if ($len == $k)
{
printArr($arr, $k);
return;
}
// Decide the starting number
// to put at current position:
// If length is 0, then there
// are no previous elements
// in arr[]. So start putting
// new numbers with 1. If length
// is not 0, then start from value
// of previous element plus 1.
$i = ($len == 0)? 1 :
$arr[$len - 1] + 1;
// Increase length
$len++;
// Put all numbers (which are
// greater than the previous
// element) at new position.
while ($i <= $n)
{
$arr[$len-1] = $i;
printSeqUtil($n, $k,
$len, $arr);
$i++;
}
// This is important. The
// variable 'len' is shared
// among all function calls
// in recursion tree. Its
// value must be brought back
// before next iteration of
// while loop
$len--;
}
// This function prints all
// increasing sequences of
// first n natural numbers.
// The length of every sequence
// must be k. This function
// mainly uses printSeqUtil()
function printSeq($n, $k)
{
$arr = array(); // An array to store
// individual sequences
$len = 0; // Initial length of
// current sequence
printSeqUtil($n, $k,
$len, $arr);
}
// Driver Code
$k = 3;
$n = 7;
printSeq($n, $k);
// This code is contributed by Ajit
?>
Javascript
<script>
// Javascript program to print all
// increasing sequences of
// length 'k' such that the
// elements in every sequence
// are from first 'n'
// natural numbers.
// A utility function to print
// contents of arr[0..k-1]
function printArr(arr, k)
{
for(let i = 0; i < k; i++)
document.write(arr[i] + " ");
document.write("</br>");
}
// A recursive function to print
// all increasing sequences
// of first n natural numbers.
// Every sequence should be
// length k. The array arr[] is
// used to store current sequence
function printSeqUtil(n, k, len, arr)
{
// If length of current increasing
// sequence becomes k, print it
if (len == k)
{
printArr(arr, k);
return;
}
// Decide the starting number
// to put at current position:
// If length is 0, then there
// are no previous elements
// in arr[]. So start putting
// new numbers with 1.
// If length is not 0,
// then start from value of
// previous element plus 1.
let i = (len == 0) ? 1 : arr[len - 1] + 1;
// Increase length
len++;
// Put all numbers (which are
// greater than the previous
// element) at new position.
while (i <= n)
{
arr[len - 1] = i;
printSeqUtil(n, k, len, arr);
i++;
}
// This is important. The
// variable 'len' is shared among
// all function calls in recursion
// tree. Its value must be
// brought back before next
// iteration of while loop
len--;
}
// This function prints all
// increasing sequences of
// first n natural numbers.
// The length of every sequence
// must be k. This function
// mainly uses printSeqUtil()
function printSeq(n, k)
{
// An array to store
// individual sequences
let arr = new Array(k);
// Initial length of
// current sequence
let len = 0;
printSeqUtil(n, k, len, arr);
}
// Driver code
let k = 3, n = 7;
printSeq(n, k);
// This code is contributed by divyesh072019
</script>
Producción:
1 2 3 1 2 4 1 2 5 1 2 6 1 2 7 1 3 4 1 3 5 1 3 6 1 3 7 1 4 5 1 4 6 1 4 7 1 5 6 1 5 7 1 6 7 2 3 4 2 3 5 2 3 6 2 3 7 2 4 5 2 4 6 2 4 7 2 5 6 2 5 7 2 6 7 3 4 5 3 4 6 3 4 7 3 5 6 3 5 7 3 6 7 4 5 6 4 5 7 4 6 7 5 6 7
Complejidad Temporal: O(n*n!), ya que hay n! permutaciones y requiere O(n) tiempo para imprimir una permutación. T(n) = n * T(n-1) + O(1) cuando se reduce resultará en O(n*n!) tiempo.
Espacio auxiliar: O(n)
Este artículo es una contribución de Arjun . 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