Genere todos los subconjuntos posibles de tamaño r de la array dada con elementos distintos.
Ejemplos:
Input : arr[] = {1, 2, 3, 4}
r = 2
Output : 1 2
1 3
1 4
2 3
2 4
3 4
Input : arr[] = {10, 20, 30, 40, 50}
r = 3
Output : 10 20 30
10 20 40
10 20 50
10 30 40
10 30 50
10 40 50
20 30 40
20 30 50
20 40 50
30 40 50
Este problema es el mismo Imprime todas las combinaciones posibles de r elementos en una array dada de tamaño n .
La idea aquí es similar al problema de la suma de subconjuntos . Nosotros, uno por uno, consideramos cada elemento de la array de entrada y recurrimos para dos casos:
- El elemento se incluye en la combinación actual (Ponemos el elemento en data[] y aumentamos el siguiente índice disponible en data[])
- El elemento está excluido en la combinación actual (No ponemos el elemento y no cambiamos el índice)
Cuando el número de elementos en data[] se vuelve 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
Implementación:
C++
// C++ Program to print all combination of size r in
// an array of size n
#include <iostream>
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 <<"\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[] = { 10, 20, 30, 40, 50 };
int r = 3;
int n = sizeof(arr) / sizeof(arr[0]);
printCombination(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
#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[] = { 10, 20, 30, 40, 50 };
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 Permutation {
/* 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++)
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[] = { 10, 20, 30, 40, 50 };
int r = 3;
int n = arr.length;
printCombination(arr, n, r);
}
}
/* This code is contributed by Devesh Agrawal */
Python3
# Python3 program to print all
# subset combination of n
# element in given set of r element .
# 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, n, r,
index, data, i):
# Current combination is
# ready to be printed,
# 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)
# 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 = list(range(r))
# Print all combination
# using temporary
# array 'data[]'
combinationUtil(arr, n, r,
0, data, 0)
# Driver Code
arr = [10, 20, 30, 40, 50]
r = 3
n = len(arr)
printcombination(arr, n, r)
# This code is contributed
# by Ambuj sahu
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 function to check for
above function */
public static void Main()
{
int []arr = { 10, 20, 30, 40, 50 };
int r = 3;
int n = arr.Length;
printCombination(arr, n, r);
}
}
// This code is contributed by vt_m.
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 program to test above functions
$arr = array( 10, 20, 30, 40, 50 );
$r = 3;
$n = count($arr);
printCombination($arr, $n, $r);
// This code is contributed by anuj_67.
?>
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);
data.fill(0);
// Print all combination using
// temporary array 'data[]'
combinationUtil(arr, n, r, 0, data, 0);
}
let arr = [ 10, 20, 30, 40, 50 ];
let r = 3;
let n = arr.length;
printCombination(arr, n, r);
</script>
Producción
10 20 30 10 20 40 10 20 50 10 30 40 10 30 50 10 40 50 20 30 40 20 30 50 20 40 50 30 40 50
Consulte la publicación a continuación para obtener más soluciones e ideas para manejar duplicados en la array de entrada.
Imprime todas las combinaciones posibles de r elementos en una array dada de tamaño n .
Este artículo es una contribución de Dhiman Mayank . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo 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.
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