Distinct permutations of the string
In this article, we will explore the problem of finding distinct permutations of a given string. We will provide an explanation of the problem statement, present a suitable example, describe a pseudocode algorithm, analyze its time complexity, and finally explain the output.
Introduction
The problem of finding distinct permutations of a string involves generating all possible arrangements of the characters in the string without repeating any permutation. For example, given the string "ABABAB," we want to find all the distinct permutations of this string.
Problem Statement
Given a string of length n, we need to print all possible distinct permutations of the characters in the string.
Example
Let's consider the string "ABABAB" as an example. The distinct permutations of this string are as follows:
ABABAB ABABBA ABAABB ABBAAB ABBABA ABBBAA AABBAB AABBBA AABABB AAABBB BAABAB BAABBA BAAABB BABAAB BABABA BABBAA BBAAAB BBAABA BBABAA BBBAAA
Pseudocode Algorithm
Here is the pseudocode algorithm to generate distinct permutations of a string:
swap(str[], i, j):
temp = str[i]
str[i] = str[j]
str[j] = temp
sequence(str[], start, end):
status = 0
for i = start to end:
if str[i] = str[end]:
status = 1
return status
permutations(str[], n, size):
if n >= size:
return
if n == size - 1:
print str
return
for i = n to size:
if sequence(str, n, i) == 0:
swap(str, i, n)
permutations(str, n + 1, size)
swap(str, i, n)
main():
str1 = "ABABAB"
size = length of str1
print "Permutations of [", str1, "] is"
permutations(str1, 0, size)
str2 = "SIGNING"
size = length of str2
print "Permutations of [", str2, "] is"
permutations(str2, 0, size)
Code Solution
// C Program
// Distinct permutations of the string
#include <stdio.h>
//Swap the character of given index
void swap(char str[],int i,int j)
{
char temp=str[i];
str[i]=str[j];
str[j]=temp;
}
//Check next same element are exist or not
int sequece(char str[],int start,int end)
{
int status=0;
for (int i = start; i < end && status==0; ++i)
{
if(str[i]==str[end])
{
status=1;
}
}
return status;
}
//print all permutations of a string without duplicates
void permutations(char str[],int n ,int size)
{
if(n>=size)
{
return;
}
if(n==size-1)
{
printf("%s\n",str );
return;
}
for (int i = n; i < size; ++i)
{
if(sequece(str,n,i)==0)
{
//perform permutation operation
swap(str,i,n);
permutations(str,n+1,size);
swap(str,i,n);
}
}
}
int main()
{
char str1[]="ABABAB";
//Get the size
int size=sizeof(str1)/sizeof(str1[0])-1;
printf("Permutations of [%s] is \n",str1);
permutations(str1,0,size);
char str2[]="SIGNING";
//Get the size
size=sizeof(str1)/sizeof(str1[0])-1;
printf("\n\nPermutations of [%s] is \n",str2);
permutations(str2,0,size);
return 0;
}
Output
Permutations of [ABABAB] is
ABABAB
ABABBA
ABAABB
ABBAAB
ABBABA
ABBBAA
AABBAB
AABBBA
AABABB
AAABBB
BAABAB
BAABBA
BAAABB
BABAAB
BABABA
BABBAA
BBAAAB
BBAABA
BBABAA
BBBAAA
Permutations of [SIGNING] is
SIGNING
SIGNNIG
SIGINNG
SINGING
SINGNIG
SINIGNG
SININGG
SINNIGG
SINNGIG
SIINGNG
SIINNGG
SIIGNNG
SGINING
SGINNIG
SGIINNG
SGNIING
SGNINIG
SGNNIIG
SNGIING
SNGINIG
SNGNIIG
SNIGING
SNIGNIG
SNIIGNG
SNIINGG
SNINIGG
SNINGIG
SNNIIGG
SNNIGIG
SNNGIIG
ISGNING
ISGNNIG
ISGINNG
ISNGING
ISNGNIG
ISNIGNG
ISNINGG
ISNNIGG
ISNNGIG
ISINGNG
ISINNGG
ISIGNNG
IGSNING
IGSNNIG
IGSINNG
IGNSING
IGNSNIG
IGNISNG
IGNINSG
IGNNISG
IGNNSIG
IGINSNG
IGINNSG
IGISNNG
INGSING
INGSNIG
INGISNG
INGINSG
INGNISG
INGNSIG
INSGING
INSGNIG
INSIGNG
INSINGG
INSNIGG
INSNGIG
INISGNG
INISNGG
INIGSNG
INIGNSG
ININGSG
ININSGG
INNSIGG
INNSGIG
INNISGG
INNIGSG
INNGISG
INNGSIG
IIGNSNG
IIGNNSG
IIGSNNG
IINGSNG
IINGNSG
IINSGNG
IINSNGG
IINNSGG
IINNGSG
IISNGNG
IISNNGG
IISGNNG
GISNING
GISNNIG
GISINNG
GINSING
GINSNIG
GINISNG
GININSG
GINNISG
GINNSIG
GIINSNG
GIINNSG
GIISNNG
GSINING
GSINNIG
GSIINNG
GSNIING
GSNINIG
GSNNIIG
GNSIING
GNSINIG
GNSNIIG
GNISING
GNISNIG
GNIISNG
GNIINSG
GNINISG
GNINSIG
GNNIISG
GNNISIG
GNNSIIG
NIGSING
NIGSNIG
NIGISNG
NIGINSG
NIGNISG
NIGNSIG
NISGING
NISGNIG
NISIGNG
NISINGG
NISNIGG
NISNGIG
NIISGNG
NIISNGG
NIIGSNG
NIIGNSG
NIINGSG
NIINSGG
NINSIGG
NINSGIG
NINISGG
NINIGSG
NINGISG
NINGSIG
NGISING
NGISNIG
NGIISNG
NGIINSG
NGINISG
NGINSIG
NGSIING
NGSINIG
NGSNIIG
NGNSIIG
NGNISIG
NGNIISG
NSGIING
NSGINIG
NSGNIIG
NSIGING
NSIGNIG
NSIIGNG
NSIINGG
NSINIGG
NSINGIG
NSNIIGG
NSNIGIG
NSNGIIG
NNGSIIG
NNGISIG
NNGIISG
NNSGIIG
NNSIGIG
NNSIIGG
NNISGIG
NNISIGG
NNIGSIG
NNIGISG
NNIIGSG
NNIISGG// Java program
// Distinct permutations of the string
public class MyBacktracking
{
//Swapping two string elements by index
public String swap(String text,int size,int a,int b)
{
//Check valid location of swap element
if((a>=0 && a<size) && (b >= 0 && b < size))
{
//Get first character
char first = text.charAt(a);
//Get second character
char second = text.charAt(b);
//Put character
text = text.substring(0, b)
+ first
+ text.substring(b + 1);
text = text.substring(0, a)
+ second
+ text.substring(a + 1);
}
return text;
}
//Check next same element are exist or not
public boolean sequece(String str,int start,int last)
{
boolean status=false;
for (int i = start; i < last && status==false; ++i)
{
if(str.charAt(i)==str.charAt(last))
{
status=true;
}
}
return status;
}
//print all permutations of a string without duplicates
public void permutations(String str,int n ,int size)
{
if(n>=size)
{
return;
}
if(n==size-1)
{
System.out.print(str+"\n" );
return;
}
for (int i = n; i < size; ++i)
{
if(sequece(str,n,i)==false)
{
//perform permutation operation
str=swap(str,size,i,n);
permutations(str,n+1,size);
str=swap(str,size,i,n);
}
}
}
public static void main(String[] args)
{
MyBacktracking obj = new MyBacktracking();
String text = "ABABAB";
int size = text.length();
System.out.print("Permutations of ["+text+"] is \n");
obj.permutations(text,0,size);
text ="SIGNING";
size = text.length();
System.out.print("Permutations of ["+text+"] is \n");
obj.permutations(text,0,size);
}
}
Output
Permutations of [ABABAB] is
ABABAB
ABABBA
ABAABB
ABBAAB
ABBABA
ABBBAA
AABBAB
AABBBA
AABABB
AAABBB
BAABAB
BAABBA
BAAABB
BABAAB
BABABA
BABBAA
BBAAAB
BBAABA
BBABAA
BBBAAA
Permutations of [SIGNING] is
SIGNING
SIGNNIG
SIGINNG
SINGING
SINGNIG
SINIGNG
SININGG
SINNIGG
SINNGIG
SIINGNG
SIINNGG
SIIGNNG
SGINING
SGINNIG
SGIINNG
SGNIING
SGNINIG
SGNNIIG
SNGIING
SNGINIG
SNGNIIG
SNIGING
SNIGNIG
SNIIGNG
SNIINGG
SNINIGG
SNINGIG
SNNIIGG
SNNIGIG
SNNGIIG
ISGNING
ISGNNIG
ISGINNG
ISNGING
ISNGNIG
ISNIGNG
ISNINGG
ISNNIGG
ISNNGIG
ISINGNG
ISINNGG
ISIGNNG
IGSNING
IGSNNIG
IGSINNG
IGNSING
IGNSNIG
IGNISNG
IGNINSG
IGNNISG
IGNNSIG
IGINSNG
IGINNSG
IGISNNG
INGSING
INGSNIG
INGISNG
INGINSG
INGNISG
INGNSIG
INSGING
INSGNIG
INSIGNG
INSINGG
INSNIGG
INSNGIG
INISGNG
INISNGG
INIGSNG
INIGNSG
ININGSG
ININSGG
INNSIGG
INNSGIG
INNISGG
INNIGSG
INNGISG
INNGSIG
IIGNSNG
IIGNNSG
IIGSNNG
IINGSNG
IINGNSG
IINSGNG
IINSNGG
IINNSGG
IINNGSG
IISNGNG
IISNNGG
IISGNNG
GISNING
GISNNIG
GISINNG
GINSING
GINSNIG
GINISNG
GININSG
GINNISG
GINNSIG
GIINSNG
GIINNSG
GIISNNG
GSINING
GSINNIG
GSIINNG
GSNIING
GSNINIG
GSNNIIG
GNSIING
GNSINIG
GNSNIIG
GNISING
GNISNIG
GNIISNG
GNIINSG
GNINISG
GNINSIG
GNNIISG
GNNISIG
GNNSIIG
NIGSING
NIGSNIG
NIGISNG
NIGINSG
NIGNISG
NIGNSIG
NISGING
NISGNIG
NISIGNG
NISINGG
NISNIGG
NISNGIG
NIISGNG
NIISNGG
NIIGSNG
NIIGNSG
NIINGSG
NIINSGG
NINSIGG
NINSGIG
NINISGG
NINIGSG
NINGISG
NINGSIG
NGISING
NGISNIG
NGIISNG
NGIINSG
NGINISG
NGINSIG
NGSIING
NGSINIG
NGSNIIG
NGNSIIG
NGNISIG
NGNIISG
NSGIING
NSGINIG
NSGNIIG
NSIGING
NSIGNIG
NSIIGNG
NSIINGG
NSINIGG
NSINGIG
NSNIIGG
NSNIGIG
NSNGIIG
NNGSIIG
NNGISIG
NNGIISG
NNSGIIG
NNSIGIG
NNSIIGG
NNISGIG
NNISIGG
NNIGSIG
NNIGISG
NNIIGSG
NNIISGG// C++ program
// Distinct permutations of the string
#include<iostream>
using namespace std;
class MyBacktracking {
public:
//Swap the string element of given indexes
string swap(string text,int size,int a,int b)
{
if((a>=0 && a<size) && (b >= 0 && b < size))
{
//When valid a and b location
char temp = text[a];
text[a] = text[b];
text[b] = temp;
}
//return modified result
return text;
}
//Check next same element are exist or not
bool sequece(string str, int start, int last) {
bool status = false;
for (int i = start; i < last &&
status == false; ++i) {
if (str[i] == str[last]) {
status = true;
}
}
return status;
}
//print all permutations of a string without duplicates
void permutations(string str, int n, int size) {
if (n >= size) {
return;
}
if (n == size - 1) {
cout << str << "\n";
return;
}
for (int i = n; i < size; ++i) {
if (this->sequece(str, n, i) == false) {
//perform permutation operation
str = this->swap(str, size, i, n);
this->permutations(str, n + 1, size);
str = this->swap(str, size, i, n);
}
}
}
};
int main() {
MyBacktracking obj = MyBacktracking();
string text = "ABABAB";
int size = text.size();
cout << "Permutations of [" << text << "] is \n";
obj.permutations(text, 0, size);
text = "SIGNING";
size = text.size();
cout << "Permutations of [" << text << "] is \n";
obj.permutations(text, 0, size);
return 0;
}
Output
Permutations of [ABABAB] is
ABABAB
ABABBA
ABAABB
ABBAAB
ABBABA
ABBBAA
AABBAB
AABBBA
AABABB
AAABBB
BAABAB
BAABBA
BAAABB
BABAAB
BABABA
BABBAA
BBAAAB
BBAABA
BBABAA
BBBAAA
Permutations of [SIGNING] is
SIGNING
SIGNIGN
SIGNNIG
SIGNNGI
SIGNGNI
SIGNGIN
SIGINNG
SIGINGN
SIGIGNN
SIGGINN
SIGGNIN
SIGGNNI
SINGING
SINGIGN
SINGNIG
SINGNGI
SINGGNI
SINGGIN
SINIGNG
SINIGGN
SININGG
SINNIGG
SINNGIG
SINNGGI
SIINGNG
SIINGGN
SIINNGG
SIIGNNG
SIIGNGN
SIIGGNN
SGINING
SGINIGN
SGINNIG
SGINNGI
SGINGNI
SGINGIN
SGIINNG
SGIINGN
SGIIGNN
SGIGINN
SGIGNIN
SGIGNNI
SGNIING
SGNIIGN
SGNINIG
SGNINGI
SGNIGNI
SGNIGIN
SGNNIIG
SGNNIGI
SGNNGII
SGNGINI
SGNGIIN
SGNGNII
SGGNINI
SGGNIIN
SGGNNII
SGGINNI
SGGININ
SGGIINN
SNGIING
SNGIIGN
SNGINIG
SNGINGI
SNGIGNI
SNGIGIN
SNGNIIG
SNGNIGI
SNGNGII
SNGGINI
SNGGIIN
SNGGNII
SNIGING
SNIGIGN
SNIGNIG
SNIGNGI
SNIGGNI
SNIGGIN
SNIIGNG
SNIIGGN
SNIINGG
SNINIGG
SNINGIG
SNINGGI
SNNIIGG
SNNIGIG
SNNIGGI
SNNGIIG
SNNGIGI
SNNGGII
ISGNING
ISGNIGN
ISGNNIG
ISGNNGI
ISGNGNI
ISGNGIN
ISGINNG
ISGINGN
ISGIGNN
ISGGINN
ISGGNIN
ISGGNNI
ISNGING
ISNGIGN
ISNGNIG
ISNGNGI
ISNGGNI
ISNGGIN
ISNIGNG
ISNIGGN
ISNINGG
ISNNIGG
ISNNGIG
ISNNGGI
ISINGNG
ISINGGN
ISINNGG
ISIGNNG
ISIGNGN
ISIGGNN
IGSNING
IGSNIGN
IGSNNIG
IGSNNGI
IGSNGNI
IGSNGIN
IGSINNG
IGSINGN
IGSIGNN
IGSGINN
IGSGNIN
IGSGNNI
IGNSING
IGNSIGN
IGNSNIG
IGNSNGI
IGNSGNI
IGNSGIN
IGNISNG
IGNISGN
IGNINSG
IGNINGS
IGNIGNS
IGNIGSN
IGNNISG
IGNNIGS
IGNNSIG
IGNNSGI
IGNNGSI
IGNNGIS
IGNGINS
IGNGISN
IGNGNIS
IGNGNSI
IGNGSNI
IGNGSIN
IGINSNG
IGINSGN
IGINNSG
IGINNGS
IGINGNS
IGINGSN
IGISNNG
IGISNGN
IGISGNN
IGIGSNN
IGIGNSN
IGIGNNS
IGGNINS
IGGNISN
IGGNNIS
IGGNNSI
IGGNSNI
IGGNSIN
IGGINNS
IGGINSN
IGGISNN
IGGSINN
IGGSNIN
IGGSNNI
INGSING
INGSIGN
INGSNIG
INGSNGI
INGSGNI
INGSGIN
INGISNG
INGISGN
INGINSG
INGINGS
INGIGNS
INGIGSN
INGNISG
INGNIGS
INGNSIG
INGNSGI
INGNGSI
INGNGIS
INGGINS
INGGISN
INGGNIS
INGGNSI
INGGSNI
INGGSIN
INSGING
INSGIGN
INSGNIG
INSGNGI
INSGGNI
INSGGIN
INSIGNG
INSIGGN
INSINGG
INSNIGG
INSNGIG
INSNGGI
INISGNG
INISGGN
INISNGG
INIGSNG
INIGSGN
INIGNSG
INIGNGS
INIGGNS
INIGGSN
ININGSG
ININGGS
ININSGG
INNSIGG
INNSGIG
INNSGGI
INNISGG
INNIGSG
INNIGGS
INNGISG
INNGIGS
INNGSIG
INNGSGI
INNGGSI
INNGGIS
IIGNSNG
IIGNSGN
IIGNNSG
IIGNNGS
IIGNGNS
IIGNGSN
IIGSNNG
IIGSNGN
IIGSGNN
IIGGSNN
IIGGNSN
IIGGNNS
IINGSNG
IINGSGN
IINGNSG
IINGNGS
IINGGNS
IINGGSN
IINSGNG
IINSGGN
IINSNGG
IINNSGG
IINNGSG
IINNGGS
IISNGNG
IISNGGN
IISNNGG
IISGNNG
IISGNGN
IISGGNN
GISNING
GISNIGN
GISNNIG
GISNNGI
GISNGNI
GISNGIN
GISINNG
GISINGN
GISIGNN
GISGINN
GISGNIN
GISGNNI
GINSING
GINSIGN
GINSNIG
GINSNGI
GINSGNI
GINSGIN
GINISNG
GINISGN
GININSG
GININGS
GINIGNS
GINIGSN
GINNISG
GINNIGS
GINNSIG
GINNSGI
GINNGSI
GINNGIS
GINGINS
GINGISN
GINGNIS
GINGNSI
GINGSNI
GINGSIN
GIINSNG
GIINSGN
GIINNSG
GIINNGS
GIINGNS
GIINGSN
GIISNNG
GIISNGN
GIISGNN
GIIGSNN
GIIGNSN
GIIGNNS
GIGNINS
GIGNISN
GIGNNIS
GIGNNSI
GIGNSNI
GIGNSIN
GIGINNS
GIGINSN
GIGISNN
GIGSINN
GIGSNIN
GIGSNNI
GSINING
GSINIGN
GSINNIG
GSINNGI
GSINGNI
GSINGIN
GSIINNG
GSIINGN
GSIIGNN
GSIGINN
GSIGNIN
GSIGNNI
GSNIING
GSNIIGN
GSNINIG
GSNINGI
GSNIGNI
GSNIGIN
GSNNIIG
GSNNIGI
GSNNGII
GSNGINI
GSNGIIN
GSNGNII
GSGNINI
GSGNIIN
GSGNNII
GSGINNI
GSGININ
GSGIINN
GNSIING
GNSIIGN
GNSINIG
GNSINGI
GNSIGNI
GNSIGIN
GNSNIIG
GNSNIGI
GNSNGII
GNSGINI
GNSGIIN
GNSGNII
GNISING
GNISIGN
GNISNIG
GNISNGI
GNISGNI
GNISGIN
GNIISNG
GNIISGN
GNIINSG
GNIINGS
GNIIGNS
GNIIGSN
GNINISG
GNINIGS
GNINSIG
GNINSGI
GNINGSI
GNINGIS
GNIGINS
GNIGISN
GNIGNIS
GNIGNSI
GNIGSNI
GNIGSIN
GNNIISG
GNNIIGS
GNNISIG
GNNISGI
GNNIGSI
GNNIGIS
GNNSIIG
GNNSIGI
GNNSGII
GNNGISI
GNNGIIS
GNNGSII
GNGIINS
GNGIISN
GNGINIS
GNGINSI
GNGISNI
GNGISIN
GNGNIIS
GNGNISI
GNGNSII
GNGSINI
GNGSIIN
GNGSNII
GGSNINI
GGSNIIN
GGSNNII
GGSINNI
GGSININ
GGSIINN
GGNSINI
GGNSIIN
GGNSNII
GGNISNI
GGNISIN
GGNINSI
GGNINIS
GGNIINS
GGNIISN
GGNNISI
GGNNIIS
GGNNSII
GGINSNI
GGINSIN
GGINNSI
GGINNIS
GGININS
GGINISN
GGISNNI
GGISNIN
GGISINN
GGIISNN
GGIINSN
GGIINNS
NIGSING
NIGSIGN
NIGSNIG
NIGSNGI
NIGSGNI
NIGSGIN
NIGISNG
NIGISGN
NIGINSG
NIGINGS
NIGIGNS
NIGIGSN
NIGNISG
NIGNIGS
NIGNSIG
NIGNSGI
NIGNGSI
NIGNGIS
NIGGINS
NIGGISN
NIGGNIS
NIGGNSI
NIGGSNI
NIGGSIN
NISGING
NISGIGN
NISGNIG
NISGNGI
NISGGNI
NISGGIN
NISIGNG
NISIGGN
NISINGG
NISNIGG
NISNGIG
NISNGGI
NIISGNG
NIISGGN
NIISNGG
NIIGSNG
NIIGSGN
NIIGNSG
NIIGNGS
NIIGGNS
NIIGGSN
NIINGSG
NIINGGS
NIINSGG
NINSIGG
NINSGIG
NINSGGI
NINISGG
NINIGSG
NINIGGS
NINGISG
NINGIGS
NINGSIG
NINGSGI
NINGGSI
NINGGIS
NGISING
NGISIGN
NGISNIG
NGISNGI
NGISGNI
NGISGIN
NGIISNG
NGIISGN
NGIINSG
NGIINGS
NGIIGNS
NGIIGSN
NGINISG
NGINIGS
NGINSIG
NGINSGI
NGINGSI
NGINGIS
NGIGINS
NGIGISN
NGIGNIS
NGIGNSI
NGIGSNI
NGIGSIN
NGSIING
NGSIIGN
NGSINIG
NGSINGI
NGSIGNI
NGSIGIN
NGSNIIG
NGSNIGI
NGSNGII
NGSGINI
NGSGIIN
NGSGNII
NGNSIIG
NGNSIGI
NGNSGII
NGNISIG
NGNISGI
NGNIISG
NGNIIGS
NGNIGIS
NGNIGSI
NGNGIIS
NGNGISI
NGNGSII
NGGSINI
NGGSIIN
NGGSNII
NGGISNI
NGGISIN
NGGINSI
NGGINIS
NGGIINS
NGGIISN
NGGNISI
NGGNIIS
NGGNSII
NSGIING
NSGIIGN
NSGINIG
NSGINGI
NSGIGNI
NSGIGIN
NSGNIIG
NSGNIGI
NSGNGII
NSGGINI
NSGGIIN
NSGGNII
NSIGING
NSIGIGN
NSIGNIG
NSIGNGI
NSIGGNI
NSIGGIN
NSIIGNG
NSIIGGN
NSIINGG
NSINIGG
NSINGIG
NSINGGI
NSNIIGG
NSNIGIG
NSNIGGI
NSNGIIG
NSNGIGI
NSNGGII
NNGSIIG
NNGSIGI
NNGSGII
NNGISIG
NNGISGI
NNGIISG
NNGIIGS
NNGIGIS
NNGIGSI
NNGGIIS
NNGGISI
NNGGSII
NNSGIIG
NNSGIGI
NNSGGII
NNSIGIG
NNSIGGI
NNSIIGG
NNISGIG
NNISGGI
NNISIGG
NNIGSIG
NNIGSGI
NNIGISG
NNIGIGS
NNIGGIS
NNIGGSI
NNIIGSG
NNIIGGS
NNIISGG// C# program
// Distinct permutations of the string
using System;
public class MyBacktracking {
//Swapping two string elements by index
public String swap(String text, int size, int a, int b) {
//Check valid location of swap element
if ((a >= 0 && a < size) && (b >= 0 && b < size)) {
//Get first character
char first = text[a];
//Get second character
char second = text[b];
//Put characters
text = text.Substring(0, b) + first + text.Substring(b + 1);
text = text.Substring(0, a) + second + text.Substring(a + 1);
}
//important this text are modified inside a function.
//return modified text and assign on actual text variable
return text;
}
//Check next same element are exist or not
public Boolean sequece(String str, int start, int last) {
Boolean status = false;
for (int i = start; i < last &&
status == false; ++i) {
if (str[i] == str[last]) {
status = true;
}
}
return status;
}
//print all permutations of a string without duplicates
public void permutations(String str, int n, int size) {
if (n >= size) {
return;
}
if (n == size - 1) {
Console.Write(str + "\n");
return;
}
for (int i = n; i < size; ++i) {
if (sequece(str, n, i) == false) {
//perform permutation operation
str = swap(str, size, i, n);
permutations(str, n + 1, size);
str = swap(str, size, i, n);
}
}
}
public static void Main(String[] args) {
MyBacktracking obj = new MyBacktracking();
String text = "ABABAB";
int size = text.Length;
Console.Write("Permutations of [" + text + "] is \n");
obj.permutations(text, 0, size);
text = "SIGNING";
size = text.Length;
Console.Write("Permutations of [" + text + "] is \n");
obj.permutations(text, 0, size);
}
}
Output
Permutations of [ABABAB] is
ABABAB
ABABBA
ABAABB
ABBAAB
ABBABA
ABBBAA
AABBAB
AABBBA
AABABB
AAABBB
BAABAB
BAABBA
BAAABB
BABAAB
BABABA
BABBAA
BBAAAB
BBAABA
BBABAA
BBBAAA
Permutations of [SIGNING] is
SIGNING
SIGNIGN
SIGNNIG
SIGNNGI
SIGNGNI
SIGNGIN
SIGINNG
SIGINGN
SIGIGNN
SIGGINN
SIGGNIN
SIGGNNI
SINGING
SINGIGN
SINGNIG
SINGNGI
SINGGNI
SINGGIN
SINIGNG
SINIGGN
SININGG
SINNIGG
SINNGIG
SINNGGI
SIINGNG
SIINGGN
SIINNGG
SIIGNNG
SIIGNGN
SIIGGNN
SGINING
SGINIGN
SGINNIG
SGINNGI
SGINGNI
SGINGIN
SGIINNG
SGIINGN
SGIIGNN
SGIGINN
SGIGNIN
SGIGNNI
SGNIING
SGNIIGN
SGNINIG
SGNINGI
SGNIGNI
SGNIGIN
SGNNIIG
SGNNIGI
SGNNGII
SGNGINI
SGNGIIN
SGNGNII
SGGNINI
SGGNIIN
SGGNNII
SGGINNI
SGGININ
SGGIINN
SNGIING
SNGIIGN
SNGINIG
SNGINGI
SNGIGNI
SNGIGIN
SNGNIIG
SNGNIGI
SNGNGII
SNGGINI
SNGGIIN
SNGGNII
SNIGING
SNIGIGN
SNIGNIG
SNIGNGI
SNIGGNI
SNIGGIN
SNIIGNG
SNIIGGN
SNIINGG
SNINIGG
SNINGIG
SNINGGI
SNNIIGG
SNNIGIG
SNNIGGI
SNNGIIG
SNNGIGI
SNNGGII
ISGNING
ISGNIGN
ISGNNIG
ISGNNGI
ISGNGNI
ISGNGIN
ISGINNG
ISGINGN
ISGIGNN
ISGGINN
ISGGNIN
ISGGNNI
ISNGING
ISNGIGN
ISNGNIG
ISNGNGI
ISNGGNI
ISNGGIN
ISNIGNG
ISNIGGN
ISNINGG
ISNNIGG
ISNNGIG
ISNNGGI
ISINGNG
ISINGGN
ISINNGG
ISIGNNG
ISIGNGN
ISIGGNN
IGSNING
IGSNIGN
IGSNNIG
IGSNNGI
IGSNGNI
IGSNGIN
IGSINNG
IGSINGN
IGSIGNN
IGSGINN
IGSGNIN
IGSGNNI
IGNSING
IGNSIGN
IGNSNIG
IGNSNGI
IGNSGNI
IGNSGIN
IGNISNG
IGNISGN
IGNINSG
IGNINGS
IGNIGNS
IGNIGSN
IGNNISG
IGNNIGS
IGNNSIG
IGNNSGI
IGNNGSI
IGNNGIS
IGNGINS
IGNGISN
IGNGNIS
IGNGNSI
IGNGSNI
IGNGSIN
IGINSNG
IGINSGN
IGINNSG
IGINNGS
IGINGNS
IGINGSN
IGISNNG
IGISNGN
IGISGNN
IGIGSNN
IGIGNSN
IGIGNNS
IGGNINS
IGGNISN
IGGNNIS
IGGNNSI
IGGNSNI
IGGNSIN
IGGINNS
IGGINSN
IGGISNN
IGGSINN
IGGSNIN
IGGSNNI
INGSING
INGSIGN
INGSNIG
INGSNGI
INGSGNI
INGSGIN
INGISNG
INGISGN
INGINSG
INGINGS
INGIGNS
INGIGSN
INGNISG
INGNIGS
INGNSIG
INGNSGI
INGNGSI
INGNGIS
INGGINS
INGGISN
INGGNIS
INGGNSI
INGGSNI
INGGSIN
INSGING
INSGIGN
INSGNIG
INSGNGI
INSGGNI
INSGGIN
INSIGNG
INSIGGN
INSINGG
INSNIGG
INSNGIG
INSNGGI
INISGNG
INISGGN
INISNGG
INIGSNG
INIGSGN
INIGNSG
INIGNGS
INIGGNS
INIGGSN
ININGSG
ININGGS
ININSGG
INNSIGG
INNSGIG
INNSGGI
INNISGG
INNIGSG
INNIGGS
INNGISG
INNGIGS
INNGSIG
INNGSGI
INNGGSI
INNGGIS
IIGNSNG
IIGNSGN
IIGNNSG
IIGNNGS
IIGNGNS
IIGNGSN
IIGSNNG
IIGSNGN
IIGSGNN
IIGGSNN
IIGGNSN
IIGGNNS
IINGSNG
IINGSGN
IINGNSG
IINGNGS
IINGGNS
IINGGSN
IINSGNG
IINSGGN
IINSNGG
IINNSGG
IINNGSG
IINNGGS
IISNGNG
IISNGGN
IISNNGG
IISGNNG
IISGNGN
IISGGNN
GISNING
GISNIGN
GISNNIG
GISNNGI
GISNGNI
GISNGIN
GISINNG
GISINGN
GISIGNN
GISGINN
GISGNIN
GISGNNI
GINSING
GINSIGN
GINSNIG
GINSNGI
GINSGNI
GINSGIN
GINISNG
GINISGN
GININSG
GININGS
GINIGNS
GINIGSN
GINNISG
GINNIGS
GINNSIG
GINNSGI
GINNGSI
GINNGIS
GINGINS
GINGISN
GINGNIS
GINGNSI
GINGSNI
GINGSIN
GIINSNG
GIINSGN
GIINNSG
GIINNGS
GIINGNS
GIINGSN
GIISNNG
GIISNGN
GIISGNN
GIIGSNN
GIIGNSN
GIIGNNS
GIGNINS
GIGNISN
GIGNNIS
GIGNNSI
GIGNSNI
GIGNSIN
GIGINNS
GIGINSN
GIGISNN
GIGSINN
GIGSNIN
GIGSNNI
GSINING
GSINIGN
GSINNIG
GSINNGI
GSINGNI
GSINGIN
GSIINNG
GSIINGN
GSIIGNN
GSIGINN
GSIGNIN
GSIGNNI
GSNIING
GSNIIGN
GSNINIG
GSNINGI
GSNIGNI
GSNIGIN
GSNNIIG
GSNNIGI
GSNNGII
GSNGINI
GSNGIIN
GSNGNII
GSGNINI
GSGNIIN
GSGNNII
GSGINNI
GSGININ
GSGIINN
GNSIING
GNSIIGN
GNSINIG
GNSINGI
GNSIGNI
GNSIGIN
GNSNIIG
GNSNIGI
GNSNGII
GNSGINI
GNSGIIN
GNSGNII
GNISING
GNISIGN
GNISNIG
GNISNGI
GNISGNI
GNISGIN
GNIISNG
GNIISGN
GNIINSG
GNIINGS
GNIIGNS
GNIIGSN
GNINISG
GNINIGS
GNINSIG
GNINSGI
GNINGSI
GNINGIS
GNIGINS
GNIGISN
GNIGNIS
GNIGNSI
GNIGSNI
GNIGSIN
GNNIISG
GNNIIGS
GNNISIG
GNNISGI
GNNIGSI
GNNIGIS
GNNSIIG
GNNSIGI
GNNSGII
GNNGISI
GNNGIIS
GNNGSII
GNGIINS
GNGIISN
GNGINIS
GNGINSI
GNGISNI
GNGISIN
GNGNIIS
GNGNISI
GNGNSII
GNGSINI
GNGSIIN
GNGSNII
GGSNINI
GGSNIIN
GGSNNII
GGSINNI
GGSININ
GGSIINN
GGNSINI
GGNSIIN
GGNSNII
GGNISNI
GGNISIN
GGNINSI
GGNINIS
GGNIINS
GGNIISN
GGNNISI
GGNNIIS
GGNNSII
GGINSNI
GGINSIN
GGINNSI
GGINNIS
GGININS
GGINISN
GGISNNI
GGISNIN
GGISINN
GGIISNN
GGIINSN
GGIINNS
NIGSING
NIGSIGN
NIGSNIG
NIGSNGI
NIGSGNI
NIGSGIN
NIGISNG
NIGISGN
NIGINSG
NIGINGS
NIGIGNS
NIGIGSN
NIGNISG
NIGNIGS
NIGNSIG
NIGNSGI
NIGNGSI
NIGNGIS
NIGGINS
NIGGISN
NIGGNIS
NIGGNSI
NIGGSNI
NIGGSIN
NISGING
NISGIGN
NISGNIG
NISGNGI
NISGGNI
NISGGIN
NISIGNG
NISIGGN
NISINGG
NISNIGG
NISNGIG
NISNGGI
NIISGNG
NIISGGN
NIISNGG
NIIGSNG
NIIGSGN
NIIGNSG
NIIGNGS
NIIGGNS
NIIGGSN
NIINGSG
NIINGGS
NIINSGG
NINSIGG
NINSGIG
NINSGGI
NINISGG
NINIGSG
NINIGGS
NINGISG
NINGIGS
NINGSIG
NINGSGI
NINGGSI
NINGGIS
NGISING
NGISIGN
NGISNIG
NGISNGI
NGISGNI
NGISGIN
NGIISNG
NGIISGN
NGIINSG
NGIINGS
NGIIGNS
NGIIGSN
NGINISG
NGINIGS
NGINSIG
NGINSGI
NGINGSI
NGINGIS
NGIGINS
NGIGISN
NGIGNIS
NGIGNSI
NGIGSNI
NGIGSIN
NGSIING
NGSIIGN
NGSINIG
NGSINGI
NGSIGNI
NGSIGIN
NGSNIIG
NGSNIGI
NGSNGII
NGSGINI
NGSGIIN
NGSGNII
NGNSIIG
NGNSIGI
NGNSGII
NGNISIG
NGNISGI
NGNIISG
NGNIIGS
NGNIGIS
NGNIGSI
NGNGIIS
NGNGISI
NGNGSII
NGGSINI
NGGSIIN
NGGSNII
NGGISNI
NGGISIN
NGGINSI
NGGINIS
NGGIINS
NGGIISN
NGGNISI
NGGNIIS
NGGNSII
NSGIING
NSGIIGN
NSGINIG
NSGINGI
NSGIGNI
NSGIGIN
NSGNIIG
NSGNIGI
NSGNGII
NSGGINI
NSGGIIN
NSGGNII
NSIGING
NSIGIGN
NSIGNIG
NSIGNGI
NSIGGNI
NSIGGIN
NSIIGNG
NSIIGGN
NSIINGG
NSINIGG
NSINGIG
NSINGGI
NSNIIGG
NSNIGIG
NSNIGGI
NSNGIIG
NSNGIGI
NSNGGII
NNGSIIG
NNGSIGI
NNGSGII
NNGISIG
NNGISGI
NNGIISG
NNGIIGS
NNGIGIS
NNGIGSI
NNGGIIS
NNGGISI
NNGGSII
NNSGIIG
NNSGIGI
NNSGGII
NNSIGIG
NNSIGGI
NNSIIGG
NNISGIG
NNISGGI
NNISIGG
NNIGSIG
NNIGSGI
NNIGISG
NNIGIGS
NNIGGIS
NNIGGSI
NNIIGSG
NNIIGGS
NNIISGG<?php
// Php program
// Distinct permutations of the string
class MyBacktracking {
//Swapping two string elements by index
public function swap($text, $size, $a, $b) {
//Check valid location of swap element
if (($a >= 0 && $a < $size) && ($b >= 0 && $b < $size)) {
//Get first character
$first = $text[$a];
//Get second character
$second = $text[$b];
//Put character
$text = substr($text,0, $b-strlen($text)) . $first .substr($text,$b+1 );
$text = substr($text,0, $a-strlen($text)) . $second .substr($text,$a+1 );
}
return $text;
}
//Check next same element are exist or not
public function sequece($str, $start, $last) {
$status = false;
for ($i = $start; $i < $last &&
$status == false; ++$i) {
if ($str[$i] == $str[$last]) {
$status = true;
}
}
return $status;
}
//print all permutations of a string without duplicates
public function permutations($str, $n, $size) {
if ($n >= $size) {
return;
}
if ($n == $size - 1) {
echo($str ."\n");
return;
}
for ($i = $n; $i < $size; ++$i) {
if ($this->sequece($str, $n, $i) == false) {
//perform permutation operation
$str = $this->swap($str, $size, $i, $n);
$this->permutations($str, $n + 1, $size);
$str = $this->swap($str, $size, $i, $n);
}
}
}
}
function main() {
$obj = new MyBacktracking();
$text = "ABABAB";
$size = strlen($text);
echo("Permutations of [". $text ."] is \n");
$obj->permutations($text, 0, $size);
$text = "SIGNING";
$size = strlen($text);
echo("Permutations of [". $text ."] is \n");
$obj->permutations($text, 0, $size);
}
main();
Output
Permutations of [ABABAB] is
ABABAB
ABABBA
ABAABB
ABBAAB
ABBABA
ABBBAA
AABBAB
AABBBA
AABABB
AAABBB
BAABAB
BAABBA
BAAABB
BABAAB
BABABA
BABBAA
BBAAAB
BBAABA
BBABAA
BBBAAA
Permutations of [SIGNING] is
SIGNING
SIGNIGN
SIGNNIG
SIGNNGI
SIGNGNI
SIGNGIN
SIGINNG
SIGINGN
SIGIGNN
SIGGINN
SIGGNIN
SIGGNNI
SINGING
SINGIGN
SINGNIG
SINGNGI
SINGGNI
SINGGIN
SINIGNG
SINIGGN
SININGG
SINNIGG
SINNGIG
SINNGGI
SIINGNG
SIINGGN
SIINNGG
SIIGNNG
SIIGNGN
SIIGGNN
SGINING
SGINIGN
SGINNIG
SGINNGI
SGINGNI
SGINGIN
SGIINNG
SGIINGN
SGIIGNN
SGIGINN
SGIGNIN
SGIGNNI
SGNIING
SGNIIGN
SGNINIG
SGNINGI
SGNIGNI
SGNIGIN
SGNNIIG
SGNNIGI
SGNNGII
SGNGINI
SGNGIIN
SGNGNII
SGGNINI
SGGNIIN
SGGNNII
SGGINNI
SGGININ
SGGIINN
SNGIING
SNGIIGN
SNGINIG
SNGINGI
SNGIGNI
SNGIGIN
SNGNIIG
SNGNIGI
SNGNGII
SNGGINI
SNGGIIN
SNGGNII
SNIGING
SNIGIGN
SNIGNIG
SNIGNGI
SNIGGNI
SNIGGIN
SNIIGNG
SNIIGGN
SNIINGG
SNINIGG
SNINGIG
SNINGGI
SNNIIGG
SNNIGIG
SNNIGGI
SNNGIIG
SNNGIGI
SNNGGII
ISGNING
ISGNIGN
ISGNNIG
ISGNNGI
ISGNGNI
ISGNGIN
ISGINNG
ISGINGN
ISGIGNN
ISGGINN
ISGGNIN
ISGGNNI
ISNGING
ISNGIGN
ISNGNIG
ISNGNGI
ISNGGNI
ISNGGIN
ISNIGNG
ISNIGGN
ISNINGG
ISNNIGG
ISNNGIG
ISNNGGI
ISINGNG
ISINGGN
ISINNGG
ISIGNNG
ISIGNGN
ISIGGNN
IGSNING
IGSNIGN
IGSNNIG
IGSNNGI
IGSNGNI
IGSNGIN
IGSINNG
IGSINGN
IGSIGNN
IGSGINN
IGSGNIN
IGSGNNI
IGNSING
IGNSIGN
IGNSNIG
IGNSNGI
IGNSGNI
IGNSGIN
IGNISNG
IGNISGN
IGNINSG
IGNINGS
IGNIGNS
IGNIGSN
IGNNISG
IGNNIGS
IGNNSIG
IGNNSGI
IGNNGSI
IGNNGIS
IGNGINS
IGNGISN
IGNGNIS
IGNGNSI
IGNGSNI
IGNGSIN
IGINSNG
IGINSGN
IGINNSG
IGINNGS
IGINGNS
IGINGSN
IGISNNG
IGISNGN
IGISGNN
IGIGSNN
IGIGNSN
IGIGNNS
IGGNINS
IGGNISN
IGGNNIS
IGGNNSI
IGGNSNI
IGGNSIN
IGGINNS
IGGINSN
IGGISNN
IGGSINN
IGGSNIN
IGGSNNI
INGSING
INGSIGN
INGSNIG
INGSNGI
INGSGNI
INGSGIN
INGISNG
INGISGN
INGINSG
INGINGS
INGIGNS
INGIGSN
INGNISG
INGNIGS
INGNSIG
INGNSGI
INGNGSI
INGNGIS
INGGINS
INGGISN
INGGNIS
INGGNSI
INGGSNI
INGGSIN
INSGING
INSGIGN
INSGNIG
INSGNGI
INSGGNI
INSGGIN
INSIGNG
INSIGGN
INSINGG
INSNIGG
INSNGIG
INSNGGI
INISGNG
INISGGN
INISNGG
INIGSNG
INIGSGN
INIGNSG
INIGNGS
INIGGNS
INIGGSN
ININGSG
ININGGS
ININSGG
INNSIGG
INNSGIG
INNSGGI
INNISGG
INNIGSG
INNIGGS
INNGISG
INNGIGS
INNGSIG
INNGSGI
INNGGSI
INNGGIS
IIGNSNG
IIGNSGN
IIGNNSG
IIGNNGS
IIGNGNS
IIGNGSN
IIGSNNG
IIGSNGN
IIGSGNN
IIGGSNN
IIGGNSN
IIGGNNS
IINGSNG
IINGSGN
IINGNSG
IINGNGS
IINGGNS
IINGGSN
IINSGNG
IINSGGN
IINSNGG
IINNSGG
IINNGSG
IINNGGS
IISNGNG
IISNGGN
IISNNGG
IISGNNG
IISGNGN
IISGGNN
GISNING
GISNIGN
GISNNIG
GISNNGI
GISNGNI
GISNGIN
GISINNG
GISINGN
GISIGNN
GISGINN
GISGNIN
GISGNNI
GINSING
GINSIGN
GINSNIG
GINSNGI
GINSGNI
GINSGIN
GINISNG
GINISGN
GININSG
GININGS
GINIGNS
GINIGSN
GINNISG
GINNIGS
GINNSIG
GINNSGI
GINNGSI
GINNGIS
GINGINS
GINGISN
GINGNIS
GINGNSI
GINGSNI
GINGSIN
GIINSNG
GIINSGN
GIINNSG
GIINNGS
GIINGNS
GIINGSN
GIISNNG
GIISNGN
GIISGNN
GIIGSNN
GIIGNSN
GIIGNNS
GIGNINS
GIGNISN
GIGNNIS
GIGNNSI
GIGNSNI
GIGNSIN
GIGINNS
GIGINSN
GIGISNN
GIGSINN
GIGSNIN
GIGSNNI
GSINING
GSINIGN
GSINNIG
GSINNGI
GSINGNI
GSINGIN
GSIINNG
GSIINGN
GSIIGNN
GSIGINN
GSIGNIN
GSIGNNI
GSNIING
GSNIIGN
GSNINIG
GSNINGI
GSNIGNI
GSNIGIN
GSNNIIG
GSNNIGI
GSNNGII
GSNGINI
GSNGIIN
GSNGNII
GSGNINI
GSGNIIN
GSGNNII
GSGINNI
GSGININ
GSGIINN
GNSIING
GNSIIGN
GNSINIG
GNSINGI
GNSIGNI
GNSIGIN
GNSNIIG
GNSNIGI
GNSNGII
GNSGINI
GNSGIIN
GNSGNII
GNISING
GNISIGN
GNISNIG
GNISNGI
GNISGNI
GNISGIN
GNIISNG
GNIISGN
GNIINSG
GNIINGS
GNIIGNS
GNIIGSN
GNINISG
GNINIGS
GNINSIG
GNINSGI
GNINGSI
GNINGIS
GNIGINS
GNIGISN
GNIGNIS
GNIGNSI
GNIGSNI
GNIGSIN
GNNIISG
GNNIIGS
GNNISIG
GNNISGI
GNNIGSI
GNNIGIS
GNNSIIG
GNNSIGI
GNNSGII
GNNGISI
GNNGIIS
GNNGSII
GNGIINS
GNGIISN
GNGINIS
GNGINSI
GNGISNI
GNGISIN
GNGNIIS
GNGNISI
GNGNSII
GNGSINI
GNGSIIN
GNGSNII
GGSNINI
GGSNIIN
GGSNNII
GGSINNI
GGSININ
GGSIINN
GGNSINI
GGNSIIN
GGNSNII
GGNISNI
GGNISIN
GGNINSI
GGNINIS
GGNIINS
GGNIISN
GGNNISI
GGNNIIS
GGNNSII
GGINSNI
GGINSIN
GGINNSI
GGINNIS
GGININS
GGINISN
GGISNNI
GGISNIN
GGISINN
GGIISNN
GGIINSN
GGIINNS
NIGSING
NIGSIGN
NIGSNIG
NIGSNGI
NIGSGNI
NIGSGIN
NIGISNG
NIGISGN
NIGINSG
NIGINGS
NIGIGNS
NIGIGSN
NIGNISG
NIGNIGS
NIGNSIG
NIGNSGI
NIGNGSI
NIGNGIS
NIGGINS
NIGGISN
NIGGNIS
NIGGNSI
NIGGSNI
NIGGSIN
NISGING
NISGIGN
NISGNIG
NISGNGI
NISGGNI
NISGGIN
NISIGNG
NISIGGN
NISINGG
NISNIGG
NISNGIG
NISNGGI
NIISGNG
NIISGGN
NIISNGG
NIIGSNG
NIIGSGN
NIIGNSG
NIIGNGS
NIIGGNS
NIIGGSN
NIINGSG
NIINGGS
NIINSGG
NINSIGG
NINSGIG
NINSGGI
NINISGG
NINIGSG
NINIGGS
NINGISG
NINGIGS
NINGSIG
NINGSGI
NINGGSI
NINGGIS
NGISING
NGISIGN
NGISNIG
NGISNGI
NGISGNI
NGISGIN
NGIISNG
NGIISGN
NGIINSG
NGIINGS
NGIIGNS
NGIIGSN
NGINISG
NGINIGS
NGINSIG
NGINSGI
NGINGSI
NGINGIS
NGIGINS
NGIGISN
NGIGNIS
NGIGNSI
NGIGSNI
NGIGSIN
NGSIING
NGSIIGN
NGSINIG
NGSINGI
NGSIGNI
NGSIGIN
NGSNIIG
NGSNIGI
NGSNGII
NGSGINI
NGSGIIN
NGSGNII
NGNSIIG
NGNSIGI
NGNSGII
NGNISIG
NGNISGI
NGNIISG
NGNIIGS
NGNIGIS
NGNIGSI
NGNGIIS
NGNGISI
NGNGSII
NGGSINI
NGGSIIN
NGGSNII
NGGISNI
NGGISIN
NGGINSI
NGGINIS
NGGIINS
NGGIISN
NGGNISI
NGGNIIS
NGGNSII
NSGIING
NSGIIGN
NSGINIG
NSGINGI
NSGIGNI
NSGIGIN
NSGNIIG
NSGNIGI
NSGNGII
NSGGINI
NSGGIIN
NSGGNII
NSIGING
NSIGIGN
NSIGNIG
NSIGNGI
NSIGGNI
NSIGGIN
NSIIGNG
NSIIGGN
NSIINGG
NSINIGG
NSINGIG
NSINGGI
NSNIIGG
NSNIGIG
NSNIGGI
NSNGIIG
NSNGIGI
NSNGGII
NNGSIIG
NNGSIGI
NNGSGII
NNGISIG
NNGISGI
NNGIISG
NNGIIGS
NNGIGIS
NNGIGSI
NNGGIIS
NNGGISI
NNGGSII
NNSGIIG
NNSGIGI
NNSGGII
NNSIGIG
NNSIGGI
NNSIIGG
NNISGIG
NNISGGI
NNISIGG
NNIGSIG
NNIGSGI
NNIGISG
NNIGIGS
NNIGGIS
NNIGGSI
NNIIGSG
NNIIGGS
NNIISGG// Node Js program
// Distinct permutations of the string
class MyBacktracking {
//Swapping two string elements by index
swap(text, size, a, b) {
//Check valid location of swap element
if ((a >= 0 && a < size) && (b >= 0 && b < size)) {
//Get first character
var first = text[a];
//Get second character
var second = text[b];
//Put character
text = text.substring(0, b) + first + text.substring(b + 1);
text = text.substring(0, a) + second + text.substring(a + 1);
}
return text;
}
//Check next same element are exist or not
sequece(str, start, last) {
var status = false;
for (var i = start; i < last &&
status == false; ++i) {
if (str[i] == str[last]) {
status = true;
}
}
return status;
}
//print all permutations of a string without duplicates
permutations(str, n, size) {
if (n >= size) {
return;
}
if (n == size - 1) {
process.stdout.write(str + "\n");
return;
}
for (var i = n; i < size; ++i) {
if (this.sequece(str, n, i) == false) {
//perform permutation operation
str = this.swap(str, size, i, n);
this.permutations(str, n + 1, size);
str = this.swap(str, size, i, n);
}
}
}
}
function main(args) {
var obj = new MyBacktracking();
var text = "ABABAB";
var size = text.length;
process.stdout.write("Permutations of [" + text + "] is \n");
obj.permutations(text, 0, size);
text = "SIGNING";
size = text.length;
process.stdout.write("Permutations of [" + text + "] is \n");
obj.permutations(text, 0, size);
}
main();
Output
Permutations of [ABABAB] is
ABABAB
ABABBA
ABAABB
ABBAAB
ABBABA
ABBBAA
AABBAB
AABBBA
AABABB
AAABBB
BAABAB
BAABBA
BAAABB
BABAAB
BABABA
BABBAA
BBAAAB
BBAABA
BBABAA
BBBAAA
Permutations of [SIGNING] is
SIGNING
SIGNIGN
SIGNNIG
SIGNNGI
SIGNGNI
SIGNGIN
SIGINNG
SIGINGN
SIGIGNN
SIGGINN
SIGGNIN
SIGGNNI
SINGING
SINGIGN
SINGNIG
SINGNGI
SINGGNI
SINGGIN
SINIGNG
SINIGGN
SININGG
SINNIGG
SINNGIG
SINNGGI
SIINGNG
SIINGGN
SIINNGG
SIIGNNG
SIIGNGN
SIIGGNN
SGINING
SGINIGN
SGINNIG
SGINNGI
SGINGNI
SGINGIN
SGIINNG
SGIINGN
SGIIGNN
SGIGINN
SGIGNIN
SGIGNNI
SGNIING
SGNIIGN
SGNINIG
SGNINGI
SGNIGNI
SGNIGIN
SGNNIIG
SGNNIGI
SGNNGII
SGNGINI
SGNGIIN
SGNGNII
SGGNINI
SGGNIIN
SGGNNII
SGGINNI
SGGININ
SGGIINN
SNGIING
SNGIIGN
SNGINIG
SNGINGI
SNGIGNI
SNGIGIN
SNGNIIG
SNGNIGI
SNGNGII
SNGGINI
SNGGIIN
SNGGNII
SNIGING
SNIGIGN
SNIGNIG
SNIGNGI
SNIGGNI
SNIGGIN
SNIIGNG
SNIIGGN
SNIINGG
SNINIGG
SNINGIG
SNINGGI
SNNIIGG
SNNIGIG
SNNIGGI
SNNGIIG
SNNGIGI
SNNGGII
ISGNING
ISGNIGN
ISGNNIG
ISGNNGI
ISGNGNI
ISGNGIN
ISGINNG
ISGINGN
ISGIGNN
ISGGINN
ISGGNIN
ISGGNNI
ISNGING
ISNGIGN
ISNGNIG
ISNGNGI
ISNGGNI
ISNGGIN
ISNIGNG
ISNIGGN
ISNINGG
ISNNIGG
ISNNGIG
ISNNGGI
ISINGNG
ISINGGN
ISINNGG
ISIGNNG
ISIGNGN
ISIGGNN
IGSNING
IGSNIGN
IGSNNIG
IGSNNGI
IGSNGNI
IGSNGIN
IGSINNG
IGSINGN
IGSIGNN
IGSGINN
IGSGNIN
IGSGNNI
IGNSING
IGNSIGN
IGNSNIG
IGNSNGI
IGNSGNI
IGNSGIN
IGNISNG
IGNISGN
IGNINSG
IGNINGS
IGNIGNS
IGNIGSN
IGNNISG
IGNNIGS
IGNNSIG
IGNNSGI
IGNNGSI
IGNNGIS
IGNGINS
IGNGISN
IGNGNIS
IGNGNSI
IGNGSNI
IGNGSIN
IGINSNG
IGINSGN
IGINNSG
IGINNGS
IGINGNS
IGINGSN
IGISNNG
IGISNGN
IGISGNN
IGIGSNN
IGIGNSN
IGIGNNS
IGGNINS
IGGNISN
IGGNNIS
IGGNNSI
IGGNSNI
IGGNSIN
IGGINNS
IGGINSN
IGGISNN
IGGSINN
IGGSNIN
IGGSNNI
INGSING
INGSIGN
INGSNIG
INGSNGI
INGSGNI
INGSGIN
INGISNG
INGISGN
INGINSG
INGINGS
INGIGNS
INGIGSN
INGNISG
INGNIGS
INGNSIG
INGNSGI
INGNGSI
INGNGIS
INGGINS
INGGISN
INGGNIS
INGGNSI
INGGSNI
INGGSIN
INSGING
INSGIGN
INSGNIG
INSGNGI
INSGGNI
INSGGIN
INSIGNG
INSIGGN
INSINGG
INSNIGG
INSNGIG
INSNGGI
INISGNG
INISGGN
INISNGG
INIGSNG
INIGSGN
INIGNSG
INIGNGS
INIGGNS
INIGGSN
ININGSG
ININGGS
ININSGG
INNSIGG
INNSGIG
INNSGGI
INNISGG
INNIGSG
INNIGGS
INNGISG
INNGIGS
INNGSIG
INNGSGI
INNGGSI
INNGGIS
IIGNSNG
IIGNSGN
IIGNNSG
IIGNNGS
IIGNGNS
IIGNGSN
IIGSNNG
IIGSNGN
IIGSGNN
IIGGSNN
IIGGNSN
IIGGNNS
IINGSNG
IINGSGN
IINGNSG
IINGNGS
IINGGNS
IINGGSN
IINSGNG
IINSGGN
IINSNGG
IINNSGG
IINNGSG
IINNGGS
IISNGNG
IISNGGN
IISNNGG
IISGNNG
IISGNGN
IISGGNN
GISNING
GISNIGN
GISNNIG
GISNNGI
GISNGNI
GISNGIN
GISINNG
GISINGN
GISIGNN
GISGINN
GISGNIN
GISGNNI
GINSING
GINSIGN
GINSNIG
GINSNGI
GINSGNI
GINSGIN
GINISNG
GINISGN
GININSG
GININGS
GINIGNS
GINIGSN
GINNISG
GINNIGS
GINNSIG
GINNSGI
GINNGSI
GINNGIS
GINGINS
GINGISN
GINGNIS
GINGNSI
GINGSNI
GINGSIN
GIINSNG
GIINSGN
GIINNSG
GIINNGS
GIINGNS
GIINGSN
GIISNNG
GIISNGN
GIISGNN
GIIGSNN
GIIGNSN
GIIGNNS
GIGNINS
GIGNISN
GIGNNIS
GIGNNSI
GIGNSNI
GIGNSIN
GIGINNS
GIGINSN
GIGISNN
GIGSINN
GIGSNIN
GIGSNNI
GSINING
GSINIGN
GSINNIG
GSINNGI
GSINGNI
GSINGIN
GSIINNG
GSIINGN
GSIIGNN
GSIGINN
GSIGNIN
GSIGNNI
GSNIING
GSNIIGN
GSNINIG
GSNINGI
GSNIGNI
GSNIGIN
GSNNIIG
GSNNIGI
GSNNGII
GSNGINI
GSNGIIN
GSNGNII
GSGNINI
GSGNIIN
GSGNNII
GSGINNI
GSGININ
GSGIINN
GNSIING
GNSIIGN
GNSINIG
GNSINGI
GNSIGNI
GNSIGIN
GNSNIIG
GNSNIGI
GNSNGII
GNSGINI
GNSGIIN
GNSGNII
GNISING
GNISIGN
GNISNIG
GNISNGI
GNISGNI
GNISGIN
GNIISNG
GNIISGN
GNIINSG
GNIINGS
GNIIGNS
GNIIGSN
GNINISG
GNINIGS
GNINSIG
GNINSGI
GNINGSI
GNINGIS
GNIGINS
GNIGISN
GNIGNIS
GNIGNSI
GNIGSNI
GNIGSIN
GNNIISG
GNNIIGS
GNNISIG
GNNISGI
GNNIGSI
GNNIGIS
GNNSIIG
GNNSIGI
GNNSGII
GNNGISI
GNNGIIS
GNNGSII
GNGIINS
GNGIISN
GNGINIS
GNGINSI
GNGISNI
GNGISIN
GNGNIIS
GNGNISI
GNGNSII
GNGSINI
GNGSIIN
GNGSNII
GGSNINI
GGSNIIN
GGSNNII
GGSINNI
GGSININ
GGSIINN
GGNSINI
GGNSIIN
GGNSNII
GGNISNI
GGNISIN
GGNINSI
GGNINIS
GGNIINS
GGNIISN
GGNNISI
GGNNIIS
GGNNSII
GGINSNI
GGINSIN
GGINNSI
GGINNIS
GGININS
GGINISN
GGISNNI
GGISNIN
GGISINN
GGIISNN
GGIINSN
GGIINNS
NIGSING
NIGSIGN
NIGSNIG
NIGSNGI
NIGSGNI
NIGSGIN
NIGISNG
NIGISGN
NIGINSG
NIGINGS
NIGIGNS
NIGIGSN
NIGNISG
NIGNIGS
NIGNSIG
NIGNSGI
NIGNGSI
NIGNGIS
NIGGINS
NIGGISN
NIGGNIS
NIGGNSI
NIGGSNI
NIGGSIN
NISGING
NISGIGN
NISGNIG
NISGNGI
NISGGNI
NISGGIN
NISIGNG
NISIGGN
NISINGG
NISNIGG
NISNGIG
NISNGGI
NIISGNG
NIISGGN
NIISNGG
NIIGSNG
NIIGSGN
NIIGNSG
NIIGNGS
NIIGGNS
NIIGGSN
NIINGSG
NIINGGS
NIINSGG
NINSIGG
NINSGIG
NINSGGI
NINISGG
NINIGSG
NINIGGS
NINGISG
NINGIGS
NINGSIG
NINGSGI
NINGGSI
NINGGIS
NGISING
NGISIGN
NGISNIG
NGISNGI
NGISGNI
NGISGIN
NGIISNG
NGIISGN
NGIINSG
NGIINGS
NGIIGNS
NGIIGSN
NGINISG
NGINIGS
NGINSIG
NGINSGI
NGINGSI
NGINGIS
NGIGINS
NGIGISN
NGIGNIS
NGIGNSI
NGIGSNI
NGIGSIN
NGSIING
NGSIIGN
NGSINIG
NGSINGI
NGSIGNI
NGSIGIN
NGSNIIG
NGSNIGI
NGSNGII
NGSGINI
NGSGIIN
NGSGNII
NGNSIIG
NGNSIGI
NGNSGII
NGNISIG
NGNISGI
NGNIISG
NGNIIGS
NGNIGIS
NGNIGSI
NGNGIIS
NGNGISI
NGNGSII
NGGSINI
NGGSIIN
NGGSNII
NGGISNI
NGGISIN
NGGINSI
NGGINIS
NGGIINS
NGGIISN
NGGNISI
NGGNIIS
NGGNSII
NSGIING
NSGIIGN
NSGINIG
NSGINGI
NSGIGNI
NSGIGIN
NSGNIIG
NSGNIGI
NSGNGII
NSGGINI
NSGGIIN
NSGGNII
NSIGING
NSIGIGN
NSIGNIG
NSIGNGI
NSIGGNI
NSIGGIN
NSIIGNG
NSIIGGN
NSIINGG
NSINIGG
NSINGIG
NSINGGI
NSNIIGG
NSNIGIG
NSNIGGI
NSNGIIG
NSNGIGI
NSNGGII
NNGSIIG
NNGSIGI
NNGSGII
NNGISIG
NNGISGI
NNGIISG
NNGIIGS
NNGIGIS
NNGIGSI
NNGGIIS
NNGGISI
NNGGSII
NNSGIIG
NNSGIGI
NNSGGII
NNSIGIG
NNSIGGI
NNSIIGG
NNISGIG
NNISGGI
NNISIGG
NNIGSIG
NNIGSGI
NNIGISG
NNIGIGS
NNIGGIS
NNIGGSI
NNIIGSG
NNIIGGS
NNIISGG# Python 3 program
# Distinct permutations of the string
class MyBacktracking :
# Swapping two string elements by index
def swap(self, text, size, a, b) :
# Check valid location of swap element
if ((a >= 0 and a < size) and(b >= 0 and b < size)) :
data = list(text)
data[a],data[b] = data[b],data[a]
return ''.join(data)
return text
# Check next same element are exist or not
def sequece(self, str, start, last) :
status = False
i = start
while (i < last and status == False) :
if (str[i] == str[last]) :
status = True
i += 1
return status
# print all permutations of a string without duplicates
def permutations(self, str, n, size) :
if (n >= size) :
return
if (n == size - 1) :
print(str ,"\n", end = "")
return
i = n
while (i < size) :
if (self.sequece(str, n, i) == False) :
# perform permutation operation
str = self.swap(str, size, i, n)
self.permutations(str, n + 1, size)
str = self.swap(str, size, i, n)
i += 1
def main() :
obj = MyBacktracking()
text = "ABABAB"
size = len(text)
print("Permutations of [", text ,"] is \n", end = "")
obj.permutations(text, 0, size)
text = "SIGNING"
size = len(text)
print("Permutations of [", text ,"] is \n", end = "")
obj.permutations(text, 0, size)
if __name__ == "__main__":
main()
Output
Permutations of [ ABABAB ] is
ABABAB
ABABBA
ABAABB
ABBAAB
ABBABA
ABBBAA
AABBAB
AABBBA
AABABB
AAABBB
BAABAB
BAABBA
BAAABB
BABAAB
BABABA
BABBAA
BBAAAB
BBAABA
BBABAA
BBBAAA
Permutations of [ SIGNING ] is
SIGNING
SIGNIGN
SIGNNIG
SIGNNGI
SIGNGNI
SIGNGIN
SIGINNG
SIGINGN
SIGIGNN
SIGGINN
SIGGNIN
SIGGNNI
SINGING
SINGIGN
SINGNIG
SINGNGI
SINGGNI
SINGGIN
SINIGNG
SINIGGN
SININGG
SINNIGG
SINNGIG
SINNGGI
SIINGNG
SIINGGN
SIINNGG
SIIGNNG
SIIGNGN
SIIGGNN
SGINING
SGINIGN
SGINNIG
SGINNGI
SGINGNI
SGINGIN
SGIINNG
SGIINGN
SGIIGNN
SGIGINN
SGIGNIN
SGIGNNI
SGNIING
SGNIIGN
SGNINIG
SGNINGI
SGNIGNI
SGNIGIN
SGNNIIG
SGNNIGI
SGNNGII
SGNGINI
SGNGIIN
SGNGNII
SGGNINI
SGGNIIN
SGGNNII
SGGINNI
SGGININ
SGGIINN
SNGIING
SNGIIGN
SNGINIG
SNGINGI
SNGIGNI
SNGIGIN
SNGNIIG
SNGNIGI
SNGNGII
SNGGINI
SNGGIIN
SNGGNII
SNIGING
SNIGIGN
SNIGNIG
SNIGNGI
SNIGGNI
SNIGGIN
SNIIGNG
SNIIGGN
SNIINGG
SNINIGG
SNINGIG
SNINGGI
SNNIIGG
SNNIGIG
SNNIGGI
SNNGIIG
SNNGIGI
SNNGGII
ISGNING
ISGNIGN
ISGNNIG
ISGNNGI
ISGNGNI
ISGNGIN
ISGINNG
ISGINGN
ISGIGNN
ISGGINN
ISGGNIN
ISGGNNI
ISNGING
ISNGIGN
ISNGNIG
ISNGNGI
ISNGGNI
ISNGGIN
ISNIGNG
ISNIGGN
ISNINGG
ISNNIGG
ISNNGIG
ISNNGGI
ISINGNG
ISINGGN
ISINNGG
ISIGNNG
ISIGNGN
ISIGGNN
IGSNING
IGSNIGN
IGSNNIG
IGSNNGI
IGSNGNI
IGSNGIN
IGSINNG
IGSINGN
IGSIGNN
IGSGINN
IGSGNIN
IGSGNNI
IGNSING
IGNSIGN
IGNSNIG
IGNSNGI
IGNSGNI
IGNSGIN
IGNISNG
IGNISGN
IGNINSG
IGNINGS
IGNIGNS
IGNIGSN
IGNNISG
IGNNIGS
IGNNSIG
IGNNSGI
IGNNGSI
IGNNGIS
IGNGINS
IGNGISN
IGNGNIS
IGNGNSI
IGNGSNI
IGNGSIN
IGINSNG
IGINSGN
IGINNSG
IGINNGS
IGINGNS
IGINGSN
IGISNNG
IGISNGN
IGISGNN
IGIGSNN
IGIGNSN
IGIGNNS
IGGNINS
IGGNISN
IGGNNIS
IGGNNSI
IGGNSNI
IGGNSIN
IGGINNS
IGGINSN
IGGISNN
IGGSINN
IGGSNIN
IGGSNNI
INGSING
INGSIGN
INGSNIG
INGSNGI
INGSGNI
INGSGIN
INGISNG
INGISGN
INGINSG
INGINGS
INGIGNS
INGIGSN
INGNISG
INGNIGS
INGNSIG
INGNSGI
INGNGSI
INGNGIS
INGGINS
INGGISN
INGGNIS
INGGNSI
INGGSNI
INGGSIN
INSGING
INSGIGN
INSGNIG
INSGNGI
INSGGNI
INSGGIN
INSIGNG
INSIGGN
INSINGG
INSNIGG
INSNGIG
INSNGGI
INISGNG
INISGGN
INISNGG
INIGSNG
INIGSGN
INIGNSG
INIGNGS
INIGGNS
INIGGSN
ININGSG
ININGGS
ININSGG
INNSIGG
INNSGIG
INNSGGI
INNISGG
INNIGSG
INNIGGS
INNGISG
INNGIGS
INNGSIG
INNGSGI
INNGGSI
INNGGIS
IIGNSNG
IIGNSGN
IIGNNSG
IIGNNGS
IIGNGNS
IIGNGSN
IIGSNNG
IIGSNGN
IIGSGNN
IIGGSNN
IIGGNSN
IIGGNNS
IINGSNG
IINGSGN
IINGNSG
IINGNGS
IINGGNS
IINGGSN
IINSGNG
IINSGGN
IINSNGG
IINNSGG
IINNGSG
IINNGGS
IISNGNG
IISNGGN
IISNNGG
IISGNNG
IISGNGN
IISGGNN
GISNING
GISNIGN
GISNNIG
GISNNGI
GISNGNI
GISNGIN
GISINNG
GISINGN
GISIGNN
GISGINN
GISGNIN
GISGNNI
GINSING
GINSIGN
GINSNIG
GINSNGI
GINSGNI
GINSGIN
GINISNG
GINISGN
GININSG
GININGS
GINIGNS
GINIGSN
GINNISG
GINNIGS
GINNSIG
GINNSGI
GINNGSI
GINNGIS
GINGINS
GINGISN
GINGNIS
GINGNSI
GINGSNI
GINGSIN
GIINSNG
GIINSGN
GIINNSG
GIINNGS
GIINGNS
GIINGSN
GIISNNG
GIISNGN
GIISGNN
GIIGSNN
GIIGNSN
GIIGNNS
GIGNINS
GIGNISN
GIGNNIS
GIGNNSI
GIGNSNI
GIGNSIN
GIGINNS
GIGINSN
GIGISNN
GIGSINN
GIGSNIN
GIGSNNI
GSINING
GSINIGN
GSINNIG
GSINNGI
GSINGNI
GSINGIN
GSIINNG
GSIINGN
GSIIGNN
GSIGINN
GSIGNIN
GSIGNNI
GSNIING
GSNIIGN
GSNINIG
GSNINGI
GSNIGNI
GSNIGIN
GSNNIIG
GSNNIGI
GSNNGII
GSNGINI
GSNGIIN
GSNGNII
GSGNINI
GSGNIIN
GSGNNII
GSGINNI
GSGININ
GSGIINN
GNSIING
GNSIIGN
GNSINIG
GNSINGI
GNSIGNI
GNSIGIN
GNSNIIG
GNSNIGI
GNSNGII
GNSGINI
GNSGIIN
GNSGNII
GNISING
GNISIGN
GNISNIG
GNISNGI
GNISGNI
GNISGIN
GNIISNG
GNIISGN
GNIINSG
GNIINGS
GNIIGNS
GNIIGSN
GNINISG
GNINIGS
GNINSIG
GNINSGI
GNINGSI
GNINGIS
GNIGINS
GNIGISN
GNIGNIS
GNIGNSI
GNIGSNI
GNIGSIN
GNNIISG
GNNIIGS
GNNISIG
GNNISGI
GNNIGSI
GNNIGIS
GNNSIIG
GNNSIGI
GNNSGII
GNNGISI
GNNGIIS
GNNGSII
GNGIINS
GNGIISN
GNGINIS
GNGINSI
GNGISNI
GNGISIN
GNGNIIS
GNGNISI
GNGNSII
GNGSINI
GNGSIIN
GNGSNII
GGSNINI
GGSNIIN
GGSNNII
GGSINNI
GGSININ
GGSIINN
GGNSINI
GGNSIIN
GGNSNII
GGNISNI
GGNISIN
GGNINSI
GGNINIS
GGNIINS
GGNIISN
GGNNISI
GGNNIIS
GGNNSII
GGINSNI
GGINSIN
GGINNSI
GGINNIS
GGININS
GGINISN
GGISNNI
GGISNIN
GGISINN
GGIISNN
GGIINSN
GGIINNS
NIGSING
NIGSIGN
NIGSNIG
NIGSNGI
NIGSGNI
NIGSGIN
NIGISNG
NIGISGN
NIGINSG
NIGINGS
NIGIGNS
NIGIGSN
NIGNISG
NIGNIGS
NIGNSIG
NIGNSGI
NIGNGSI
NIGNGIS
NIGGINS
NIGGISN
NIGGNIS
NIGGNSI
NIGGSNI
NIGGSIN
NISGING
NISGIGN
NISGNIG
NISGNGI
NISGGNI
NISGGIN
NISIGNG
NISIGGN
NISINGG
NISNIGG
NISNGIG
NISNGGI
NIISGNG
NIISGGN
NIISNGG
NIIGSNG
NIIGSGN
NIIGNSG
NIIGNGS
NIIGGNS
NIIGGSN
NIINGSG
NIINGGS
NIINSGG
NINSIGG
NINSGIG
NINSGGI
NINISGG
NINIGSG
NINIGGS
NINGISG
NINGIGS
NINGSIG
NINGSGI
NINGGSI
NINGGIS
NGISING
NGISIGN
NGISNIG
NGISNGI
NGISGNI
NGISGIN
NGIISNG
NGIISGN
NGIINSG
NGIINGS
NGIIGNS
NGIIGSN
NGINISG
NGINIGS
NGINSIG
NGINSGI
NGINGSI
NGINGIS
NGIGINS
NGIGISN
NGIGNIS
NGIGNSI
NGIGSNI
NGIGSIN
NGSIING
NGSIIGN
NGSINIG
NGSINGI
NGSIGNI
NGSIGIN
NGSNIIG
NGSNIGI
NGSNGII
NGSGINI
NGSGIIN
NGSGNII
NGNSIIG
NGNSIGI
NGNSGII
NGNISIG
NGNISGI
NGNIISG
NGNIIGS
NGNIGIS
NGNIGSI
NGNGIIS
NGNGISI
NGNGSII
NGGSINI
NGGSIIN
NGGSNII
NGGISNI
NGGISIN
NGGINSI
NGGINIS
NGGIINS
NGGIISN
NGGNISI
NGGNIIS
NGGNSII
NSGIING
NSGIIGN
NSGINIG
NSGINGI
NSGIGNI
NSGIGIN
NSGNIIG
NSGNIGI
NSGNGII
NSGGINI
NSGGIIN
NSGGNII
NSIGING
NSIGIGN
NSIGNIG
NSIGNGI
NSIGGNI
NSIGGIN
NSIIGNG
NSIIGGN
NSIINGG
NSINIGG
NSINGIG
NSINGGI
NSNIIGG
NSNIGIG
NSNIGGI
NSNGIIG
NSNGIGI
NSNGGII
NNGSIIG
NNGSIGI
NNGSGII
NNGISIG
NNGISGI
NNGIISG
NNGIIGS
NNGIGIS
NNGIGSI
NNGGIIS
NNGGISI
NNGGSII
NNSGIIG
NNSGIGI
NNSGGII
NNSIGIG
NNSIGGI
NNSIIGG
NNISGIG
NNISGGI
NNISIGG
NNIGSIG
NNIGSGI
NNIGISG
NNIGIGS
NNIGGIS
NNIGGSI
NNIIGSG
NNIIGGS
NNIISGG# Ruby program
# Distinct permutations of the string
class MyBacktracking
# Swapping two string elements by index
def swap(text, size, a, b)
# Check valid location of swap element
if ((a >= 0 && a < size) && (b >= 0 && b < size))
# Get first character
first = text[a]
text[a]=text[b]
text[b]=first
end
return text
end
# Check next same element are exist or not
def sequece(str, start, last)
status = false
i = start
while (i < last &&
status == false)
if (str[i] == str[last])
status = true
end
i += 1
end
return status
end
# print all permutations of a string without duplicates
def permutations(str, n, size)
if (n >= size)
return
end
if (n == size - 1)
print(str ,"\n")
return
end
i = n
while (i < size)
if (self.sequece(str, n, i) == false)
# perform permutation operation
str = self.swap(str, size, i, n)
self.permutations(str, n + 1, size)
str = self.swap(str, size, i, n)
end
i += 1
end
end
end
def main()
obj = MyBacktracking.new()
text = "ABABAB"
size = text.length()
print("Permutations of [", text ,"] is \n")
obj.permutations(text, 0, size)
text = "SIGNING"
size = text.length()
print("Permutations of [", text ,"] is \n")
obj.permutations(text, 0, size)
end
main()
Output
Permutations of [ABABAB] is
ABABAB
ABABBA
ABAABB
ABBAAB
ABBABA
ABBBAA
AABBAB
AABBBA
AABABB
AAABBB
BAABAB
BAABBA
BAAABB
BABAAB
BABABA
BABBAA
BBAAAB
BBAABA
BBABAA
BBBAAA
Permutations of [SIGNING] is
SIGNING
SIGNIGN
SIGNNIG
SIGNNGI
SIGNGNI
SIGNGIN
SIGINNG
SIGINGN
SIGIGNN
SIGGINN
SIGGNIN
SIGGNNI
SINGING
SINGIGN
SINGNIG
SINGNGI
SINGGNI
SINGGIN
SINIGNG
SINIGGN
SININGG
SINNIGG
SINNGIG
SINNGGI
SIINGNG
SIINGGN
SIINNGG
SIIGNNG
SIIGNGN
SIIGGNN
SGINING
SGINIGN
SGINNIG
SGINNGI
SGINGNI
SGINGIN
SGIINNG
SGIINGN
SGIIGNN
SGIGINN
SGIGNIN
SGIGNNI
SGNIING
SGNIIGN
SGNINIG
SGNINGI
SGNIGNI
SGNIGIN
SGNNIIG
SGNNIGI
SGNNGII
SGNGINI
SGNGIIN
SGNGNII
SGGNINI
SGGNIIN
SGGNNII
SGGINNI
SGGININ
SGGIINN
SNGIING
SNGIIGN
SNGINIG
SNGINGI
SNGIGNI
SNGIGIN
SNGNIIG
SNGNIGI
SNGNGII
SNGGINI
SNGGIIN
SNGGNII
SNIGING
SNIGIGN
SNIGNIG
SNIGNGI
SNIGGNI
SNIGGIN
SNIIGNG
SNIIGGN
SNIINGG
SNINIGG
SNINGIG
SNINGGI
SNNIIGG
SNNIGIG
SNNIGGI
SNNGIIG
SNNGIGI
SNNGGII
ISGNING
ISGNIGN
ISGNNIG
ISGNNGI
ISGNGNI
ISGNGIN
ISGINNG
ISGINGN
ISGIGNN
ISGGINN
ISGGNIN
ISGGNNI
ISNGING
ISNGIGN
ISNGNIG
ISNGNGI
ISNGGNI
ISNGGIN
ISNIGNG
ISNIGGN
ISNINGG
ISNNIGG
ISNNGIG
ISNNGGI
ISINGNG
ISINGGN
ISINNGG
ISIGNNG
ISIGNGN
ISIGGNN
IGSNING
IGSNIGN
IGSNNIG
IGSNNGI
IGSNGNI
IGSNGIN
IGSINNG
IGSINGN
IGSIGNN
IGSGINN
IGSGNIN
IGSGNNI
IGNSING
IGNSIGN
IGNSNIG
IGNSNGI
IGNSGNI
IGNSGIN
IGNISNG
IGNISGN
IGNINSG
IGNINGS
IGNIGNS
IGNIGSN
IGNNISG
IGNNIGS
IGNNSIG
IGNNSGI
IGNNGSI
IGNNGIS
IGNGINS
IGNGISN
IGNGNIS
IGNGNSI
IGNGSNI
IGNGSIN
IGINSNG
IGINSGN
IGINNSG
IGINNGS
IGINGNS
IGINGSN
IGISNNG
IGISNGN
IGISGNN
IGIGSNN
IGIGNSN
IGIGNNS
IGGNINS
IGGNISN
IGGNNIS
IGGNNSI
IGGNSNI
IGGNSIN
IGGINNS
IGGINSN
IGGISNN
IGGSINN
IGGSNIN
IGGSNNI
INGSING
INGSIGN
INGSNIG
INGSNGI
INGSGNI
INGSGIN
INGISNG
INGISGN
INGINSG
INGINGS
INGIGNS
INGIGSN
INGNISG
INGNIGS
INGNSIG
INGNSGI
INGNGSI
INGNGIS
INGGINS
INGGISN
INGGNIS
INGGNSI
INGGSNI
INGGSIN
INSGING
INSGIGN
INSGNIG
INSGNGI
INSGGNI
INSGGIN
INSIGNG
INSIGGN
INSINGG
INSNIGG
INSNGIG
INSNGGI
INISGNG
INISGGN
INISNGG
INIGSNG
INIGSGN
INIGNSG
INIGNGS
INIGGNS
INIGGSN
ININGSG
ININGGS
ININSGG
INNSIGG
INNSGIG
INNSGGI
INNISGG
INNIGSG
INNIGGS
INNGISG
INNGIGS
INNGSIG
INNGSGI
INNGGSI
INNGGIS
IIGNSNG
IIGNSGN
IIGNNSG
IIGNNGS
IIGNGNS
IIGNGSN
IIGSNNG
IIGSNGN
IIGSGNN
IIGGSNN
IIGGNSN
IIGGNNS
IINGSNG
IINGSGN
IINGNSG
IINGNGS
IINGGNS
IINGGSN
IINSGNG
IINSGGN
IINSNGG
IINNSGG
IINNGSG
IINNGGS
IISNGNG
IISNGGN
IISNNGG
IISGNNG
IISGNGN
IISGGNN
GISNING
GISNIGN
GISNNIG
GISNNGI
GISNGNI
GISNGIN
GISINNG
GISINGN
GISIGNN
GISGINN
GISGNIN
GISGNNI
GINSING
GINSIGN
GINSNIG
GINSNGI
GINSGNI
GINSGIN
GINISNG
GINISGN
GININSG
GININGS
GINIGNS
GINIGSN
GINNISG
GINNIGS
GINNSIG
GINNSGI
GINNGSI
GINNGIS
GINGINS
GINGISN
GINGNIS
GINGNSI
GINGSNI
GINGSIN
GIINSNG
GIINSGN
GIINNSG
GIINNGS
GIINGNS
GIINGSN
GIISNNG
GIISNGN
GIISGNN
GIIGSNN
GIIGNSN
GIIGNNS
GIGNINS
GIGNISN
GIGNNIS
GIGNNSI
GIGNSNI
GIGNSIN
GIGINNS
GIGINSN
GIGISNN
GIGSINN
GIGSNIN
GIGSNNI
GSINING
GSINIGN
GSINNIG
GSINNGI
GSINGNI
GSINGIN
GSIINNG
GSIINGN
GSIIGNN
GSIGINN
GSIGNIN
GSIGNNI
GSNIING
GSNIIGN
GSNINIG
GSNINGI
GSNIGNI
GSNIGIN
GSNNIIG
GSNNIGI
GSNNGII
GSNGINI
GSNGIIN
GSNGNII
GSGNINI
GSGNIIN
GSGNNII
GSGINNI
GSGININ
GSGIINN
GNSIING
GNSIIGN
GNSINIG
GNSINGI
GNSIGNI
GNSIGIN
GNSNIIG
GNSNIGI
GNSNGII
GNSGINI
GNSGIIN
GNSGNII
GNISING
GNISIGN
GNISNIG
GNISNGI
GNISGNI
GNISGIN
GNIISNG
GNIISGN
GNIINSG
GNIINGS
GNIIGNS
GNIIGSN
GNINISG
GNINIGS
GNINSIG
GNINSGI
GNINGSI
GNINGIS
GNIGINS
GNIGISN
GNIGNIS
GNIGNSI
GNIGSNI
GNIGSIN
GNNIISG
GNNIIGS
GNNISIG
GNNISGI
GNNIGSI
GNNIGIS
GNNSIIG
GNNSIGI
GNNSGII
GNNGISI
GNNGIIS
GNNGSII
GNGIINS
GNGIISN
GNGINIS
GNGINSI
GNGISNI
GNGISIN
GNGNIIS
GNGNISI
GNGNSII
GNGSINI
GNGSIIN
GNGSNII
GGSNINI
GGSNIIN
GGSNNII
GGSINNI
GGSININ
GGSIINN
GGNSINI
GGNSIIN
GGNSNII
GGNISNI
GGNISIN
GGNINSI
GGNINIS
GGNIINS
GGNIISN
GGNNISI
GGNNIIS
GGNNSII
GGINSNI
GGINSIN
GGINNSI
GGINNIS
GGININS
GGINISN
GGISNNI
GGISNIN
GGISINN
GGIISNN
GGIINSN
GGIINNS
NIGSING
NIGSIGN
NIGSNIG
NIGSNGI
NIGSGNI
NIGSGIN
NIGISNG
NIGISGN
NIGINSG
NIGINGS
NIGIGNS
NIGIGSN
NIGNISG
NIGNIGS
NIGNSIG
NIGNSGI
NIGNGSI
NIGNGIS
NIGGINS
NIGGISN
NIGGNIS
NIGGNSI
NIGGSNI
NIGGSIN
NISGING
NISGIGN
NISGNIG
NISGNGI
NISGGNI
NISGGIN
NISIGNG
NISIGGN
NISINGG
NISNIGG
NISNGIG
NISNGGI
NIISGNG
NIISGGN
NIISNGG
NIIGSNG
NIIGSGN
NIIGNSG
NIIGNGS
NIIGGNS
NIIGGSN
NIINGSG
NIINGGS
NIINSGG
NINSIGG
NINSGIG
NINSGGI
NINISGG
NINIGSG
NINIGGS
NINGISG
NINGIGS
NINGSIG
NINGSGI
NINGGSI
NINGGIS
NGISING
NGISIGN
NGISNIG
NGISNGI
NGISGNI
NGISGIN
NGIISNG
NGIISGN
NGIINSG
NGIINGS
NGIIGNS
NGIIGSN
NGINISG
NGINIGS
NGINSIG
NGINSGI
NGINGSI
NGINGIS
NGIGINS
NGIGISN
NGIGNIS
NGIGNSI
NGIGSNI
NGIGSIN
NGSIING
NGSIIGN
NGSINIG
NGSINGI
NGSIGNI
NGSIGIN
NGSNIIG
NGSNIGI
NGSNGII
NGSGINI
NGSGIIN
NGSGNII
NGNSIIG
NGNSIGI
NGNSGII
NGNISIG
NGNISGI
NGNIISG
NGNIIGS
NGNIGIS
NGNIGSI
NGNGIIS
NGNGISI
NGNGSII
NGGSINI
NGGSIIN
NGGSNII
NGGISNI
NGGISIN
NGGINSI
NGGINIS
NGGIINS
NGGIISN
NGGNISI
NGGNIIS
NGGNSII
NSGIING
NSGIIGN
NSGINIG
NSGINGI
NSGIGNI
NSGIGIN
NSGNIIG
NSGNIGI
NSGNGII
NSGGINI
NSGGIIN
NSGGNII
NSIGING
NSIGIGN
NSIGNIG
NSIGNGI
NSIGGNI
NSIGGIN
NSIIGNG
NSIIGGN
NSIINGG
NSINIGG
NSINGIG
NSINGGI
NSNIIGG
NSNIGIG
NSNIGGI
NSNGIIG
NSNGIGI
NSNGGII
NNGSIIG
NNGSIGI
NNGSGII
NNGISIG
NNGISGI
NNGIISG
NNGIIGS
NNGIGIS
NNGIGSI
NNGGIIS
NNGGISI
NNGGSII
NNSGIIG
NNSGIGI
NNSGGII
NNSIGIG
NNSIGGI
NNSIIGG
NNISGIG
NNISGGI
NNISIGG
NNIGSIG
NNIGSGI
NNIGISG
NNIGIGS
NNIGGIS
NNIGGSI
NNIIGSG
NNIIGGS
NNIISGG
// Scala program
// Distinct permutations of the string
class MyBacktracking {
//Swapping two string elements by index
def swap(info: String, size: Int, a: Int, b: Int): String = {
//Check valid location of swap element
var text = info;
if ((a >= 0 && a < size) && (b >= 0 && b < size)) {
//Get first character
val first: Char = text(a);
//Get second character
val second: Char = text(b);
//Put character
text = text.substring(0, b) + first + text.substring(b + 1);
text = text.substring(0, a) + second + text.substring(a + 1);
}
return text;
}
//Check next same element are exist or not
def sequece(str: String, start: Int, last: Int): Boolean = {
var status: Boolean = false;
var i: Int = start;
while (i < last &&
status == false) {
if (str(i) == str(last)) {
status = true;
}
i += 1;
}
return status;
}
//print all permutations of a string without duplicates
def permutations(text: String, n: Int, size: Int): Unit = {
var str: String = text;
if (n >= size) {
return;
}
if (n == size - 1) {
print(str + "\n");
return;
}
var i: Int = n;
while (i < size) {
if (sequece(str, n, i) == false) {
//perform permutation operation
str = swap(str, size, i, n);
permutations(str, n + 1, size);
str = swap(str, size, i, n);
}
i += 1;
}
}
}
object Main {
def main(args: Array[String]): Unit = {
var obj: MyBacktracking = new MyBacktracking();
var text: String = "ABABAB";
var size: Int = text.length();
print("Permutations of [" + text + "] is \n");
obj.permutations(text, 0, size);
text = "SIGNING";
size = text.length();
print("Permutations of [" + text + "] is \n");
obj.permutations(text, 0, size);
}
}
Output
Permutations of [ABABAB] is
ABABAB
ABABBA
ABAABB
ABBAAB
ABBABA
ABBBAA
AABBAB
AABBBA
AABABB
AAABBB
BAABAB
BAABBA
BAAABB
BABAAB
BABABA
BABBAA
BBAAAB
BBAABA
BBABAA
BBBAAA
Permutations of [SIGNING] is
SIGNING
SIGNIGN
SIGNNIG
SIGNNGI
SIGNGNI
SIGNGIN
SIGINNG
SIGINGN
SIGIGNN
SIGGINN
SIGGNIN
SIGGNNI
SINGING
SINGIGN
SINGNIG
SINGNGI
SINGGNI
SINGGIN
SINIGNG
SINIGGN
SININGG
SINNIGG
SINNGIG
SINNGGI
SIINGNG
SIINGGN
SIINNGG
SIIGNNG
SIIGNGN
SIIGGNN
SGINING
SGINIGN
SGINNIG
SGINNGI
SGINGNI
SGINGIN
SGIINNG
SGIINGN
SGIIGNN
SGIGINN
SGIGNIN
SGIGNNI
SGNIING
SGNIIGN
SGNINIG
SGNINGI
SGNIGNI
SGNIGIN
SGNNIIG
SGNNIGI
SGNNGII
SGNGINI
SGNGIIN
SGNGNII
SGGNINI
SGGNIIN
SGGNNII
SGGINNI
SGGININ
SGGIINN
SNGIING
SNGIIGN
SNGINIG
SNGINGI
SNGIGNI
SNGIGIN
SNGNIIG
SNGNIGI
SNGNGII
SNGGINI
SNGGIIN
SNGGNII
SNIGING
SNIGIGN
SNIGNIG
SNIGNGI
SNIGGNI
SNIGGIN
SNIIGNG
SNIIGGN
SNIINGG
SNINIGG
SNINGIG
SNINGGI
SNNIIGG
SNNIGIG
SNNIGGI
SNNGIIG
SNNGIGI
SNNGGII
ISGNING
ISGNIGN
ISGNNIG
ISGNNGI
ISGNGNI
ISGNGIN
ISGINNG
ISGINGN
ISGIGNN
ISGGINN
ISGGNIN
ISGGNNI
ISNGING
ISNGIGN
ISNGNIG
ISNGNGI
ISNGGNI
ISNGGIN
ISNIGNG
ISNIGGN
ISNINGG
ISNNIGG
ISNNGIG
ISNNGGI
ISINGNG
ISINGGN
ISINNGG
ISIGNNG
ISIGNGN
ISIGGNN
IGSNING
IGSNIGN
IGSNNIG
IGSNNGI
IGSNGNI
IGSNGIN
IGSINNG
IGSINGN
IGSIGNN
IGSGINN
IGSGNIN
IGSGNNI
IGNSING
IGNSIGN
IGNSNIG
IGNSNGI
IGNSGNI
IGNSGIN
IGNISNG
IGNISGN
IGNINSG
IGNINGS
IGNIGNS
IGNIGSN
IGNNISG
IGNNIGS
IGNNSIG
IGNNSGI
IGNNGSI
IGNNGIS
IGNGINS
IGNGISN
IGNGNIS
IGNGNSI
IGNGSNI
IGNGSIN
IGINSNG
IGINSGN
IGINNSG
IGINNGS
IGINGNS
IGINGSN
IGISNNG
IGISNGN
IGISGNN
IGIGSNN
IGIGNSN
IGIGNNS
IGGNINS
IGGNISN
IGGNNIS
IGGNNSI
IGGNSNI
IGGNSIN
IGGINNS
IGGINSN
IGGISNN
IGGSINN
IGGSNIN
IGGSNNI
INGSING
INGSIGN
INGSNIG
INGSNGI
INGSGNI
INGSGIN
INGISNG
INGISGN
INGINSG
INGINGS
INGIGNS
INGIGSN
INGNISG
INGNIGS
INGNSIG
INGNSGI
INGNGSI
INGNGIS
INGGINS
INGGISN
INGGNIS
INGGNSI
INGGSNI
INGGSIN
INSGING
INSGIGN
INSGNIG
INSGNGI
INSGGNI
INSGGIN
INSIGNG
INSIGGN
INSINGG
INSNIGG
INSNGIG
INSNGGI
INISGNG
INISGGN
INISNGG
INIGSNG
INIGSGN
INIGNSG
INIGNGS
INIGGNS
INIGGSN
ININGSG
ININGGS
ININSGG
INNSIGG
INNSGIG
INNSGGI
INNISGG
INNIGSG
INNIGGS
INNGISG
INNGIGS
INNGSIG
INNGSGI
INNGGSI
INNGGIS
IIGNSNG
IIGNSGN
IIGNNSG
IIGNNGS
IIGNGNS
IIGNGSN
IIGSNNG
IIGSNGN
IIGSGNN
IIGGSNN
IIGGNSN
IIGGNNS
IINGSNG
IINGSGN
IINGNSG
IINGNGS
IINGGNS
IINGGSN
IINSGNG
IINSGGN
IINSNGG
IINNSGG
IINNGSG
IINNGGS
IISNGNG
IISNGGN
IISNNGG
IISGNNG
IISGNGN
IISGGNN
GISNING
GISNIGN
GISNNIG
GISNNGI
GISNGNI
GISNGIN
GISINNG
GISINGN
GISIGNN
GISGINN
GISGNIN
GISGNNI
GINSING
GINSIGN
GINSNIG
GINSNGI
GINSGNI
GINSGIN
GINISNG
GINISGN
GININSG
GININGS
GINIGNS
GINIGSN
GINNISG
GINNIGS
GINNSIG
GINNSGI
GINNGSI
GINNGIS
GINGINS
GINGISN
GINGNIS
GINGNSI
GINGSNI
GINGSIN
GIINSNG
GIINSGN
GIINNSG
GIINNGS
GIINGNS
GIINGSN
GIISNNG
GIISNGN
GIISGNN
GIIGSNN
GIIGNSN
GIIGNNS
GIGNINS
GIGNISN
GIGNNIS
GIGNNSI
GIGNSNI
GIGNSIN
GIGINNS
GIGINSN
GIGISNN
GIGSINN
GIGSNIN
GIGSNNI
GSINING
GSINIGN
GSINNIG
GSINNGI
GSINGNI
GSINGIN
GSIINNG
GSIINGN
GSIIGNN
GSIGINN
GSIGNIN
GSIGNNI
GSNIING
GSNIIGN
GSNINIG
GSNINGI
GSNIGNI
GSNIGIN
GSNNIIG
GSNNIGI
GSNNGII
GSNGINI
GSNGIIN
GSNGNII
GSGNINI
GSGNIIN
GSGNNII
GSGINNI
GSGININ
GSGIINN
GNSIING
GNSIIGN
GNSINIG
GNSINGI
GNSIGNI
GNSIGIN
GNSNIIG
GNSNIGI
GNSNGII
GNSGINI
GNSGIIN
GNSGNII
GNISING
GNISIGN
GNISNIG
GNISNGI
GNISGNI
GNISGIN
GNIISNG
GNIISGN
GNIINSG
GNIINGS
GNIIGNS
GNIIGSN
GNINISG
GNINIGS
GNINSIG
GNINSGI
GNINGSI
GNINGIS
GNIGINS
GNIGISN
GNIGNIS
GNIGNSI
GNIGSNI
GNIGSIN
GNNIISG
GNNIIGS
GNNISIG
GNNISGI
GNNIGSI
GNNIGIS
GNNSIIG
GNNSIGI
GNNSGII
GNNGISI
GNNGIIS
GNNGSII
GNGIINS
GNGIISN
GNGINIS
GNGINSI
GNGISNI
GNGISIN
GNGNIIS
GNGNISI
GNGNSII
GNGSINI
GNGSIIN
GNGSNII
GGSNINI
GGSNIIN
GGSNNII
GGSINNI
GGSININ
GGSIINN
GGNSINI
GGNSIIN
GGNSNII
GGNISNI
GGNISIN
GGNINSI
GGNINIS
GGNIINS
GGNIISN
GGNNISI
GGNNIIS
GGNNSII
GGINSNI
GGINSIN
GGINNSI
GGINNIS
GGININS
GGINISN
GGISNNI
GGISNIN
GGISINN
GGIISNN
GGIINSN
GGIINNS
NIGSING
NIGSIGN
NIGSNIG
NIGSNGI
NIGSGNI
NIGSGIN
NIGISNG
NIGISGN
NIGINSG
NIGINGS
NIGIGNS
NIGIGSN
NIGNISG
NIGNIGS
NIGNSIG
NIGNSGI
NIGNGSI
NIGNGIS
NIGGINS
NIGGISN
NIGGNIS
NIGGNSI
NIGGSNI
NIGGSIN
NISGING
NISGIGN
NISGNIG
NISGNGI
NISGGNI
NISGGIN
NISIGNG
NISIGGN
NISINGG
NISNIGG
NISNGIG
NISNGGI
NIISGNG
NIISGGN
NIISNGG
NIIGSNG
NIIGSGN
NIIGNSG
NIIGNGS
NIIGGNS
NIIGGSN
NIINGSG
NIINGGS
NIINSGG
NINSIGG
NINSGIG
NINSGGI
NINISGG
NINIGSG
NINIGGS
NINGISG
NINGIGS
NINGSIG
NINGSGI
NINGGSI
NINGGIS
NGISING
NGISIGN
NGISNIG
NGISNGI
NGISGNI
NGISGIN
NGIISNG
NGIISGN
NGIINSG
NGIINGS
NGIIGNS
NGIIGSN
NGINISG
NGINIGS
NGINSIG
NGINSGI
NGINGSI
NGINGIS
NGIGINS
NGIGISN
NGIGNIS
NGIGNSI
NGIGSNI
NGIGSIN
NGSIING
NGSIIGN
NGSINIG
NGSINGI
NGSIGNI
NGSIGIN
NGSNIIG
NGSNIGI
NGSNGII
NGSGINI
NGSGIIN
NGSGNII
NGNSIIG
NGNSIGI
NGNSGII
NGNISIG
NGNISGI
NGNIISG
NGNIIGS
NGNIGIS
NGNIGSI
NGNGIIS
NGNGISI
NGNGSII
NGGSINI
NGGSIIN
NGGSNII
NGGISNI
NGGISIN
NGGINSI
NGGINIS
NGGIINS
NGGIISN
NGGNISI
NGGNIIS
NGGNSII
NSGIING
NSGIIGN
NSGINIG
NSGINGI
NSGIGNI
NSGIGIN
NSGNIIG
NSGNIGI
NSGNGII
NSGGINI
NSGGIIN
NSGGNII
NSIGING
NSIGIGN
NSIGNIG
NSIGNGI
NSIGGNI
NSIGGIN
NSIIGNG
NSIIGGN
NSIINGG
NSINIGG
NSINGIG
NSINGGI
NSNIIGG
NSNIGIG
NSNIGGI
NSNGIIG
NSNGIGI
NSNGGII
NNGSIIG
NNGSIGI
NNGSGII
NNGISIG
NNGISGI
NNGIISG
NNGIIGS
NNGIGIS
NNGIGSI
NNGGIIS
NNGGISI
NNGGSII
NNSGIIG
NNSGIGI
NNSGGII
NNSIGIG
NNSIGGI
NNSIIGG
NNISGIG
NNISGGI
NNISIGG
NNIGSIG
NNIGSGI
NNIGISG
NNIGIGS
NNIGGIS
NNIGGSI
NNIIGSG
NNIIGGS
NNIISGG// Swift program
// Distinct permutations of the string
class MyBacktracking {
//Swapping two string elements by index
func swap(_ text: String, _ size: Int, _ a: Int, _ b: Int) -> String {
//Check valid location of swap element
if ((a >= 0 && a < size) && (b >= 0 && b < size)) {
var result = Array(text)
result.swapAt(a, b)
return String(result)
}
return text;
}
//Check next same element are exist or not
func sequece(_ text: String, _ start: Int, _ last: Int) -> Bool {
var status: Bool = false;
var i: Int = start;
let str = Array(text);
while (i < last &&
status == false) {
if (str[i] == str[last]) {
status = true;
}
i += 1;
}
return status;
}
//print all permutations of a string without duplicates
func permutations(_ text: String, _ n: Int, _ size: Int) {
var str : String = text;
if (n >= size) {
return;
}
if (n == size - 1) {
print(str ,"\n", terminator: "");
return;
}
var i: Int = n;
while (i < size) {
if (self.sequece(str, n, i) == false) {
//perform permutation operation
str = self.swap(str, size, i, n);
self.permutations(str, n + 1, size);
str = self.swap(str, size, i, n);
}
i += 1;
}
}
}
func main() {
let obj: MyBacktracking = MyBacktracking();
var text: String = "ABABAB";
var size: Int = text.count;
print("Permutations of [", text ,"] is \n", terminator: "");
obj.permutations(text, 0, size);
text = "SIGNING";
size = text.count;
print("Permutations of [", text ,"] is \n", terminator: "");
obj.permutations(text, 0, size);
}
main();
Output
Permutations of [ ABABAB ] is
ABABAB
ABABBA
ABAABB
ABBAAB
ABBABA
ABBBAA
AABBAB
AABBBA
AABABB
AAABBB
BAABAB
BAABBA
BAAABB
BABAAB
BABABA
BABBAA
BBAAAB
BBAABA
BBABAA
BBBAAA
Permutations of [ SIGNING ] is
SIGNING
SIGNIGN
SIGNNIG
SIGNNGI
SIGNGNI
SIGNGIN
SIGINNG
SIGINGN
SIGIGNN
SIGGINN
SIGGNIN
SIGGNNI
SINGING
SINGIGN
SINGNIG
SINGNGI
SINGGNI
SINGGIN
SINIGNG
SINIGGN
SININGG
SINNIGG
SINNGIG
SINNGGI
SIINGNG
SIINGGN
SIINNGG
SIIGNNG
SIIGNGN
SIIGGNN
SGINING
SGINIGN
SGINNIG
SGINNGI
SGINGNI
SGINGIN
SGIINNG
SGIINGN
SGIIGNN
SGIGINN
SGIGNIN
SGIGNNI
SGNIING
SGNIIGN
SGNINIG
SGNINGI
SGNIGNI
SGNIGIN
SGNNIIG
SGNNIGI
SGNNGII
SGNGINI
SGNGIIN
SGNGNII
SGGNINI
SGGNIIN
SGGNNII
SGGINNI
SGGININ
SGGIINN
SNGIING
SNGIIGN
SNGINIG
SNGINGI
SNGIGNI
SNGIGIN
SNGNIIG
SNGNIGI
SNGNGII
SNGGINI
SNGGIIN
SNGGNII
SNIGING
SNIGIGN
SNIGNIG
SNIGNGI
SNIGGNI
SNIGGIN
SNIIGNG
SNIIGGN
SNIINGG
SNINIGG
SNINGIG
SNINGGI
SNNIIGG
SNNIGIG
SNNIGGI
SNNGIIG
SNNGIGI
SNNGGII
ISGNING
ISGNIGN
ISGNNIG
ISGNNGI
ISGNGNI
ISGNGIN
ISGINNG
ISGINGN
ISGIGNN
ISGGINN
ISGGNIN
ISGGNNI
ISNGING
ISNGIGN
ISNGNIG
ISNGNGI
ISNGGNI
ISNGGIN
ISNIGNG
ISNIGGN
ISNINGG
ISNNIGG
ISNNGIG
ISNNGGI
ISINGNG
ISINGGN
ISINNGG
ISIGNNG
ISIGNGN
ISIGGNN
IGSNING
IGSNIGN
IGSNNIG
IGSNNGI
IGSNGNI
IGSNGIN
IGSINNG
IGSINGN
IGSIGNN
IGSGINN
IGSGNIN
IGSGNNI
IGNSING
IGNSIGN
IGNSNIG
IGNSNGI
IGNSGNI
IGNSGIN
IGNISNG
IGNISGN
IGNINSG
IGNINGS
IGNIGNS
IGNIGSN
IGNNISG
IGNNIGS
IGNNSIG
IGNNSGI
IGNNGSI
IGNNGIS
IGNGINS
IGNGISN
IGNGNIS
IGNGNSI
IGNGSNI
IGNGSIN
IGINSNG
IGINSGN
IGINNSG
IGINNGS
IGINGNS
IGINGSN
IGISNNG
IGISNGN
IGISGNN
IGIGSNN
IGIGNSN
IGIGNNS
IGGNINS
IGGNISN
IGGNNIS
IGGNNSI
IGGNSNI
IGGNSIN
IGGINNS
IGGINSN
IGGISNN
IGGSINN
IGGSNIN
IGGSNNI
INGSING
INGSIGN
INGSNIG
INGSNGI
INGSGNI
INGSGIN
INGISNG
INGISGN
INGINSG
INGINGS
INGIGNS
INGIGSN
INGNISG
INGNIGS
INGNSIG
INGNSGI
INGNGSI
INGNGIS
INGGINS
INGGISN
INGGNIS
INGGNSI
INGGSNI
INGGSIN
INSGING
INSGIGN
INSGNIG
INSGNGI
INSGGNI
INSGGIN
INSIGNG
INSIGGN
INSINGG
INSNIGG
INSNGIG
INSNGGI
INISGNG
INISGGN
INISNGG
INIGSNG
INIGSGN
INIGNSG
INIGNGS
INIGGNS
INIGGSN
ININGSG
ININGGS
ININSGG
INNSIGG
INNSGIG
INNSGGI
INNISGG
INNIGSG
INNIGGS
INNGISG
INNGIGS
INNGSIG
INNGSGI
INNGGSI
INNGGIS
IIGNSNG
IIGNSGN
IIGNNSG
IIGNNGS
IIGNGNS
IIGNGSN
IIGSNNG
IIGSNGN
IIGSGNN
IIGGSNN
IIGGNSN
IIGGNNS
IINGSNG
IINGSGN
IINGNSG
IINGNGS
IINGGNS
IINGGSN
IINSGNG
IINSGGN
IINSNGG
IINNSGG
IINNGSG
IINNGGS
IISNGNG
IISNGGN
IISNNGG
IISGNNG
IISGNGN
IISGGNN
GISNING
GISNIGN
GISNNIG
GISNNGI
GISNGNI
GISNGIN
GISINNG
GISINGN
GISIGNN
GISGINN
GISGNIN
GISGNNI
GINSING
GINSIGN
GINSNIG
GINSNGI
GINSGNI
GINSGIN
GINISNG
GINISGN
GININSG
GININGS
GINIGNS
GINIGSN
GINNISG
GINNIGS
GINNSIG
GINNSGI
GINNGSI
GINNGIS
GINGINS
GINGISN
GINGNIS
GINGNSI
GINGSNI
GINGSIN
GIINSNG
GIINSGN
GIINNSG
GIINNGS
GIINGNS
GIINGSN
GIISNNG
GIISNGN
GIISGNN
GIIGSNN
GIIGNSN
GIIGNNS
GIGNINS
GIGNISN
GIGNNIS
GIGNNSI
GIGNSNI
GIGNSIN
GIGINNS
GIGINSN
GIGISNN
GIGSINN
GIGSNIN
GIGSNNI
GSINING
GSINIGN
GSINNIG
GSINNGI
GSINGNI
GSINGIN
GSIINNG
GSIINGN
GSIIGNN
GSIGINN
GSIGNIN
GSIGNNI
GSNIING
GSNIIGN
GSNINIG
GSNINGI
GSNIGNI
GSNIGIN
GSNNIIG
GSNNIGI
GSNNGII
GSNGINI
GSNGIIN
GSNGNII
GSGNINI
GSGNIIN
GSGNNII
GSGINNI
GSGININ
GSGIINN
GNSIING
GNSIIGN
GNSINIG
GNSINGI
GNSIGNI
GNSIGIN
GNSNIIG
GNSNIGI
GNSNGII
GNSGINI
GNSGIIN
GNSGNII
GNISING
GNISIGN
GNISNIG
GNISNGI
GNISGNI
GNISGIN
GNIISNG
GNIISGN
GNIINSG
GNIINGS
GNIIGNS
GNIIGSN
GNINISG
GNINIGS
GNINSIG
GNINSGI
GNINGSI
GNINGIS
GNIGINS
GNIGISN
GNIGNIS
GNIGNSI
GNIGSNI
GNIGSIN
GNNIISG
GNNIIGS
GNNISIG
GNNISGI
GNNIGSI
GNNIGIS
GNNSIIG
GNNSIGI
GNNSGII
GNNGISI
GNNGIIS
GNNGSII
GNGIINS
GNGIISN
GNGINIS
GNGINSI
GNGISNI
GNGISIN
GNGNIIS
GNGNISI
GNGNSII
GNGSINI
GNGSIIN
GNGSNII
GGSNINI
GGSNIIN
GGSNNII
GGSINNI
GGSININ
GGSIINN
GGNSINI
GGNSIIN
GGNSNII
GGNISNI
GGNISIN
GGNINSI
GGNINIS
GGNIINS
GGNIISN
GGNNISI
GGNNIIS
GGNNSII
GGINSNI
GGINSIN
GGINNSI
GGINNIS
GGININS
GGINISN
GGISNNI
GGISNIN
GGISINN
GGIISNN
GGIINSN
GGIINNS
NIGSING
NIGSIGN
NIGSNIG
NIGSNGI
NIGSGNI
NIGSGIN
NIGISNG
NIGISGN
NIGINSG
NIGINGS
NIGIGNS
NIGIGSN
NIGNISG
NIGNIGS
NIGNSIG
NIGNSGI
NIGNGSI
NIGNGIS
NIGGINS
NIGGISN
NIGGNIS
NIGGNSI
NIGGSNI
NIGGSIN
NISGING
NISGIGN
NISGNIG
NISGNGI
NISGGNI
NISGGIN
NISIGNG
NISIGGN
NISINGG
NISNIGG
NISNGIG
NISNGGI
NIISGNG
NIISGGN
NIISNGG
NIIGSNG
NIIGSGN
NIIGNSG
NIIGNGS
NIIGGNS
NIIGGSN
NIINGSG
NIINGGS
NIINSGG
NINSIGG
NINSGIG
NINSGGI
NINISGG
NINIGSG
NINIGGS
NINGISG
NINGIGS
NINGSIG
NINGSGI
NINGGSI
NINGGIS
NGISING
NGISIGN
NGISNIG
NGISNGI
NGISGNI
NGISGIN
NGIISNG
NGIISGN
NGIINSG
NGIINGS
NGIIGNS
NGIIGSN
NGINISG
NGINIGS
NGINSIG
NGINSGI
NGINGSI
NGINGIS
NGIGINS
NGIGISN
NGIGNIS
NGIGNSI
NGIGSNI
NGIGSIN
NGSIING
NGSIIGN
NGSINIG
NGSINGI
NGSIGNI
NGSIGIN
NGSNIIG
NGSNIGI
NGSNGII
NGSGINI
NGSGIIN
NGSGNII
NGNSIIG
NGNSIGI
NGNSGII
NGNISIG
NGNISGI
NGNIISG
NGNIIGS
NGNIGIS
NGNIGSI
NGNGIIS
NGNGISI
NGNGSII
NGGSINI
NGGSIIN
NGGSNII
NGGISNI
NGGISIN
NGGINSI
NGGINIS
NGGIINS
NGGIISN
NGGNISI
NGGNIIS
NGGNSII
NSGIING
NSGIIGN
NSGINIG
NSGINGI
NSGIGNI
NSGIGIN
NSGNIIG
NSGNIGI
NSGNGII
NSGGINI
NSGGIIN
NSGGNII
NSIGING
NSIGIGN
NSIGNIG
NSIGNGI
NSIGGNI
NSIGGIN
NSIIGNG
NSIIGGN
NSIINGG
NSINIGG
NSINGIG
NSINGGI
NSNIIGG
NSNIGIG
NSNIGGI
NSNGIIG
NSNGIGI
NSNGGII
NNGSIIG
NNGSIGI
NNGSGII
NNGISIG
NNGISGI
NNGIISG
NNGIIGS
NNGIGIS
NNGIGSI
NNGGIIS
NNGGISI
NNGGSII
NNSGIIG
NNSGIGI
NNSGGII
NNSIGIG
NNSIGGI
NNSIIGG
NNISGIG
NNISGGI
NNISIGG
NNIGSIG
NNIGSGI
NNIGISG
NNIGIGS
NNIGGIS
NNIGGSI
NNIIGSG
NNIIGGS
NNIISGGExplanation
The algorithm uses a recursive approach to generate permutations. It starts by swapping characters in the string and recursively generates permutations by swapping characters back. The sequence function checks whether the next same element exists or not to avoid duplicate permutations.
The main function initializes two strings, "ABABAB" and "SIGNING." It calculates the size of each string and calls the permutations function for each string to generate the distinct permutations.
Output Explanation
For the string "ABABAB," the distinct permutations are printed as follows: [list all permutations]. Similarly, for the string "SIGNING," the distinct permutations are printed: [list all permutations]. The output demonstrates all possible distinct permutations of the given strings.
Time Complexity
The time complexity of this algorithm can be analyzed as follows: Let n be the length of the input string. For each character in the string, we perform a constant amount of work. Therefore, the overall time complexity is O(n!), where n! represents the factorial of n.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment