Dada una string de longitud n, imprime todas las permutaciones de la string dada. Se permite la repetición de caracteres. Imprime estas permutaciones en orden ordenado lexicográficamente
Ejemplos:
C++
// C++ program to print all permutations
// with repetition of characters
#include <bits/stdc++.h>
#include<string.h>
using namespace std;
/* Following function is used by
the library qsort() function
to sort an array of chars */
int compare (const void * a, const void * b);
/* The main function that recursively
prints all repeated permutations of
the given string. It uses data[] to store all
permutations one by one */
void allLexicographicRecur (char *str, char* data,
int last, int index)
{
int i, len = strlen(str);
// One by one fix all characters at
// the given index and recur for
// the/ subsequent indexes
for ( i = 0; i < len; i++ )
{
// Fix the ith character at index
// and if this is not the last
// index then recursively call
// for higher indexes
data[index] = str[i] ;
// If this is the last index then
// print the string stored in
// data[]
if (index == last)
cout << data << endl;
else // Recur for higher indexes
allLexicographicRecur (str, data, last, index+1);
}
}
/* This function sorts input string,
allocate memory for data (needed
for allLexicographicRecur()) and
calls allLexicographicRecur() for
printing all permutations */
void allLexicographic(char *str)
{
int len = strlen (str) ;
// Create a temp array that will
// be used by allLexicographicRecur()
char *data = (char *) malloc (sizeof(char) * (len + 1)) ;
data[len] = '\0';
// Sort the input string so that
// we get all output strings in
// lexicographically sorted order
qsort(str, len, sizeof(char), compare);
// Now print all permutations
allLexicographicRecur (str, data, len-1, 0);
// Free data to avoid memory leak
free(data);
}
// Needed for library function qsort()
int compare (const void * a, const void * b)
{
return ( *(char *)a - *(char *)b );
}
// Driver code
int main()
{
char str[] = "ABC";
cout << "All permutations with repetition of "<<
str <<" are: "<<endl ;
allLexicographic(str);
return 0;
}
// This code is contributed by rathbhupendra
C
// C program to print all permutations with repetition
// of characters
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/* Following function is used by the library qsort() function
to sort an array of chars */
int compare (const void * a, const void * b);
/* The main function that recursively prints all repeated
permutations of the given string. It uses data[] to store all
permutations one by one */
void allLexicographicRecur (char *str, char* data, int last, int index)
{
int i, len = strlen(str);
// One by one fix all characters at the given index and recur for
// the/ subsequent indexes
for ( i=0; i<len; i++ )
{
// Fix the ith character at index and if this is not the last
// index then recursively call for higher indexes
data[index] = str[i] ;
// If this is the last index then print the string stored in
// data[]
if (index == last)
printf("%s\n", data);
else // Recur for higher indexes
allLexicographicRecur (str, data, last, index+1);
}
}
/* This function sorts input string, allocate memory for data (needed
for allLexicographicRecur()) and calls allLexicographicRecur() for
printing all permutations */
void allLexicographic(char *str)
{
int len = strlen (str) ;
// Create a temp array that will be used by allLexicographicRecur()
char *data = (char *) malloc (sizeof(char) * (len + 1)) ;
data[len] = '\0';
// Sort the input string so that we get all output strings in
// lexicographically sorted order
qsort(str, len, sizeof(char), compare);
// Now print all permutations
allLexicographicRecur (str, data, len-1, 0);
// Free data to avoid memory leak
free(data);
}
// Needed for library function qsort()
int compare (const void * a, const void * b)
{
return ( *(char *)a - *(char *)b );
}
// Driver program to test above functions
int main()
{
char str[] = "ABC";
printf("All permutations with repetition of %s are: \n",
str);
allLexicographic(str);
return 0;
}
Java
// Java program to print all permutations
// with repetition of characters
import java.util.Arrays;
class GFG
{
// The main function that recursively prints
// all repeated permutations of the given string.
// It uses data[] to store all permutations one by one
static void allLexicographicRecur(String str, char[] data,
int last, int index)
{
int length = str.length();
// One by one fix all characters at the given index
// and recur for the subsequent indexes
for (int i = 0; i < length; i++)
{
// Fix the ith character at index and if
// this is not the last index then
// recursively call for higher indexes
data[index] = str.charAt(i);
// If this is the last index then print
// the string stored in data[]
if (index == last)
System.out.println(new String(data));
else
allLexicographicRecur(str, data, last,
index + 1);
}
}
// This function sorts input string, allocate memory
// for data(needed for allLexicographicRecur()) and calls
// allLexicographicRecur() for printing all permutations
static void allLexicographic(String str)
{
int length = str.length();
// Create a temp array that will be used by
// allLexicographicRecur()
char[] data = new char[length + 1];
char[] temp = str.toCharArray();
// Sort the input string so that we get all
// output strings in lexicographically sorted order
Arrays.sort(temp);
str = new String(temp);
// Now print all permutations
allLexicographicRecur(str, data, length - 1, 0);
}
// Driver Code
public static void main(String[] args)
{
String str = "ABC";
System.out.printf("All permutations with " +
"repetition of %s are: \n", str);
allLexicographic(str);
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python program to print all permutations with repetition
# of characters
def toString(List):
return ''.join(List)
# The main function that recursively prints all repeated
# permutations of the given string. It uses data[] to store
# all permutations one by one
def allLexicographicRecur (string, data, last, index):
length = len(string)
# One by one fix all characters at the given index and
# recur for the subsequent indexes
for i in range(length):
# Fix the ith character at index and if this is not
# the last index then recursively call for higher
# indexes
data[index] = string[i]
# If this is the last index then print the string
# stored in data[]
if index==last:
print (toString(data))
else:
allLexicographicRecur(string, data, last, index+1)
# This function sorts input string, allocate memory for data
# (needed for allLexicographicRecur()) and calls
# allLexicographicRecur() for printing all permutations
def allLexicographic(string):
length = len(string)
# Create a temp array that will be used by
# allLexicographicRecur()
data = [""] * (length+1)
# Sort the input string so that we get all output strings in
# lexicographically sorted order
string = sorted(string)
# Now print all permutations
allLexicographicRecur(string, data, length-1, 0)
# Driver program to test the above functions
string = "ABC"
print ("All permutations with repetition of " + string + " are:")
allLexicographic(string)
# This code is contributed to Bhavya Jain
C#
// C# program to print all permutations
// with repetition of characters
using System;
public class GFG
{
// The main function that recursively prints
// all repeated permutations of the given string.
// It uses data[] to store all permutations one by one
static void allLexicographicRecur(String str, char[] data,
int last, int index)
{
int length = str.Length;
// One by one fix all characters at the given index
// and recur for the subsequent indexes
for (int i = 0; i < length; i++)
{
// Fix the ith character at index and if
// this is not the last index then
// recursively call for higher indexes
data[index] = str[i];
// If this is the last index then print
// the string stored in data[]
if (index == last)
Console.WriteLine(new String(data));
else
allLexicographicRecur(str, data, last,
index + 1);
}
}
// This function sorts input string, allocate memory
// for data(needed for allLexicographicRecur()) and calls
// allLexicographicRecur() for printing all permutations
static void allLexicographic(String str)
{
int length = str.Length;
// Create a temp array that will be used by
// allLexicographicRecur()
char[] data = new char[length + 1];
char[] temp = str.ToCharArray();
// Sort the input string so that we get all
// output strings in lexicographically sorted order
Array.Sort(temp);
str = new String(temp);
// Now print all permutations
allLexicographicRecur(str, data, length - 1, 0);
}
// Driver Code
public static void Main(String[] args)
{
String str = "ABC";
Console.Write("All permutations with " +
"repetition of {0} are: \n", str);
allLexicographic(str);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript code to implement the approach
// The main function that recursively prints
// all repeated permutations of the given string.
// It uses data[] to store all permutations one by one
function allLexicographicRecur(str, data, last, index)
{
let length = str.length;
// One by one fix all letacters at the given index
// and recur for the subsequent indexes
for (let i = 0; i < length; i++)
{
// Fix the ith letacter at index and if
// this is not the last index then
// recursively call for higher indexes
data[index] = str[i];
// If this is the last index then print
// the string stored in data[]
if (index == last)
document.write(new String(data) + "<br/>");
else
allLexicographicRecur(str, data, last,
index + 1);
}
}
// This function sorts input string, allocate memory
// for data(needed for allLexicographicRecur()) and calls
// allLexicographicRecur() for printing all permutations
function allLexicographic(str)
{
let length = str.length;
// Create a temp array that will be used by
// allLexicographicRecur()
let data = new Array(length + 1);
let temp = str.split();
// Sort the input string so that we get all
// output strings in lexicographically sorted order
temp.sort();
str = new String(temp);
// Now print all permutations
allLexicographicRecur(str, data, length - 1, 0);
}
// Driver code
let str = "ABC";
document.write("All permutations with " +
"repetition of " + str + " are " + "<br/>");
allLexicographic(str);
// This code is contributed by sanjoy_62.
</script>
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