SHARE
SPREAD
HELP

The Tradition of Sharing

Help your friends and juniors by posting answers to the questions that you know. Also post questions that are not available.


To start with, Sr2Jr’s first step is to reduce the expenses related to education. To achieve this goal Sr2Jr organized the textbook’s question and answers. Sr2Jr is community based and need your support to fill the question and answers. The question and answers posted will be available free of cost to all.

 

#
Authors:
Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser
Chapter:
Java Primer
Exercise:
Exercises
Question:22 | ISBN:9781118771334 | Edition: 6

Question

Write a short Java program that outputs all possible strings formed by using the characters 'c', 'a', 't', 'd', 'o', and 'g' exactly once.

TextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbook

Answer

package java_problems_datastructures;

import java.util.ArrayList;

public class AllPossibleStrings {

	/*
	 * Below method takes String as parameter and returns list of all possible
	 * strings formed with that string.
	 * 
	 */

	public static ArrayList<String> permutation(String string) {

		// make an Arraylist

		ArrayList<String> res = new ArrayList<String>();

		// if length of string greater than 1
		if (string.length() > 1) {
			// we will take last index
			int lastIndex = string.length() - 1;

			// substring method takes and index and make a seperate string
			// beginning from the character we pass as argument

			String lastCharacter = string.substring(lastIndex);

			// save the remaining string in rest by using one more substring method.

			String restOfString = string.substring(0, lastIndex);
			// Perform permutation on the rest string and
			// merge with the last character
			res = merge(permutation(restOfString), lastCharacter);

		}

		// if length of string equals 1
		else if (string.length() == 1) {
			res.add(string);
		}
		return res;
	}

	// merge method takes list of substrings and last charater
	public static ArrayList<String> merge(ArrayList<String> list, String lastCharacter) {
		ArrayList<String> res = new ArrayList<>();
		// Loop through all the string in the list
		for (String string : list) {
			// For each string, insert the last character to all possible positions
			// and add them to new list
			for (int i = 0; i <= string.length(); ++i) {
				String permutedString = new StringBuffer(string).insert(i, lastCharacter).toString();
				res.add(permutedString);
			}
		}
		return res;
	}

	public static void main(String args[]) {

		// call the method and print all strings
		for (String array : permutation("catdog")) {
			System.out.println(array);
		}

	}

}


Output:  (Desclaimer: pretty long output for sure)

godtac
ogdtac
odgtac
odtgac
odtagc
odtacg
gdotac
dgotac
dogtac
dotgac
dotagc
dotacg
gdtoac
dgtoac
dtgoac
dtogac
dtoagc
dtoacg
gdtaoc
dgtaoc
dtgaoc
dtagoc
dtaogc
dtaocg
gdtaco
dgtaco
dtgaco
dtagco
dtacgo
dtacog
gotdac
ogtdac
otgdac
otdgac
otdagc
otdacg
gtodac
tgodac
togdac
todgac
todagc
todacg
gtdoac
tgdoac
tdgoac
tdogac
tdoagc
tdoacg
gtdaoc
tgdaoc
tdgaoc
tdagoc
tdaogc
tdaocg
gtdaco
tgdaco
tdgaco
tdagco
tdacgo
tdacog
gotadc
ogtadc
otgadc
otagdc
otadgc
otadcg
gtoadc
tgoadc
togadc
toagdc
toadgc
toadcg
gtaodc
tgaodc
tagodc
taogdc
taodgc
taodcg
gtadoc
tgadoc
tagdoc
tadgoc
tadogc
tadocg
gtadco
tgadco
tagdco
tadgco
tadcgo
tadcog
gotacd
ogtacd
otgacd
otagcd
otacgd
otacdg
gtoacd
tgoacd
togacd
toagcd
toacgd
toacdg
gtaocd
tgaocd
tagocd
taogcd
taocgd
taocdg
gtacod
tgacod
tagcod
tacgod
tacogd
tacodg
gtacdo
tgacdo
tagcdo
tacgdo
tacdgo
tacdog
godatc
ogdatc
odgatc
odagtc
odatgc
odatcg
gdoatc
dgoatc
dogatc
doagtc
doatgc
doatcg
gdaotc
dgaotc
dagotc
daogtc
daotgc
daotcg
gdatoc
dgatoc
dagtoc
datgoc
datogc
datocg
gdatco
dgatco
dagtco
datgco
datcgo
datcog
goadtc
ogadtc
oagdtc
oadgtc
oadtgc
oadtcg
gaodtc
agodtc
aogdtc
aodgtc
aodtgc
aodtcg
gadotc
agdotc
adgotc
adogtc
adotgc
adotcg
gadtoc
agdtoc
adgtoc
adtgoc
adtogc
adtocg
gadtco
agdtco
adgtco
adtgco
adtcgo
adtcog
goatdc
ogatdc
oagtdc
oatgdc
oatdgc
oatdcg
gaotdc
agotdc
aogtdc
aotgdc
aotdgc
aotdcg
gatodc
agtodc
atgodc
atogdc
atodgc
atodcg
gatdoc
agtdoc
atgdoc
atdgoc
atdogc
atdocg
gatdco
agtdco
atgdco
atdgco
atdcgo
atdcog
goatcd
ogatcd
oagtcd
oatgcd
oatcgd
oatcdg
gaotcd
agotcd
aogtcd
aotgcd
aotcgd
aotcdg
gatocd
agtocd
atgocd
atogcd
atocgd
atocdg
gatcod
agtcod
atgcod
atcgod
atcogd
atcodg
gatcdo
agtcdo
atgcdo
atcgdo
atcdgo
atcdog
godact
ogdact
odgact
odagct
odacgt
odactg
gdoact
dgoact
dogact
doagct
doacgt
doactg
gdaoct
dgaoct
dagoct
daogct
daocgt
daoctg
gdacot
dgacot
dagcot
dacgot
dacogt
dacotg
gdacto
dgacto
dagcto
dacgto
dactgo
dactog
goadct
ogadct
oagdct
oadgct
oadcgt
oadctg
gaodct
agodct
aogdct
aodgct
aodcgt
aodctg
gadoct
agdoct
adgoct
adogct
adocgt
adoctg
gadcot
agdcot
adgcot
adcgot
adcogt
adcotg
gadcto
agdcto
adgcto
adcgto
adctgo
adctog
goacdt
ogacdt
oagcdt
oacgdt
oacdgt
oacdtg
gaocdt
agocdt
aogcdt
aocgdt
aocdgt
aocdtg
gacodt
agcodt
acgodt
acogdt
acodgt
acodtg
gacdot
agcdot
acgdot
acdgot
acdogt
acdotg
gacdto
agcdto
acgdto
acdgto
acdtgo
acdtog
goactd
ogactd
oagctd
oacgtd
oactgd
oactdg
gaoctd
agoctd
aogctd
aocgtd
aoctgd
aoctdg
gacotd
agcotd
acgotd
acogtd
acotgd
acotdg
gactod
agctod
acgtod
actgod
actogd
actodg
gactdo
agctdo
acgtdo
actgdo
actdgo
actdog
godtca
ogdtca
odgtca
odtgca
odtcga
odtcag
gdotca
dgotca
dogtca
dotgca
dotcga
dotcag
gdtoca
dgtoca
dtgoca
dtogca
dtocga
dtocag
gdtcoa
dgtcoa
dtgcoa
dtcgoa
dtcoga
dtcoag
gdtcao
dgtcao
dtgcao
dtcgao
dtcago
dtcaog
gotdca
ogtdca
otgdca
otdgca
otdcga
otdcag
gtodca
tgodca
togdca
todgca
todcga
todcag
gtdoca
tgdoca
tdgoca
tdogca
tdocga
tdocag
gtdcoa
tgdcoa
tdgcoa
tdcgoa
tdcoga
tdcoag
gtdcao
tgdcao
tdgcao
tdcgao
tdcago
tdcaog
gotcda
ogtcda
otgcda
otcgda
otcdga
otcdag
gtocda
tgocda
togcda
tocgda
tocdga
tocdag
gtcoda
tgcoda
tcgoda
tcogda
tcodga
tcodag
gtcdoa
tgcdoa
tcgdoa
tcdgoa
tcdoga
tcdoag
gtcdao
tgcdao
tcgdao
tcdgao
tcdago
tcdaog
gotcad
ogtcad
otgcad
otcgad
otcagd
otcadg
gtocad
tgocad
togcad
tocgad
tocagd
tocadg
gtcoad
tgcoad
tcgoad
tcogad
tcoagd
tcoadg
gtcaod
tgcaod
tcgaod
tcagod
tcaogd
tcaodg
gtcado
tgcado
tcgado
tcagdo
tcadgo
tcadog
godcta
ogdcta
odgcta
odcgta
odctga
odctag
gdocta
dgocta
dogcta
docgta
doctga
doctag
gdcota
dgcota
dcgota
dcogta
dcotga
dcotag
gdctoa
dgctoa
dcgtoa
dctgoa
dctoga
dctoag
gdctao
dgctao
dcgtao
dctgao
dctago
dctaog
gocdta
ogcdta
ocgdta
ocdgta
ocdtga
ocdtag
gcodta
cgodta
cogdta
codgta
codtga
codtag
gcdota
cgdota
cdgota
cdogta
cdotga
cdotag
gcdtoa
cgdtoa
cdgtoa
cdtgoa
cdtoga
cdtoag
gcdtao
cgdtao
cdgtao
cdtgao
cdtago
cdtaog
goctda
ogctda
ocgtda
octgda
octdga
octdag
gcotda
cgotda
cogtda
cotgda
cotdga
cotdag
gctoda
cgtoda
ctgoda
ctogda
ctodga
ctodag
gctdoa
cgtdoa
ctgdoa
ctdgoa
ctdoga
ctdoag
gctdao
cgtdao
ctgdao
ctdgao
ctdago
ctdaog
goctad
ogctad
ocgtad
octgad
octagd
octadg
gcotad
cgotad
cogtad
cotgad
cotagd
cotadg
gctoad
cgtoad
ctgoad
ctogad
ctoagd
ctoadg
gctaod
cgtaod
ctgaod
ctagod
ctaogd
ctaodg
gctado
cgtado
ctgado
ctagdo
ctadgo
ctadog
godcat
ogdcat
odgcat
odcgat
odcagt
odcatg
gdocat
dgocat
dogcat
docgat
docagt
docatg
gdcoat
dgcoat
dcgoat
dcogat
dcoagt
dcoatg
gdcaot
dgcaot
dcgaot
dcagot
dcaogt
dcaotg
gdcato
dgcato
dcgato
dcagto
dcatgo
dcatog
gocdat
ogcdat
ocgdat
ocdgat
ocdagt
ocdatg
gcodat
cgodat
cogdat
codgat
codagt
codatg
gcdoat
cgdoat
cdgoat
cdogat
cdoagt
cdoatg
gcdaot
cgdaot
cdgaot
cdagot
cdaogt
cdaotg
gcdato
cgdato
cdgato
cdagto
cdatgo
cdatog
gocadt
ogcadt
ocgadt
ocagdt
ocadgt
ocadtg
gcoadt
cgoadt
cogadt
coagdt
coadgt
coadtg
gcaodt
cgaodt
cagodt
caogdt
caodgt
caodtg
gcadot
cgadot
cagdot
cadgot
cadogt
cadotg
gcadto
cgadto
cagdto
cadgto
cadtgo
cadtog
gocatd
ogcatd
ocgatd
ocagtd
ocatgd
ocatdg
gcoatd
cgoatd
cogatd
coagtd
coatgd
coatdg
gcaotd
cgaotd
cagotd
caogtd
caotgd
caotdg
gcatod
cgatod
cagtod
catgod
catogd
catodg
gcatdo
cgatdo
cagtdo
catgdo
catdgo
catdog

 

0 0

Discussions

Post the discussion to improve the above solution.