10

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.

Improve this question
2
  • What does "with repetition" mean here? Commented Oct 31, 2012 at 14:14
  • It just means that once a character is used, it can be used again. So the number of possible outputs is 3^3, and not 3!. Commented Oct 31, 2012 at 21:40

4 Answers 4

Reset to default
10

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);
    }
  }
}
Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

You, sir, are not just a gentleman and a scholar. You are a prince, a gentleman, and a scholar. Some other people online suggested something similar, except using an array and not a string. However, your explanation was much clearer.
And for reference, if anyone is interested, here is the final function, where the n parameter controls the length of each line that is printed: public void printAll3(char[] c, int n, int k, String s) { if (s.length() >=n) {System.out.print(s + "\r\n"); return;} else if (k<n) {for (int i = 0; i< c.length; i++) { printAll3(c, n, k+1, s + c[i]); //System.out.print(s); } } }
@JanDvorak I know this is old but I had a similar problem I was trying to solve and I modified this and it totally worked.However I don't understand how your final call printAll(c,n,start+x) works. I printed it out and start goes like this for the first few calls (a, aa, aaa, aab, aac, ab, aba). I don't really understand why it doesn't end up being (abc, abcabc, abcabcabc). I was hoping you could explain it. I have been trying to trace it and I understand that each time print all calls itself inside the loop it calls itself n more times. Anyway if you could I would like some more explaination.
@MichelleJS why would it be abcabcabc? You are adding a single character to start, then later backtracking and adding different one on the same place. In the first call (start == ""): start.length == 0, so it goes to the else branch. The first character of C is a, so x == 'a' in the first iteration. "" + 'a' == "a", so the first recursive call is to printAll("abc", 3, "a"). The behavior you describe would occur if you were doing printAll(c, n, start+c) inside the loop - in which case x would end up unused.
Thankyou very much. I drew it all out on a piece of paper in order to understand. I now have to do the other the same thing without repetition. I'm not sure how to modify this code to do that but this has been a very good start.
|
3

I use this java realization of permutations with repetitions. A~(n,m): n = length of array, m = k. m can be greater or lesser then n. 

public class Permutations {


    static void permute(Object[] a, int k, PermuteCallback callback) {
        int n = a.length;

        int[] indexes = new int[k];
        int total = (int) Math.pow(n, k);

        Object[] snapshot = new Object[k];
        while (total-- > 0) {
            for (int i = 0; i < k; i++){
                snapshot[i] = a[indexes[i]];
            }
            callback.handle(snapshot);

            for (int i = 0; i < k; i++) {
                if (indexes[i] >= n - 1) {
                    indexes[i] = 0;
                } else {
                    indexes[i]++;
                    break;
                }
            }
        }
    }

    public static interface PermuteCallback{
        public void handle(Object[] snapshot);
    };

    public static void main(String[] args) {
        Object[] chars = { 'a', 'b', 'c', 'd' };
        PermuteCallback callback = new PermuteCallback() {

            @Override
            public void handle(Object[] snapshot) {
                for(int i = 0; i < snapshot.length; i ++){
                    System.out.print(snapshot[i]);
                }
                System.out.println();
            }
        };
        permute(chars, 8, callback);
    }

}

Example output is 

aaaaaaaa
baaaaaaa
caaaaaaa
daaaaaaa
abaaaaaa
bbaaaaaa
...
bcdddddd
ccdddddd
dcdddddd
addddddd
bddddddd
cddddddd
dddddddd
Improve this answer

Comments

1

I just had an idea. What if you added a hidden character (H for hidden) [A, B, C, H], then did all the fixed length permutations of it (you said you know how to do that). Then when you read it off, you stop at the hidden character, e.g. [B,A,H,C] would become (B,A).

Hmm, the downside is that you would have to track which ones you created though [B,H,A,C] is the same as [B,H,C,A]

Improve this answer

1 Comment

If I understand the problem correctly, the required length of permutation is given
1

Here is c# version to generate the permutations of given string with repetitions:

(essential idea is - number of permutations of string of length 'n' with repetitions is n^n).

string[] GetPermutationsWithRepetition(string s)
        {
            s.ThrowIfNullOrWhiteSpace("s");
            List<string> permutations = new List<string>();
            this.GetPermutationsWithRepetitionRecursive(s, "",
                permutations);
            return permutations.ToArray();
        }
        void GetPermutationsWithRepetitionRecursive(string s, string permutation, List<string> permutations)
        {
            if(permutation.Length == s.Length)
            {
                permutations.Add(permutation);
                return;
            }
            for(int i =0;i<s.Length;i++)
            {
                this.GetPermutationsWithRepetitionRecursive(s, permutation + s[i], permutations);
            }
        }

Below are the corresponding unit tests:

[TestMethod]
        public void PermutationsWithRepetitionTests()
        {
            string s = "";
            int[] output = { 1, 4, 27, 256, 3125 };
            for(int i = 1; i<=5;i++)
            {
                s += i;
                var p = this.GetPermutationsWithRepetition(s);
                Assert.AreEqual(output[i - 1], p.Length);
            }
        }
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.