Recursive String permutation with repetitions allowed

Question

Hi I'm trying to figure out an efficient way to get all permutations of a string but also allowing repetition of characters. (for example for string "ab" the output would be "aa, bb, ba, ab")

I have my code working correctly without repetition but I'm not sure how to go about modifying it to allow repetition of characters and only seem to find ways of doing this without repetition of characters.

Here is the code that I have:

    public static ArrayList<String> permutationsUnique(String word) {
    ArrayList<String> result = new ArrayList<String>();

    if (word.length() == 0) {
        result.add(word);
        return result;
    } else {

        for (int i = 0; i < word.length(); i++) {

            String shorter = word.substring(0, i) + word.substring(i + 1);

            ArrayList<String> shorterPermutations = permutationsUnique(shorter);

            for (String s : shorterPermutations) {
                result.add(word.charAt(i) + s);
            }
        }

        return result;
    }

}

I would really appreciate if some one can guide me in the right direction.

Thank you

Are you required to implement this with recursion? Is the length of each permutation limited? For example, "bba", "aba", and "abb" are also permutations created with just the letters 'a' and 'b'. — Code-Apprentice
– Code-Apprentice, Commented Oct 9, 2014 at 3:03
Is "ttat" a valid output in that case? Are my examples valid outputs in the original case? — Code-Apprentice
– Code-Apprentice, Commented Oct 9, 2014 at 3:41
a valid output shouldn't exceed the number o characters of original string while it can ignore some characters. "ttat" would be a Ok output if the original word was "cats" — user2300867
– user2300867, Commented Oct 9, 2014 at 3:51

Atul Kumbhar · Accepted Answer · 2015-09-08 00:11:57Z

I know this question was asked long back, but I just worked on one java program to have permutation of integers with repetitions allowed. I am putting my code here, in case if someone needs it.

This program can generate permutations for specified length. i.e. For integers 1,2 and lengthOfSinglePermutation = 2, output should be 11 21 12 22

For integers 1,2 and lengthOfSinglePermutation = 3, output should be 111 211 121 221 112 212 122 222

Hope this helps.

    public class PermutationsWithRepetitions {

public static void main(String[] args) {
    int[] input = { 1, 2 };
    int lengthOfSinglePermutation = 3;

    // we need to check number of unique values in array
    Set<Integer> arrValues = new HashSet<Integer>();
    for (int i : input) {
        arrValues.add(i);
    }
    int noOfUniqueValues = arrValues.size();

    int[] indexes = new int[lengthOfSinglePermutation];
    int totalPermutations = (int) Math.pow(noOfUniqueValues, lengthOfSinglePermutation);

    for (int i = 0; i < totalPermutations; i++) {

        for (int j = 0; j < lengthOfSinglePermutation; j++) {
            System.out.print(input[indexes[j]]);
        }
        System.out.println();

        for (int j = 0; j < lengthOfSinglePermutation; j++) {
            if (indexes[j] >= noOfUniqueValues - 1) {
                indexes[j] = 0;
            }
            else {
                indexes[j]++;
                break;
            }
        }
    }
}
}

Deval Khandelwal · Accepted Answer · 2014-10-09 03:08:20Z

1

Sorry, my previous answer was somewhat unrelated. DELETED. This will definitely work :-

static void Recur(String prefix, String str)
{
 if(prefix.length()==str.length())
 { 
   System.out.println(prefix); return; 
 }

   for(int i=0; i<str.length(); i++)
   Recur(prefix+str.charAt(i),str);
 }
 public static void main (String[] args)
 {
    String str = "AB";
 }

The output is

AA
AB
BA
BB

edited Oct 9, 2014 at 3:08

answered Oct 9, 2014 at 3:02

Deval Khandelwal

3,5581 gold badge29 silver badges40 bronze badges

4 Comments

user2300867 Over a year ago

What is prefix? I believe I need to keep the header of my method as: public static ArrayList<String> permutationsUnique(String word) {

Deval Khandelwal Over a year ago

prefix is basically the string which will be added in the front using recursion. You have to go through the code to understand it's meaning because it is too complex to explain the recursive process.

Deval Khandelwal Over a year ago

and my method is different than yours. You have used arraylist but I have used string which is recommended.

user2300867 Over a year ago

I see... The recursive method is suposed to be a helper method that returns the string. This is how I was calling it: for (String s : permutations(keyWord))....

Jas · Accepted Answer · 2018-12-30 09:56:38Z

0

I have another solution with a char array, but it works for any kind of array. Here, instead of print the characters (or whatever data type you want to), you can add your list and append the elements to it.

static void permuteAll(char [] a)
{   
    permuteArray(a, new char[a.length], 0);
}

static void permuteArray(char [] a, char [] s, int j)
{
    if(j == a.length)
    {
        System.out.println(new String(s));
        return;
    }

    for(int i = 0; i < a.length; i++)
    {
        s[j] = a[i];
        permuteArray(a, s, j+1);
    }

}

answered Dec 30, 2018 at 9:56

Jas

4159 silver badges23 bronze badges

Comments

Tsega Bar · Accepted Answer · 2021-11-22 16:53:11Z

0

public static void main(String args[]){
    String str="ABC";
    int maxSize =3;
    char[] chars = str.toCharArray();
    getCombination(chars, maxSize); 
}
static void getCombination(char[]chars, int maxSize){
   
  for(int i=0; i<chars.length; i++){
   combination(String.valueOf(chars[i]),chars,maxSize);
  }
}

static void combination(String prefix,char[] chars, int maxSize) {
if(prefix.length()>=maxSize){
    System.out.println(prefix);
}
else {
   for(int j= 0; j<chars.length;j++)
   {
      String newPrefix =prefix.concat(String.valueOf(chars[j]));
      combination(newPrefix,chars, maxSize);
   
  }
}
}

answered Nov 22, 2021 at 16:53

Tsega Bar

12 bronze badges

1 Comment

Community Over a year ago

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.

Collectives™ on Stack Overflow

Recursive String permutation with repetitions allowed

4 Answers 4

Comments

4 Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

4 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related