Dada una array arr[] que consta de N caracteres, la tarea es generar todas las combinaciones posibles de, como máximo , X elementos (1 ≤ X ≤ N).
Ejemplos:
Entrada: N = 3, X = 2, arr[] = {‘a’, ‘b’, ‘a’}
Salida: abc bc ca ab cb ac ba
Explicación: Todas las combinaciones posibles usando 1 carácter son 3 {‘a’ , ‘antes de Cristo’}. Todas las combinaciones posibles que usan 2 caracteres son {“bc” “ca” “ab” “cb” “ac” “ba”}.Entrada: N = 3, X = 3, arr[] = {‘d’, ‘a’, ‘b’}
Salida: dab da ab bd ad ba db dab dba abd adb bda mal
Enfoque: El problema dado se puede resolver usando el enfoque de Programación Dinámica . Siga los pasos a continuación para resolver el problema:
- Genere todas las permutaciones posibles que se pueden crear con 1 carácter, que es la array dada arr[] .
- Almacene todas las permutaciones.
- Una vez almacenada, genere todas las permutaciones posibles de 2 caracteres y guárdelas.
- Una vez que se complete el último paso, descarte todas las permutaciones de un solo carácter.
- De la misma manera, iterativamente, calcule las permutaciones hasta llegar a X.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to generate permutations of
// at most X elements from array arr[]
void differentFlagPermutations(int X,
vector<string> arr)
{
vector<string> ml;
ml = arr;
for(int i = 0; i < ml.size(); i++)
{
cout << ml[i] << " ";
}
int count = ml.size();
// Traverse all possible lengths
for(int z = 0; z < X - 1; z++)
{
// Stores all combinations
// of length z
vector<string> tmp;
// Traverse the array
for(int i = 0; i < arr.size(); i++)
{
for(int k = 0; k < ml.size(); k++)
{
if (arr[i] != ml[k])
{
// Generate all
// combinations of length z
tmp.push_back(ml[k] + arr[i]);
count += 1;
}
}
}
// Print all combinations of length z
for(int i = 0; i < tmp.size(); i++)
{
cout << tmp[i] << " ";
}
// Replace all combinations of length z - 1
// with all combinations of length z
ml = tmp;
}
}
// Driver Code
int main()
{
// Given array
vector<string> arr{ "c", "a", "b" };
// Given X
int X = 2;
differentFlagPermutations(X, arr);
return 0;
}
// This code is contributed by divyeshrabadiya07
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to generate permutations of
// at most X elements from array arr[]
static void differentFlagPermutations(int X,
String[] arr)
{
String[] ml = arr;
for(int i = 0; i < ml.length; i++)
{
System.out.print(ml[i] + " ");
}
int count = ml.length;
// Traverse all possible lengths
for(int z = 0; z < X - 1; z++)
{
// Stores all combinations
// of length z
Vector<String> tmp = new Vector<String>();
// Traverse the array
for(int i = 0; i < arr.length; i++)
{
for(int k = 0; k < ml.length; k++)
{
if (arr[i] != ml[k])
{
// Generate all
// combinations of length z
tmp.add(ml[k] + arr[i]);
count += 1;
}
}
}
// Print all combinations of length z
for(int i = 0; i < tmp.size(); i++)
{
System.out.print(tmp.get(i) + " ");
}
// Replace all combinations of length z - 1
// with all combinations of length z
ml = tmp.toArray(new String[tmp.size()]);;
}
}
// Driver Code
public static void main(String[] args)
{
// Given array
String []arr = { "c", "a", "b" };
// Given X
int X = 2;
differentFlagPermutations(X, arr);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program for the above approach
# Function to generate permutations of
# at most X elements from array arr[]
def differentFlagPermutations(X, arr):
ml = arr.copy()
print(" ".join(ml), end =" ")
count = len(ml)
# Traverse all possible lengths
for z in range(X-1):
# Stores all combinations
# of length z
tmp = []
# Traverse the array
for i in arr:
for k in ml:
if i not in k:
# Generate all
# combinations of length z
tmp.append(k + i)
count += 1
# Print all combinations of length z
print(" ".join(tmp), end =" ")
# Replace all combinations of length z - 1
# with all combinations of length z
ml = tmp
# Given array
arr = ['c', 'a', 'b']
# Given X
X = 2
differentFlagPermutations(X, arr)
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to generate permutations of
// at most X elements from array arr[]
static void differentFlagPermutations(int X, List<string> arr)
{
List<string> ml = new List<string>();
ml = arr;
for(int i = 0; i < ml.Count; i++)
{
Console.Write(ml[i] + " ");
}
int count = ml.Count;
// Traverse all possible lengths
for(int z = 0; z < X - 1; z++)
{
// Stores all combinations
// of length z
List<string> tmp = new List<string>();
// Traverse the array
for(int i = 0; i < arr.Count; i++)
{
for(int k = 0; k < ml.Count; k++)
{
if (arr[i] != ml[k])
{
// Generate all
// combinations of length z
tmp.Add(ml[k] + arr[i]);
count += 1;
}
}
}
// Print all combinations of length z
for(int i = 0; i < tmp.Count; i++)
{
Console.Write(tmp[i] + " ");
}
// Replace all combinations of length z - 1
// with all combinations of length z
ml = tmp;
}
}
// Driver code
static void Main()
{
// Given array
List<string> arr = new List<string>(new string[] { "c", "a", "b" });
// Given X
int X = 2;
differentFlagPermutations(X, arr);
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// Javascript program for the above approach
// Function to generate permutations of
// at most X elements from array arr[]
function differentFlagPermutations(X, arr)
{
let ml = [];
ml = arr;
for(let i = 0; i < ml.length; i++)
{
document.write(ml[i] + " ");
}
let count = ml.length;
// Traverse all possible lengths
for(let z = 0; z < X - 1; z++)
{
// Stores all combinations
// of length z
let tmp = [];
// Traverse the array
for(let i = 0; i < arr.length; i++)
{
for(let k = 0; k < ml.length; k++)
{
if (arr[i] != ml[k])
{
// Generate all
// combinations of length z
tmp.push(ml[k] + arr[i]);
count += 1;
}
}
}
// Print all combinations of length z
for(let i = 0; i < tmp.length; i++)
{
document.write(tmp[i] + " ");
}
// Replace all combinations of length z - 1
// with all combinations of length z
ml = tmp;
}
}
// Given array
let arr = [ "c", "a", "b" ];
// Given X
let X = 2;
differentFlagPermutations(X, arr);
</script>
Producción:
c a b ac bc ca ba cb ab
Complejidad de Tiempo: O(X*N 2 )
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por UnworthyProgrammer y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA