CODEWITHSUNDEEP
javastringrecursionpermutation
user2300867
user2300867

Reputation: 603

Recursive String permutation with repetitions allowed

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

Upvotes: 0

Views: 2539

Answers (4)

Tsega Bar
Tsega Bar

Reputation: 1

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);
   
  }
}
}

Upvotes: 0

Jas
Jas

Reputation: 415

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);
    }

}

Upvotes: 0

Atul Kumbhar
Atul Kumbhar

Reputation: 1083

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;
            }
        }
    }
}
}

Upvotes: 2

Deval Khandelwal
Deval Khandelwal

Reputation: 3548

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

Upvotes: 1

Related Questions