Swapping Array with Repeat in Java

Question

There are some similar questions on the site that have helped a bit, but I can’t completely solve this problem, so I hope this does not happen again.

This is homework in which you have the character set [A, B, C] and must use recursion to get all permutations (with repetition). The code I have 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 must determine the length of the output, so while this function displays all permutations of length 3, it cannot perform their lengths 2. I tried everything I could think of and looked at Google for the search results, and I’m aggravated with myself that I couldn’t solve what seems like a pretty simple problem.

Answer 1

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

Technically, there is no such thing as repetition permutation. I assume that you need all strings of length n with letters from c .

You can do it as follows:

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

Answer 2

I use this implementation of java repetition permutations. A ~ (n, m): n = array length, m = k. m may be greater or less than 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); } } 

Output example

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

Answer 3

I had an idea. What to do if you added a hidden character (H for hidden) [A, B, C, H], then did all the permanent permutations (you said you know how to do this). Then, when you read this, you stop at a hidden character, for example. [B, A, H, C] will become (B, A).

Hmm, the disadvantage is that you have to keep track of which ones were created, although [B, H, A, C] is the same as [B, H, C, A]

Answer 4

Here is the C # version for generating permutations of a given string with repetitions:

(the essential idea is the number of permutations of a string of length n with repetitions 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); } } 

The following are 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); } }