Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Permutation of an array, with repetition, in Java

There are some similar questions on the site that have been of some help, but I can't quite nail down this problem, so I hope this is not repetitive.

This is a homework assignment where you have a set array of characters [A, B, C], and must use recursion to get all permutations (with repetition). The code I have sort of does this:

char[] c = {'A', 'B' , 'C'};

public void printAll(char[] c, int n, int k) {
    if (k == n) {
      System.out.print(c);
      return;
    }
    else {   
      for (int j = 0; j<n; j++) {
        for (int m = 0; m<n; m++) {
           System.out.print(c[k]); 
           System.out.print(c[j]); 
           System.out.print(c[m] + "\r\n");
        }
      }
    }        
    printAll(c, n, k+1);    
}

However, the parameter n should define the length of the output, so while this function prints out all permutations of length 3, it cannot do them of length 2. I have tried everything I can think of, and have pored over Google search results, and I am aggravated with myself for not being able to solve what seems to be a rather simple problem.

like image 942
user1788424 Avatar asked Oct 31 '12 12:10

user1788424


People also ask

How do you generate permutations of an array in Java?

You take first element of an array (k=0) and exchange it with any element (i) of the array. Then you recursively apply permutation on array starting with second element. This way you get all permutations starting with i-th element.

How do you find all permutations of an array?

All permutations of an array using STL in C++ Approach: The next possible permutation of the array can be found using next_permutation() function provided in STL. Syntax: bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);

How do you calculate permutations in Java?

We use the size() method to get the number of elements in the list. We set a constant value 3 to r, i.e., the number of items taken for the Permutation. After that, we use the permutation formula, i.e., fact(n)/fact(n-r) and store the result into the result variable.


1 Answers

If I understand correctly, you are given a set of characters c and the desired length n.

Technically, there's no such thing as a permutation with repetition. I assume you want all strings of length n with letters from c.

You can do it this way:

to generate all strings of length N with letters from C
 -generate all strings of length N with letters from C
     that start with the empty string.

to generate all strings of length N with letters from C
   that start with a string S
 -if the length of S is N
  -print S
 -else for each c in C
  -generate all strings of length N with letters from C that start with S+c

In code:

printAll(char[] c, int n, String start){
  if(start.length >= n){
    System.out.println(start)
  }else{
    for(char x in c){ // not a valid syntax in Java
      printAll(c, n, start+x);
    }
  }
}
like image 110
John Dvorak Avatar answered Nov 15 '22 21:11

John Dvorak