Permutation of an array, with repetition, in Java
Solution 1
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);
}
}
}
Solution 2
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
Solution 3
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]
Solution 4
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);
}
}
user1788424
Updated on June 04, 2022Comments
-
user1788424 almost 2 years
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.
-
John Dvorak over 11 yearsIf I understand the problem correctly, the required length of permutation is given
-
user1788424 over 11 yearsYou, 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.
-
user1788424 over 11 yearsAnd 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); } } }
-
MichelleJS almost 11 years@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.
-
John Dvorak almost 11 years@MichelleJS why would it be
abcabcabc
? You are adding a single character tostart
, then later backtracking and adding different one on the same place. In the first call (start == ""
):start.length == 0
, so it goes to theelse
branch. The first character ofC
isa
, sox == 'a'
in the first iteration."" + 'a' == "a"
, so the first recursive call is toprintAll("abc", 3, "a")
. The behavior you describe would occur if you were doingprintAll(c, n, start+c)
inside the loop - in which casex
would end up unused. -
MichelleJS almost 11 yearsThankyou 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.
-
John Dvorak almost 11 years@MichelleJS one option would be to remove
x
from the list of candidates (if your language is good enough, then justprintAll(c-x, n, start+x)
). The other would be to check ifx
is already isstart
before recursing. The first option might perform better, but the second option might be easier to implement in Java. -
a.dibacco over 3 yearsI suppose that they are called not "permutations with repetitions" but "dispositions with repetitions"