Dada una array de tamaño n, genere e imprima todas las combinaciones posibles de r elementos en la array. Por ejemplo, si la array de entrada es {1, 2, 3, 4} y r es 2, la salida debería ser {1, 2}, {1, 3}, {1, 4}, {2, 3}, { 2, 4} y {3, 4}.
Los siguientes son dos métodos para hacer esto.
Método 1 (Fix Elements and Recur)
Creamos una array temporal ‘data[]’ que almacena todos los resultados uno por uno. La idea es comenzar desde el primer índice (índice = 0) en data[], uno por uno, corregir elementos en este índice y repetir para los índices restantes. Deje que la array de entrada sea {1, 2, 3, 4, 5} y r sea 3. Primero fijamos 1 en el índice 0 en data[], luego recurrimos para los índices restantes, luego fijamos 2 en el índice 0 y recurrimos. Finalmente, arreglamos 3 y recurrimos para los índices restantes. Cuando el número de elementos en data[] se vuelve igual a r (tamaño de una combinación), imprimimos data[].
El siguiente diagrama muestra el árbol de recurrencia para la misma entrada.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to print all combination
// of size r in an array of size n
#include<bits/stdc++.h>
using namespace std;
void combinationUtil(int arr[], int data[],
int start, int end,
int index, int r);
// The main function that prints
// all combinations of size r
// in arr[] of size n. This function
// mainly uses combinationUtil()
void printCombination(int arr[], int n, int r)
{
// A temporary array to store
// all combination one by one
int data[r];
// Print all combination using
// temporary array 'data[]'
combinationUtil(arr, data, 0, n-1, 0, r);
}
/* arr[] ---> Input Array
data[] ---> Temporary array to
store current combination
start & end ---> Starting and
Ending indexes in arr[]
index ---> Current index in data[]
r ---> Size of a combination to be printed */
void combinationUtil(int arr[], int data[],
int start, int end,
int index, int r)
{
// Current combination is ready
// to be printed, print it
if (index == r)
{
for (int j = 0; j < r; j++)
cout << data[j] << " ";
cout << endl;
return;
}
// replace index with all possible
// elements. The condition "end-i+1 >= r-index"
// makes sure that including one element
// at index will make a combination with
// remaining elements at remaining positions
for (int i = start; i <= end &&
end - i + 1 >= r - index; i++)
{
data[index] = arr[i];
combinationUtil(arr, data, i+1,
end, index+1, r);
}
}
// Driver code
int main()
{
int arr[] = {1, 2, 3, 4, 5};
int r = 3;
int n = sizeof(arr)/sizeof(arr[0]);
printCombination(arr, n, r);
}
// This code is contributed by rathbhupendra
C
// Program to print all combination of size r in an array of size n
#include <stdio.h>
void combinationUtil(int arr[], int data[], int start, int end,
int index, int r);
// The main function that prints all combinations of size r
// in arr[] of size n. This function mainly uses combinationUtil()
void printCombination(int arr[], int n, int r)
{
// A temporary array to store all combination one by one
int data[r];
// Print all combination using temporary array 'data[]'
combinationUtil(arr, data, 0, n-1, 0, r);
}
/* arr[] ---> Input Array
data[] ---> Temporary array to store current combination
start & end ---> Starting and Ending indexes in arr[]
index ---> Current index in data[]
r ---> Size of a combination to be printed */
void combinationUtil(int arr[], int data[], int start, int end,
int index, int r)
{
// Current combination is ready to be printed, print it
if (index == r)
{
for (int j=0; j<r; j++)
printf("%d ", data[j]);
printf("\n");
return;
}
// replace index with all possible elements. The condition
// "end-i+1 >= r-index" makes sure that including one element
// at index will make a combination with remaining elements
// at remaining positions
for (int i=start; i<=end && end-i+1 >= r-index; i++)
{
data[index] = arr[i];
combinationUtil(arr, data, i+1, end, index+1, r);
}
}
// Driver program to test above functions
int main()
{
int arr[] = {1, 2, 3, 4, 5};
int r = 3;
int n = sizeof(arr)/sizeof(arr[0]);
printCombination(arr, n, r);
}
Java
// Java program to print all combination of size r in an array of size n
import java.io.*;
class Combination {
/* arr[] ---> Input Array
data[] ---> Temporary array to store current combination
start & end ---> Starting and Ending indexes in arr[]
index ---> Current index in data[]
r ---> Size of a combination to be printed */
static void combinationUtil(int arr[], int data[], int start,
int end, int index, int r)
{
// Current combination is ready to be printed, print it
if (index == r)
{
for (int j=0; j<r; j++)
System.out.print(data[j]+" ");
System.out.println("");
return;
}
// replace index with all possible elements. The condition
// "end-i+1 >= r-index" makes sure that including one element
// at index will make a combination with remaining elements
// at remaining positions
for (int i=start; i<=end && end-i+1 >= r-index; i++)
{
data[index] = arr[i];
combinationUtil(arr, data, i+1, end, index+1, r);
}
}
// The main function that prints all combinations of size r
// in arr[] of size n. This function mainly uses combinationUtil()
static void printCombination(int arr[], int n, int r)
{
// A temporary array to store all combination one by one
int data[]=new int[r];
// Print all combination using temporary array 'data[]'
combinationUtil(arr, data, 0, n-1, 0, r);
}
/*Driver function to check for above function*/
public static void main (String[] args) {
int arr[] = {1, 2, 3, 4, 5};
int r = 3;
int n = arr.length;
printCombination(arr, n, r);
}
}
/* This code is contributed by Devesh Agrawal */
Python3
# Program to print all combination # of size r in an array of size n # The main function that prints # all combinations of size r in # arr[] of size n. This function # mainly uses combinationUtil() def printCombination(arr, n, r): # A temporary array to # store all combination # one by one data = [0]*r; # Print all combination # using temporary array 'data[]' combinationUtil(arr, data, 0, n - 1, 0, r); # arr[] ---> Input Array # data[] ---> Temporary array to # store current combination # start & end ---> Starting and Ending # indexes in arr[] # index ---> Current index in data[] # r ---> Size of a combination # to be printed def combinationUtil(arr, data, start, end, index, r): # Current combination is ready # to be printed, print it if (index == r): for j in range(r): print(data[j], end = " "); print(); return; # replace index with all # possible elements. The # condition "end-i+1 >= # r-index" makes sure that # including one element at # index will make a combination # with remaining elements at # remaining positions i = start; while(i <= end and end - i + 1 >= r - index): data[index] = arr[i]; combinationUtil(arr, data, i + 1, end, index + 1, r); i += 1; # Driver Code arr = [1, 2, 3, 4, 5]; r = 3; n = len(arr); printCombination(arr, n, r); # This code is contributed by mits
C#
// C# program to print all
// combination of size r
// in an array of size n
using System;
class GFG
{
/* arr[] ---> Input Array
data[] ---> Temporary array to
store current combination
start & end ---> Starting and Ending
indexes in arr[]
index ---> Current index in data[]
r ---> Size of a combination
to be printed */
static void combinationUtil(int []arr, int []data,
int start, int end,
int index, int r)
{
// Current combination is
// ready to be printed,
// print it
if (index == r)
{
for (int j = 0; j < r; j++)
Console.Write(data[j] + " ");
Console.WriteLine("");
return;
}
// replace index with all
// possible elements. The
// condition "end-i+1 >=
// r-index" makes sure that
// including one element
// at index will make a
// combination with remaining
// elements at remaining positions
for (int i = start; i <= end &&
end - i + 1 >= r - index; i++)
{
data[index] = arr[i];
combinationUtil(arr, data, i + 1,
end, index + 1, r);
}
}
// The main function that prints
// all combinations of size r
// in arr[] of size n. This
// function mainly uses combinationUtil()
static void printCombination(int []arr,
int n, int r)
{
// A temporary array to store
// all combination one by one
int []data = new int[r];
// Print all combination
// using temporary array 'data[]'
combinationUtil(arr, data, 0,
n - 1, 0, r);
}
// Driver Code
static public void Main ()
{
int []arr = {1, 2, 3, 4, 5};
int r = 3;
int n = arr.Length;
printCombination(arr, n, r);
}
}
// This code is contributed by m_kit
PHP
<?php
// Program to print all
// combination of size r
// in an array of size n
// The main function that
// prints all combinations
// of size r in arr[] of
// size n. This function
// mainly uses combinationUtil()
function printCombination($arr,
$n, $r)
{
// A temporary array to
// store all combination
// one by one
$data = array();
// Print all combination
// using temporary array 'data[]'
combinationUtil($arr, $data, 0,
$n - 1, 0, $r);
}
/* arr[] ---> Input Array
data[] ---> Temporary array to
store current combination
start & end ---> Starting and Ending
indexes in arr[]
index ---> Current index in data[]
r ---> Size of a combination
to be printed */
function combinationUtil($arr, $data, $start,
$end, $index, $r)
{
// Current combination is ready
// to be printed, print it
if ($index == $r)
{
for ($j = 0; $j < $r; $j++)
echo $data[$j];
echo "\n";
return;
}
// replace index with all
// possible elements. The
// condition "end-i+1 >=
// r-index" makes sure that
// including one element at
// index will make a combination
// with remaining elements at
// remaining positions
for ($i = $start;
$i <= $end &&
$end - $i + 1 >= $r - $index; $i++)
{
$data[$index] = $arr[$i];
combinationUtil($arr, $data, $i + 1,
$end, $index + 1, $r);
}
}
// Driver Code
$arr = array(1, 2, 3, 4, 5);
$r = 3;
$n = sizeof($arr);
printCombination($arr, $n, $r);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to print all
// combination of size r in an array of size n
/* arr[] ---> Input Array
data[] ---> Temporary array to store current combination
start & end ---> Starting and Ending indexes in arr[]
index ---> Current index in data[]
r ---> Size of a combination to be printed */
function combinationUtil(arr,data,start,end,index,r)
{
// Current combination is ready to be printed, print it
if (index == r)
{
for (let j=0; j<r; j++)
{
document.write(data[j]+" ");
}
document.write("<br>")
}
// replace index with all possible elements. The condition
// "end-i+1 >= r-index" makes sure that including one element
// at index will make a combination with remaining elements
// at remaining positions
for (let i=start; i<=end && end-i+1 >= r-index; i++)
{
data[index] = arr[i];
combinationUtil(arr, data, i+1, end, index+1, r);
}
}
// The main function that prints all combinations of size r
// in arr[] of size n. This function mainly uses combinationUtil()
function printCombination(arr,n,r)
{
// A temporary array to store all combination one by one
let data = new Array(r);
// Print all combination using temporary array 'data[]'
combinationUtil(arr, data, 0, n-1, 0, r);
}
/*Driver function to check for above function*/
let arr=[1, 2, 3, 4, 5];
let r = 3;
let n = arr.length;
printCombination(arr, n, r);
// This code is contributed by rag2127
</script>
Producción:
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
Complejidad del tiempo: O(n^2)
¿Cómo manejar los duplicados?
Tenga en cuenta que el método anterior no maneja duplicados. Por ejemplo, si la array de entrada es {1, 2, 1} y r es 2, entonces el programa imprime {1, 2} y {2, 1} como dos combinaciones diferentes. Podemos evitar duplicados agregando las siguientes dos cosas adicionales al código anterior.
1) Agregue código para ordenar la array antes de llamar a combinationUtil() en printCombination()
2) Agregue las siguientes líneas al final del bucle for en combinationUtil()
// Since the elements are sorted, all occurrences of an element
// must be together
while (arr[i] == arr[i+1])
i++;
Vea esto para una implementación que maneja duplicados.
Método 2 (Incluir y Excluir todos los elementos)
Al igual que el método anterior, creamos una array temporal data[]. La idea aquí es similar al problema de la suma de subconjuntos . Consideramos uno por uno cada elemento de la array de entrada y recurrimos para dos casos:
1) El elemento está incluido en la combinación actual (Ponemos el elemento en data[] e incrementamos el siguiente índice disponible en data[])
2) El elemento es excluido en la combinación actual (No ponemos el elemento y no cambiamos el índice)
Cuando el número de elementos en data[] es igual a r (tamaño de una combinación), lo imprimimos.
Este método se basa principalmente en la Identidad de Pascal , es decir, n cr= n-1 cr + n-1 cr-1
A continuación se muestra la implementación del método 2.
C++
// C++ Program to print all combination of
// size r in an array of size n
#include <bits/stdc++.h>
using namespace std;
void combinationUtil(int arr[], int n, int r,
int index, int data[], int i);
// The main function that prints all
// combinations of size r in arr[]
// of size n. This function mainly
// uses combinationUtil()
void printCombination(int arr[], int n, int r)
{
// A temporary array to store
// all combination one by one
int data[r];
// Print all combination using
// temporary array 'data[]'
combinationUtil(arr, n, r, 0, data, 0);
}
/* arr[] ---> Input Array
n ---> Size of input array
r ---> Size of a combination to be printed
index ---> Current index in data[]
data[] ---> Temporary array to store current combination
i ---> index of current element in arr[] */
void combinationUtil(int arr[], int n, int r,
int index, int data[], int i)
{
// Current combination is ready, print it
if (index == r)
{
for (int j = 0; j < r; j++)
cout << data[j] << " ";
cout << endl;
return;
}
// When no more elements are there to put in data[]
if (i >= n)
return;
// current is included, put next at next location
data[index] = arr[i];
combinationUtil(arr, n, r, index + 1, data, i + 1);
// current is excluded, replace it with next (Note that
// i+1 is passed, but index is not changed)
combinationUtil(arr, n, r, index, data, i+1);
}
// Driver code
int main()
{
int arr[] = {1, 2, 3, 4, 5};
int r = 3;
int n = sizeof(arr)/sizeof(arr[0]);
printCombination(arr, n, r);
return 0;
}
// This is code is contributed by rathbhupendra
C
// Program to print all combination of size r in an array of size n
#include<stdio.h>
void combinationUtil(int arr[],int n,int r,int index,int data[],int i);
// The main function that prints all combinations of size r
// in arr[] of size n. This function mainly uses combinationUtil()
void printCombination(int arr[], int n, int r)
{
// A temporary array to store all combination one by one
int data[r];
// Print all combination using temporary array 'data[]'
combinationUtil(arr, n, r, 0, data, 0);
}
/* arr[] ---> Input Array
n ---> Size of input array
r ---> Size of a combination to be printed
index ---> Current index in data[]
data[] ---> Temporary array to store current combination
i ---> index of current element in arr[] */
void combinationUtil(int arr[], int n, int r, int index, int data[], int i)
{
// Current combination is ready, print it
if (index == r)
{
for (int j=0; j<r; j++)
printf("%d ",data[j]);
printf("\n");
return;
}
// When no more elements are there to put in data[]
if (i >= n)
return;
// current is included, put next at next location
data[index] = arr[i];
combinationUtil(arr, n, r, index+1, data, i+1);
// current is excluded, replace it with next (Note that
// i+1 is passed, but index is not changed)
combinationUtil(arr, n, r, index, data, i+1);
}
// Driver program to test above functions
int main()
{
int arr[] = {1, 2, 3, 4, 5};
int r = 3;
int n = sizeof(arr)/sizeof(arr[0]);
printCombination(arr, n, r);
return 0;
}
Java
// Java program to print all combination of size r in an array of size n
import java.io.*;
class Combination {
/* arr[] ---> Input Array
data[] ---> Temporary array to store current combination
start & end ---> Staring and Ending indexes in arr[]
index ---> Current index in data[]
r ---> Size of a combination to be printed */
static void combinationUtil(int arr[], int n, int r, int index,
int data[], int i)
{
// Current combination is ready to be printed, print it
if (index == r)
{
for (int j=0; j<r; j++)
System.out.print(data[j]+" ");
System.out.println("");
return;
}
// When no more elements are there to put in data[]
if (i >= n)
return;
// current is included, put next at next location
data[index] = arr[i];
combinationUtil(arr, n, r, index+1, data, i+1);
// current is excluded, replace it with next (Note that
// i+1 is passed, but index is not changed)
combinationUtil(arr, n, r, index, data, i+1);
}
// The main function that prints all combinations of size r
// in arr[] of size n. This function mainly uses combinationUtil()
static void printCombination(int arr[], int n, int r)
{
// A temporary array to store all combination one by one
int data[]=new int[r];
// Print all combination using temporary array 'data[]'
combinationUtil(arr, n, r, 0, data, 0);
}
/*Driver function to check for above function*/
public static void main (String[] args) {
int arr[] = {1, 2, 3, 4, 5};
int r = 3;
int n = arr.length;
printCombination(arr, n, r);
}
}
/* This code is contributed by Devesh Agrawal */
Python 3
# Program to print all combination # of size r in an array of size n # The main function that prints all # combinations of size r in arr[] of # size n. This function mainly uses # combinationUtil() def printCombination(arr, n, r): # A temporary array to store # all combination one by one data = [0] * r # Print all combination using # temporary array 'data[]' combinationUtil(arr, n, r, 0, data, 0) ''' arr[] ---> Input Array n ---> Size of input array r ---> Size of a combination to be printed index ---> Current index in data[] data[] ---> Temporary array to store current combination i ---> index of current element in arr[] ''' def combinationUtil(arr, n, r, index, data, i): # Current combination is ready, # print it if (index == r): for j in range(r): print(data[j], end = " ") print() return # When no more elements are # there to put in data[] if (i >= n): return # current is included, put # next at next location data[index] = arr[i] combinationUtil(arr, n, r, index + 1, data, i + 1) # current is excluded, replace it # with next (Note that i+1 is passed, # but index is not changed) combinationUtil(arr, n, r, index, data, i + 1) # Driver Code if __name__ == "__main__": arr = [1, 2, 3, 4, 5] r = 3 n = len(arr) printCombination(arr, n, r) # This code is contributed # by ChitraNayal
C#
// C# program to print all
// combination of size r
// in an array of size n
using System;
class GFG
{
/* arr[] ---> Input Array
data[] ---> Temporary array to
store current combination
start & end ---> Starting and Ending
indexes in arr[]
index ---> Current index in data[]
r ---> Size of a combination
to be printed */
static void combinationUtil(int []arr, int n,
int r, int index,
int []data, int i)
{
// Current combination is ready
// to be printed, print it
if (index == r)
{
for (int j = 0; j < r; j++)
Console.Write(data[j] + " ");
Console.WriteLine("");
return;
}
// When no more elements are
// there to put in data[]
if (i >= n)
return;
// current is included, put
// next at next location
data[index] = arr[i];
combinationUtil(arr, n, r,
index + 1, data, i + 1);
// current is excluded, replace
// it with next (Note that
// i+1 is passed, but index
// is not changed)
combinationUtil(arr, n, r, index,
data, i + 1);
}
// The main function that prints
// all combinations of size r
// in arr[] of size n. This
// function mainly uses combinationUtil()
static void printCombination(int []arr,
int n, int r)
{
// A temporary array to store
// all combination one by one
int []data = new int[r];
// Print all combination
// using temporary array 'data[]'
combinationUtil(arr, n, r, 0, data, 0);
}
// Driver Code
static public void Main ()
{
int []arr = {1, 2, 3, 4, 5};
int r = 3;
int n = arr.Length;
printCombination(arr, n, r);
}
}
// This code is contributed by ajit
PHP
<?php
// Program to print all
// combination of size r
// in an array of size n
// The main function that prints
// all combinations of size r in
// arr[] of size n. This function
// mainly uses combinationUtil()
function printCombination($arr, $n, $r)
{
// A temporary array to store
// all combination one by one
$data = Array();
// Print all combination using
// temporary array 'data[]'
combinationUtil($arr, $n, $r,
0, $data, 0);
}
/* arr[] ---> Input Array
n ---> Size of input array
r ---> Size of a combination
to be printed
index ---> Current index in data[]
data[] ---> Temporary array to store
current combination
i ---> index of current element in arr[] */
function combinationUtil($arr, $n, $r,
$index, $data, $i)
{
// Current combination
// is ready, print it
if ($index == $r)
{
for ($j = 0; $j < $r; $j++)
echo $data[$j], " ";
echo "\n";
return;
}
// When no more elements are
// there to put in data[]
if ($i >= $n)
return;
// current is included, put
// next at next location
$data[$index] = $arr[$i];
combinationUtil($arr, $n, $r,
$index + 1,
$data, $i + 1);
// current is excluded, replace
// it with next (Note that i+1
// is passed, but index is not changed)
combinationUtil($arr, $n, $r,
$index, $data, $i + 1);
}
// Driver Code
$arr = array(1, 2, 3, 4, 5);
$r = 3;
$n = sizeof($arr);
printCombination($arr, $n, $r);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to print all
// combination of size r in an array of size n
/* arr[] ---> Input Array
data[] ---> Temporary array to
store current combination
start & end ---> Starting and
Ending indexes in arr[]
index ---> Current index in data[]
r ---> Size of a combination to be printed */
function combinationUtil(arr,n,r,index,data,i)
{
// Current combination is ready
// to be printed, print it
if (index == r)
{
for (let j=0; j<r; j++)
{
document.write(data[j]+" ");
}
document.write("<br>");
return;
}
// When no more elements are there
// to put in data[]
if (i >= n)
{
return;
}
// current is included, put
// next at next location
data[index] = arr[i];
combinationUtil(arr, n, r, index+1, data, i+1);
// current is excluded, replace
// it with next (Note that
// i+1 is passed, but index is not changed)
combinationUtil(arr, n, r, index, data, i+1);
}
// The main function that prints
// all combinations of size r
// in arr[] of size n. This function
// mainly uses combinationUtil()
function printCombination(arr,n,r)
{
// A temporary array to store
// all combination one by one
let data=new Array(r);
// Print all combination using
// temporary array 'data[]'
combinationUtil(arr, n, r, 0, data, 0);
}
/*Driver function to check for above function*/
let arr=[1, 2, 3, 4, 5];
let r = 3;
let n = arr.length;
printCombination(arr, n, r);
// This code is contributed by avanitrachhadiya2155
</script>
Producción :
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
¿Cómo manejar los duplicados en el método 2?
Al igual que el método 1, podemos seguir dos cosas para manejar los duplicados.
1) Agregue código para ordenar la array antes de llamar a combinationUtil() en printCombination()
2) Agregue las siguientes líneas entre dos llamadas recursivas de combinationUtil() en combinationUtil()
// Since the elements are sorted, all occurrences of an element
// must be together
while (arr[i] == arr[i+1])
i++;
Vea esto para una implementación que maneja duplicados.
A continuación se muestra otro enfoque basado en DFS para resolver este problema.
Haz todas las combinaciones de tamaño k
. Este artículo es una contribución de Bateesh . 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