Supongamos que tenemos una string de longitud-n y queremos generar todas las combinaciones/permutaciones tomadas r a la vez con/sin repeticiones. Hay cuatro conceptos fundamentales en Combinatoria
1) Combinaciones sin repeticiones/sustituciones.
2) Combinaciones con repeticiones/sustituciones.
3) Permutaciones sin repeticiones/sustituciones.
4) Permutaciones con repeticiones/sustituciones.
A continuación se muestra una tabla resumen que representa los conceptos fundamentales de la Teoría Combinatoria.
Se permiten reemplazos/repeticiones | Sustituciones/Repeticiones no permitidas | |
Permutaciones/Orden Importante | posibilidades https://www.geeksforgeeks.org/print-all-combinations-of-given-length/ Consulte el caso especial cuando r=n a continuación https://www.geeksforgeeks.org/print-all-permutations-with- repetición de caracteres |
posibilidades https://www.geeksforgeeks.org/write-ac-program-to-print-all-permutations-of-a-given-string/ |
Combinaciones/Orden No Importante | posibilidades Artículo actual ( https://www.geeksforgeeks.org/combinations-with-repetitions ) |
posibilidades https://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/ |
Este artículo trata sobre el tercer caso (Orden No importante y Repeticiones permitidas).
La idea es repetir todas las posibilidades de la string, incluso si los caracteres se repiten.
El caso base de la recursividad es cuando hay un total de caracteres ‘r’ y la combinación está lista para ser impresa.
Para mayor claridad, vea el árbol de recurrencia para la string: “ 1 2 3 4” y r=2
A continuación se muestra la implementación.
C++
// C++ program to print all combination of size r in an array // of size n with repetitions allowed #include <bits/stdc++.h> using namespace std; /* arr[] ---> Input Array chosen[] ---> Temporary array to store indices of current combination start & end ---> Starting and Ending indexes in arr[] r ---> Size of a combination to be printed */ void CombinationRepetitionUtil(int chosen[], int arr[], int index, int r, int start, int end) { // Since index has become r, current combination is // ready to be printed, print if (index == r) { for (int i = 0; i < r; i++) cout<<" "<< arr[chosen[i]]; cout<<"\n"; return; } // One by one choose all elements (without considering // the fact whether element is already chosen or not) // and recur for (int i = start; i <= end; i++) { chosen[index] = i; CombinationRepetitionUtil(chosen, arr, index + 1, r, i, end); } return; } // The main function that prints all combinations of size r // in arr[] of size n with repetitions. This function mainly // uses CombinationRepetitionUtil() void CombinationRepetition(int arr[], int n, int r) { // Allocate memory int chosen[r+1]; // Call the recursive function CombinationRepetitionUtil(chosen, arr, 0, r, 0, n-1); } // Driver program to test above functions int main() { int arr[] = {1, 2, 3, 4}; int n = sizeof(arr)/sizeof(arr[0]); int r = 2; CombinationRepetition(arr, n, r); return 0; } // this code is contributed by shivanisinghss2110
C
// C program to print all combination of size r in an array // of size n with repetitions allowed #include <stdio.h> /* arr[] ---> Input Array chosen[] ---> Temporary array to store indices of current combination start & end ---> Starting and Ending indexes in arr[] r ---> Size of a combination to be printed */ void CombinationRepetitionUtil(int chosen[], int arr[], int index, int r, int start, int end) { // Since index has become r, current combination is // ready to be printed, print if (index == r) { for (int i = 0; i < r; i++) printf("%d ", arr[chosen[i]]); printf("\n"); return; } // One by one choose all elements (without considering // the fact whether element is already chosen or not) // and recur for (int i = start; i <= end; i++) { chosen[index] = i; CombinationRepetitionUtil(chosen, arr, index + 1, r, i, end); } return; } // The main function that prints all combinations of size r // in arr[] of size n with repetitions. This function mainly // uses CombinationRepetitionUtil() void CombinationRepetition(int arr[], int n, int r) { // Allocate memory int chosen[r+1]; // Call the recursive function CombinationRepetitionUtil(chosen, arr, 0, r, 0, n-1); } // Driver program to test above functions int main() { int arr[] = {1, 2, 3, 4}; int n = sizeof(arr)/sizeof(arr[0]); int r = 2; CombinationRepetition(arr, n, r); return 0; }
Java
// Java program to print all combination of size r in an array // of size n with repetitions allowed class GFG { /* arr[] ---> Input Array chosen[] ---> Temporary array to store indices of current combination start & end ---> Starting and Ending indexes in arr[] r ---> Size of a combination to be printed */ static void CombinationRepetitionUtil(int chosen[], int arr[], int index, int r, int start, int end) { // Since index has become r, current combination is // ready to be printed, print if (index == r) { for (int i = 0; i < r; i++) { System.out.printf("%d ", arr[chosen[i]]); } System.out.printf("\n"); return; } // One by one choose all elements (without considering // the fact whether element is already chosen or not) // and recur for (int i = start; i <= end; i++) { chosen[index] = i; CombinationRepetitionUtil(chosen, arr, index + 1, r, i, end); } return; } // The main function that prints all combinations of size r // in arr[] of size n with repetitions. This function mainly // uses CombinationRepetitionUtil() static void CombinationRepetition(int arr[], int n, int r) { // Allocate memory int chosen[] = new int[r + 1]; // Call the recursive function CombinationRepetitionUtil(chosen, arr, 0, r, 0, n - 1); } // Driver program to test above functions public static void main(String[] args) { int arr[] = {1, 2, 3, 4}; int n = arr.length; int r = 2; CombinationRepetition(arr, n, r); } } /* This Java code is contributed by PrinciRaj1992*/
Python3
# Python3 program to print all combination # of size r in an array of size n ''' arr[] ---> Input Array chosen[] ---> Temporary array to store current combination start & end ---> Starting and Ending indexes in arr[] r---> Size of a combination to be printed ''' def CombinationRepetitionUtil(chosen, arr, index, r, start, end): # Current combination is ready, # print it if index == r: for j in range(r): print(chosen[j], end = " ") print() return # When no more elements are # there to put in chosen[] if start > n: return # Current is included, put # next at next location chosen[index] = arr[start] # Current is excluded, replace it # with next (Note that i+1 is passed, # but index is not changed) CombinationRepetitionUtil(chosen, arr, index + 1, r, start, end) CombinationRepetitionUtil(chosen, arr, index, r, start + 1, end) # The main function that prints all # combinations of size r in arr[] of # size n. This function mainly uses # CombinationRepetitionUtil() def CombinationRepetition(arr, n, r): # A temporary array to store # all combination one by one chosen = [0] * r # Print all combination using # temporary array 'chosen[]' CombinationRepetitionUtil(chosen, arr, 0, r, 0, n) # Driver code arr = [ 1, 2, 3, 4 ] r = 2 n = len(arr) - 1 CombinationRepetition(arr, n, r) # This code is contributed by Vaibhav Kumar 12.
C#
// C# program to print all combination of size r in an array // of size n with repetitions allowed using System; public class GFG{ /* arr[] ---> Input Array chosen[] ---> Temporary array to store indices of current combination start & end ---> Starting and Ending indexes in arr[] r ---> Size of a combination to be printed */ static void CombinationRepetitionUtil(int []chosen, int []arr, int index, int r, int start, int end) { // Since index has become r, current combination is // ready to be printed, print if (index == r) { for (int i = 0; i < r; i++) { Console.Write(arr[chosen[i]]+" "); } Console.WriteLine(); return; } // One by one choose all elements (without considering // the fact whether element is already chosen or not) // and recur for (int i = start; i <= end; i++) { chosen[index] = i; CombinationRepetitionUtil(chosen, arr, index + 1, r, i, end); } return; } // The main function that prints all combinations of size r // in arr[] of size n with repetitions. This function mainly // uses CombinationRepetitionUtil() static void CombinationRepetition(int []arr, int n, int r) { // Allocate memory int []chosen = new int[r + 1]; // Call the recursive function CombinationRepetitionUtil(chosen, arr, 0, r, 0, n - 1); } // Driver program to test above functions public static void Main() { int []arr = {1, 2, 3, 4}; int n = arr.Length; int r = 2; CombinationRepetition(arr, n, r); } } // This code is contributed by PrinciRaj1992
Javascript
<script> // javascript program to print all combination of size r in an array // of size n with repetitions allowed /* arr ---> Input Array chosen ---> Temporary array to store indices of current combination start & end ---> Starting and Ending indexes in arr r ---> Size of a combination to be printed */ function CombinationRepetitionUtil(chosen , arr, index , r , start , end) { // Since index has become r, current combination is // ready to be printed, print if (index == r) { for (var i = 0; i < r; i++) { document.write(arr[chosen[i]]+" "); } document.write("<br>"); return; } // One by one choose all elements (without considering // the fact whether element is already chosen or not) // and recur for (var i = start; i <= end; i++) { chosen[index] = i; CombinationRepetitionUtil(chosen, arr, index + 1, r, i, end); } return; } // The main function that prints all combinations of size r // in arr of size n with repetitions. This function mainly // uses CombinationRepetitionUtil() function CombinationRepetition(arr , n , r) { // Allocate memory var chosen = Array.from({length: (r + 1)}, (_, i) => 0); // Call the recursive function CombinationRepetitionUtil(chosen, arr, 0, r, 0, n - 1); } // Driver program to test above functions var arr = [1, 2, 3, 4]; var n = arr.length; var r = 2; CombinationRepetition(arr, n, r); // This code is contributed by shikhasingrajput </script>
Producción :
1 1 1 2 1 3 1 4 2 2 2 3 2 4 3 3 3 4 4 4
Complejidad de tiempo: para una string de longitud y combinaciones tomadas a la vez con repeticiones, se necesita un tiempo total.
Referencias : https://en.wikipedia.org/wiki/Combination
Este artículo es una contribución de Rachit Belwariar. Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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