Dados dos enteros k y n, escribe una función que imprima todas las secuencias de longitud k compuestas por los números 1,2…n. Debe imprimir estas secuencias en orden ordenado.
Ejemplos:
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
Método 1 (simple e iterativo):
la idea simple de imprimir todas las secuencias en orden ordenado es comenzar desde {1 1 … 1} y seguir incrementando la secuencia mientras la secuencia no se convierte en {nn … n}. A continuación se muestra el proceso detallado.
1) Cree una array de salida arr[] de tamaño k. Inicialice la array como {1, 1…1}.
2) Imprima la array arr[].
3) Actualice la array arr[] para que se convierta en sucesor inmediato (para ser impreso) de sí mismo. Por ejemplo, el sucesor inmediato de {1, 1, 1} es {1, 1, 2}, el sucesor inmediato de {1, 4, 4} es {2, 1, 1} y el sucesor inmediato de {4, 4, 3 } es {4 4 4}.
4) Repita los pasos 2 y 3 mientras haya una array sucesora. En otras palabras, mientras que la array de salida arr[] no se convierte en {n, n .. n}
Ahora hablemos de cómo modificar la array para que contenga un sucesor inmediato. Por definición, el sucesor inmediato debe tener los mismos primeros términos p y un (p+l)ésimo término mayor. En la array original, (p+1) el término (o arr[p]) es más pequeño que n y todos los términos después de arr[p], es decir, arr[p+1], arr[p+2], … arr[ k-1] son n.
Para encontrar el sucesor inmediato, buscamos el punto p en la array previamente impresa. Para encontrar el punto p, comenzamos desde el extremo derecho y seguimos moviéndonos hasta encontrar un número arr[p] tal que arr[p] sea menor que n (o no n). Una vez que encontramos dicho punto, lo incrementamos arr[p] en 1 y hacemos que todos los elementos después de arr[p] sean 1, es decir, hacemos arr[p+1] = 1, arr[p+2] = 1 . .arr[k-1] = 1. Los siguientes son los pasos detallados para obtener el sucesor inmediato de arr[]
1) Comience desde el término más a la derecha arr[k-1] y muévase hacia la izquierda. Encuentra el primer elemento arr[p] que no es igual a n.
2) Incremente arr[p] en 1
3) Comenzando desde arr[p+1] hasta arr[k-1], establezca el valor de todos los términos en 1.
C++
// CPP program of above approach
#include<iostream>
using namespace std;
/* A utility function that prints a given arr[] of length size*/
void printArray(int arr[], int size)
{
for(int i = 0; i < size; i++)
cout <<" "<< arr[i];
cout <<"\n";
return;
}
/* This function returns 0 if there are no more sequences to be printed, otherwise
modifies arr[] so that arr[] contains next sequence to be printed */
int getSuccessor(int arr[], int k, int n)
{
/* start from the rightmost side and find the first number less than n */
int p = k - 1;
while (arr[p] == n)
p--;
/* If all numbers are n in the array then there is no successor, return 0 */
if (p < 0)
return 0;
/* Update arr[] so that it contains successor */
arr[p] = arr[p] + 1;
for(int i = p + 1; i < k; i++)
arr[i] = 1;
return 1;
}
/* The main function that prints all sequences from 1, 1, ..1 to n, n, ..n */
void printSequences(int n, int k)
{
int *arr = new int[k];
/* Initialize the current sequence as the first sequence to be printed */
for(int i = 0; i < k; i++)
arr[i] = 1;
/* The loop breaks when there are no more successors to be printed */
while(1)
{
/* Print the current sequence */
printArray(arr, k);
/* Update arr[] so that it contains next sequence to be printed. And if
there are no more sequences then break the loop */
if(getSuccessor(arr, k, n) == 0)
break;
}
delete(arr); // free dynamically allocated array
return;
}
/* Driver Program to test above functions */
int main()
{
int n = 3;
int k = 2;
printSequences(n, k);
return 0;
}
// this code is contributed by shivanisinghss2110
C
// CPP program of above approach
#include<stdio.h>
/* A utility function that prints a given arr[] of length size*/
void printArray(int arr[], int size)
{
for(int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
return;
}
/* This function returns 0 if there are no more sequences to be printed, otherwise
modifies arr[] so that arr[] contains next sequence to be printed */
int getSuccessor(int arr[], int k, int n)
{
/* start from the rightmost side and find the first number less than n */
int p = k - 1;
while (arr[p] == n)
p--;
/* If all numbers are n in the array then there is no successor, return 0 */
if (p < 0)
return 0;
/* Update arr[] so that it contains successor */
arr[p] = arr[p] + 1;
for(int i = p + 1; i < k; i++)
arr[i] = 1;
return 1;
}
/* The main function that prints all sequences from 1, 1, ..1 to n, n, ..n */
void printSequences(int n, int k)
{
int *arr = new int[k];
/* Initialize the current sequence as the first sequence to be printed */
for(int i = 0; i < k; i++)
arr[i] = 1;
/* The loop breaks when there are no more successors to be printed */
while(1)
{
/* Print the current sequence */
printArray(arr, k);
/* Update arr[] so that it contains next sequence to be printed. And if
there are no more sequences then break the loop */
if(getSuccessor(arr, k, n) == 0)
break;
}
delete(arr); // free dynamically allocated array
return;
}
/* Driver Program to test above functions */
int main()
{
int n = 3;
int k = 2;
printSequences(n, k);
return 0;
}
Java
// JAVA program of above approach
class GFG
{
/* A utility function that prints a given arr[] of length 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;
}
/* This function returns 0 if there are
no more sequences to be printed, otherwise
modifies arr[] so that arr[] contains
next sequence to be printed */
static int getSuccessor(int arr[], int k, int n)
{
/* start from the rightmost side and
find the first number less than n */
int p = k - 1;
while (arr[p] == n)
{
p--;
if (p < 0)
{
break;
}
}
/* If all numbers are n in the array
then there is no successor, return 0 */
if (p < 0)
{
return 0;
}
/* Update arr[] so that it contains successor */
arr[p] = arr[p] + 1;
for (int i = p + 1; i < k; i++)
{
arr[i] = 1;
}
return 1;
}
/* The main function that prints all
sequences from 1, 1, ..1 to n, n, ..n */
static void printSequences(int n, int k)
{
int[] arr = new int[k];
/* Initialize the current sequence as
the first sequence to be printed */
for (int i = 0; i < k; i++)
{
arr[i] = 1;
}
/* The loop breaks when there are
no more successors to be printed */
while (true)
{
/* Print the current sequence */
printArray(arr, k);
/* Update arr[] so that it contains
next sequence to be printed. And if
there are no more sequences then
break the loop */
if (getSuccessor(arr, k, n) == 0)
{
break;
}
}
}
/* Driver code */
public static void main(String[] args)
{
int n = 3;
int k = 2;
printSequences(n, k);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program of above approach # A utility function that prints # a given arr[] of length size# def printArray(arr, size): for i in range(size): print(arr[i], end = " ") print() return # This function returns 0 if there are # no more sequences to be printed, otherwise # modifies arr[] so that arr[] contains # next sequence to be printed # def getSuccessor(arr, k, n): # start from the rightmost side and # find the first number less than n p = k - 1 while (arr[p] == n and 0 <= p < k): p -= 1 # If all numbers are n in the array # then there is no successor, return 0 if (p < 0): return 0 # Update arr[] so that it contains successor arr[p] = arr[p] + 1 i = p + 1 while(i < k): arr[i] = 1 i += 1 return 1 # The main function that prints all sequences # from 1, 1, ..1 to n, n, ..n def printSequences(n, k): arr = [0] * k # Initialize the current sequence as # the first sequence to be printed # for i in range(k): arr[i] = 1 # The loop breaks when there are # no more successors to be printed while(1): # Print the current sequence printArray(arr, k) # Update arr[] so that it contains # next sequence to be printed. And if # there are no more sequences then # break the loop if(getSuccessor(arr, k, n) == 0): break return # Driver code n = 3 k = 2 printSequences(n, k) # This code is contributed by shubhamsingh10
C#
// C# program of above approach
using System;
class GFG
{
/* A utility function that prints
a given []arr of length size*/
static void printArray(int []arr, int size)
{
for (int i = 0; i < size; i++)
{
Console.Write("{0} ", arr[i]);
}
Console.Write("\n");
return;
}
/* This function returns 0 if there are
no more sequences to be printed, otherwise
modifies []arr so that []arr contains
next sequence to be printed */
static int getSuccessor(int []arr, int k, int n)
{
/* start from the rightmost side and
find the first number less than n */
int p = k - 1;
while (arr[p] == n)
{
p--;
if (p < 0)
{
break;
}
}
/* If all numbers are n in the array
then there is no successor, return 0 */
if (p < 0)
{
return 0;
}
/* Update []arr so that it contains successor */
arr[p] = arr[p] + 1;
for (int i = p + 1; i < k; i++)
{
arr[i] = 1;
}
return 1;
}
/* The main function that prints all
sequences from 1, 1, ..1 to n, n, ..n */
static void printSequences(int n, int k)
{
int[] arr = new int[k];
/* Initialize the current sequence as
the first sequence to be printed */
for (int i = 0; i < k; i++)
{
arr[i] = 1;
}
/* The loop breaks when there are
no more successors to be printed */
while (true)
{
/* Print the current sequence */
printArray(arr, k);
/* Update []arr so that it contains
next sequence to be printed. And if
there are no more sequences then
break the loop */
if (getSuccessor(arr, k, n) == 0)
{
break;
}
}
}
/* Driver code */
public static void Main(String[] args)
{
int n = 3;
int k = 2;
printSequences(n, k);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript program of above approach
/* A utility function that prints a
given arr of length size*/
function printArray(arr , size)
{
for (i = 0; i < size; i++)
{
document.write(arr[i]+" ");
}
document.write("<br>");
return;
}
/* This function returns 0 if there are
no more sequences to be printed, otherwise
modifies arr so that arr contains
next sequence to be printed */
function getSuccessor(arr , k , n)
{
/* start from the rightmost side and
find the first number less than n */
var p = k - 1;
while (arr[p] == n)
{
p--;
if (p < 0)
{
break;
}
}
/* If all numbers are n in the array
then there is no successor, return 0 */
if (p < 0)
{
return 0;
}
/* Update arr so that it contains successor */
arr[p] = arr[p] + 1;
for (i = p + 1; i < k; i++)
{
arr[i] = 1;
}
return 1;
}
/* The main function that prints all
sequences from 1, 1, ..1 to n, n, ..n */
function printSequences(n , k)
{
var arr = Array.from({length: k}, (_, i) => 0);
/* Initialize the current sequence as
the first sequence to be printed */
for (i = 0; i < k; i++)
{
arr[i] = 1;
}
/* The loop breaks when there are
no more successors to be printed */
while (true)
{
/* Print the current sequence */
printArray(arr, k);
/* Update arr so that it contains
next sequence to be printed. And if
there are no more sequences then
break the loop */
if (getSuccessor(arr, k, n) == 0)
{
break;
}
}
}
/* Driver code */
var n = 3;
var k = 2;
printSequences(n, k);
// This code is contributed by 29AjayKumar
</script>
Producción:
1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
Complejidad de tiempo: Hay un total de n^k secuencias. Imprimir una secuencia y encontrar su sucesor toma tiempo O(k). Entonces, la complejidad del tiempo de la implementación anterior es O (k * n ^ k).
Espacio auxiliar: O(k)
Método 2 (complicado y recursivo)
La función recursiva printSequencesRecur genera e imprime todas las secuencias de longitud k. La idea es usar un índice de parámetro más. La función printSequencesRecur mantiene todos los términos en arr[] cuerdos hasta el índice, actualiza el valor en el índice y recursivamente se llama a sí mismo para obtener más términos después del índice.
C++
// C++ program of above approach
#include<iostream>
using namespace std;
/* A utility function that prints a given arr[] of length size*/
void printArray(int arr[], int size)
{
for(int i = 0; i < size; i++)
cout<< " "<< arr[i];
cout<<"\n";
return;
}
/* The core function that recursively generates and prints all sequences of
length k */
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);
}
}
}
/* A function that uses printSequencesRecur() to prints all sequences
from 1, 1, ..1 to n, n, ..n */
void printSequences(int n, int k)
{
int *arr = new int[k];
printSequencesRecur(arr, n, k, 0);
delete(arr); // free dynamically allocated array
return;
}
/* Driver Program to test above functions */
int main()
{
int n = 3;
int k = 2;
printSequences(n, k);
return 0;
}
// This code is contributed by shivanisinghss2110
C
// C++ program of above approach
#include<stdio.h>
/* A utility function that prints a given arr[] of length size*/
void printArray(int arr[], int size)
{
for(int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
return;
}
/* The core function that recursively generates and prints all sequences of
length k */
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);
}
}
}
/* A function that uses printSequencesRecur() to prints all sequences
from 1, 1, ..1 to n, n, ..n */
void printSequences(int n, int k)
{
int *arr = new int[k];
printSequencesRecur(arr, n, k, 0);
delete(arr); // free dynamically allocated array
return;
}
/* Driver Program to test above functions */
int main()
{
int n = 3;
int k = 2;
printSequences(n, k);
return 0;
}
Java
// Java program of above approach
class GfG {
/* A utility function that prints a given arr[] of length size*/
static void printArray(int arr[], int size)
{
for(int i = 0; i < size; i++)
System.out.print(arr[i] + " ");
System.out.println();
return;
}
/* The core function that recursively generates and prints all sequences of
length 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);
}
}
}
/* A function that uses printSequencesRecur() to prints all sequences
from 1, 1, ..1 to n, n, ..n */
static void printSequences(int n, int k)
{
int arr[] = new int[k];
printSequencesRecur(arr, n, k, 0);
return ;
}
/* Driver Program to test above functions */
public static void main(String[] args)
{
int n = 3;
int k = 2;
printSequences(n, k);
}
}
Python3
# Python3 program of above approach
# A utility function that prints a
# given arr[] of length size
def printArray(arr, size):
for i in range(size):
print(arr[i], end = " ");
print("");
return;
# The core function that recursively
# generates and prints all sequences
# of length 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);
# A function that uses printSequencesRecur() to
# prints all sequences from 1, 1, ..1 to n, n, ..n
def printSequences(n, k):
arr = [0] * n;
printSequencesRecur(arr, n, k, 0);
return;
# Driver Code
n = 3;
k = 2;
printSequences(n, k);
# This code is contributed mits
C#
// C# program of above approach
using System;
class GFG
{
/* A utility function that prints a given
arr[] of length size*/
static void printArray(int []arr, int size)
{
for(int i = 0; i < size; i++)
Console.Write(arr[i] + " ");
Console.WriteLine();
return;
}
/* The core function that recursively generates
and prints all sequences of length 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);
}
}
}
/* A function that uses printSequencesRecur() to
prints all sequences from 1, 1, ..1 to n, n, ..n */
static void printSequences(int n, int k)
{
int[] arr = new int[k];
printSequencesRecur(arr, n, k, 0);
return;
}
// Driver Code
public static void Main()
{
int n = 3;
int k = 2;
printSequences(n, k);
}
}
// This code is contributed
// by Akanksha Rai
PHP
<?php
// PHP program of above approach
/* A utility function that prints a
given arr[] of length size*/
function printArray($arr, $size)
{
for($i = 0; $i < $size; $i++)
echo $arr[$i] . " ";
echo "\n";
return;
}
/* The core function that recursively generates
and prints all sequences of length 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);
}
}
}
/* A function that uses printSequencesRecur() to
prints all sequences from 1, 1, ..1 to n, n, ..n */
function printSequences($n, $k)
{
$arr = array();
printSequencesRecur($arr, $n, $k, 0);
return;
}
// Driver Code
$n = 3;
$k = 2;
printSequences($n, $k);
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
// javascript program of above approach
/* A utility function that prints a given arr of length size*/
function printArray(arr, size)
{
for(i = 0; i < size; i++)
document.write(arr[i] + " ");
document.write("<br>");
return;
}
/* The core function that recursively
generates and prints all sequences of
length k */
function printSequencesRecur(arr , n , k , index)
{
var 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);
}
}
}
/* A function that uses printSequencesRecur()
to prints all sequences from 1, 1, ..1 to n, n, ..n */
function printSequences(n, k)
{
var arr = Array.from({length: k}, (_, i) => 0);
printSequencesRecur(arr, n, k, 0);
return ;
}
/* Driver Program to test above functions */
var n = 3;
var k = 2;
printSequences(n, k);
// This code is contributed by Amit Katiyar.
</script>
Producción:
1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
Complejidad de tiempo: hay n^k secuencias e imprimir una secuencia lleva O(k) tiempo. Entonces la complejidad del tiempo es O(k*n^k).
Espacio auxiliar: O(k)
Gracias a mopurizwarriors por sugerir el método anterior. Como sugiere alphayoung , podemos evitar el uso de arrays para secuencias pequeñas que pueden caber en un número entero. A continuación se muestra la implementación del mismo.
C++
// C++ program of above approach
/* The core function that generates and
prints all sequences of length k */
void printSeqRecur(int num, int pos, int k, int n)
{
if (pos == k)
{
cout << num << endl;
return;
}
for (int i = 1; i <= n; i++)
{
printSeqRecur(num * 10 + i, pos + 1, k, n);
}
}
/* A function that uses printSequencesRecur()
to prints all sequences
from 1, 1, ..1 to n, n, ..n */
void printSequences(int k, int n)
{
printSeqRecur(0, 0, k, n);
}
// This code is contributed by SHUBHAMSINGH10
C
// C program of above approach
/* The core function that generates and prints all sequences of length 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);
}
}
/* A function that uses printSequencesRecur() to prints all sequences
from 1, 1, ..1 to n, n, ..n */
void printSequences(int k, int n)
{
printSeqRecur(0, 0, k, n);
}
Java
// Java program of above approach
/* The core function that generates and prints all sequences of length 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);
}
}
/* A function that uses printSequencesRecur() to prints all sequences
from 1, 1, ..1 to n, n, ..n */
static void printSequences(int k, int n)
{
printSeqRecur(0, 0, k, n);
}
Python3
# Python program of above approach # We have used number instead of # arrays to prevent linear time # required to print each string def printSeqRecur ( num , n, k ): if n == 0: # if total digits become equal # to n, print the number and return print(num ) return for _ in range(1, k + 1): printSeqRecur (num * 10 + _, n - 1, k) # Driver Code if __name__ == "__main__": k = 3 # length of k-ary string n = 2 # string can take values # from 1,2,3...n printSeqRecur(0, n, k) # This code is contributed # by shivam purohit
C#
// C# program of above approach
/* The core function that generates
and prints all sequences of length 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);
}
}
/* A function that uses printSequencesRecur()
to prints all sequences from 1, 1, ..1 to n, n, ..n */
static void printSequences(int k, int n)
{
printSeqRecur(0, 0, k, n);
}
// This code is contributed by Code_Mech
PHP
<?php
// PHP program of above approach
// We have used number instead of
// arrays to prevent linear time
// required to print each string
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);
}
// Driver Code
$k = 3; // length of k-ary string
$n = 2; // string can take values
// from 1,2,3...n
printSeqRecur(0, $n, $k);
// This code is contributed mits
?>
Javascript
<script>
// Javascript program of above approach
/* The core function that generates and
prints all sequences of length k */
function printSeqRecur( num, pos, k, n)
{
if (pos == k)
{
document.write( num + "<br>" );
return;
}
for (var i = 1; i <= n; i++)
{
printSeqRecur(num * 10 + i, pos + 1, k, n);
}
}
/* A function that uses printSequencesRecur()
to prints all sequences
from 1, 1, ..1 to n, n, ..n */
function printSequences( k, n)
{
printSeqRecur(0, 0, k, n);
}
// This code is contributed by SoumikMondal
</script>
Complejidad del tiempo: O(k*n^k)
Espacio Auxiliar: O(n * k)
Referencias:
Algoritmos y programación: problemas y soluciones por Alexander Shen
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