I have an array :
String wordArr[]=new String[3];
[1 2 3]
I want to form arrays with all combinations of the above.
Say.,
123 132 213 231 321 312
Can anyone give me an idea on how to find the number of arrays needed and logic in java ?
Am figuring out on how to iterate through an array with all possible combinations. Say if i iterate for the first time with 123 then next time i should iterate through 132 and 213 and so on...
This is pseudocode for generating permutations of any array a
Array permutations(a):
if size(a) == 0 then return [];
else:
Array result;
for i in range(size(a)):
for t in permutations(a.remove(i)):
result.push(Array(a[i]) + t)
return result
Hope this makes sense, I'll try to make java code for this and upload it as soon as I can.
It is useful to apply backtracking to the implementation of permutation. The basic idea is, for index loc which goes from 0 to array length, enumerate through all the possible pick for arr[loc]
I've implemented the following in Java, but it can be done in any language.
import java.util.*;
public class PermutationTest{
private static void swap(char[] arr, int i, int j) {
char tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
private static void permutations(char[] arr, int loc, int len, ArrayList<String> result) {
if (loc == len) {
result.add(new String(arr));
return;
}
// Pick the element to put at arr[loc]
permutations(arr, loc + 1, len, result);
for (int i = loc + 1; i < len; i++) {
// Swap the current arr[loc] to position i
swap(arr, loc, i);
permutations(arr, loc + 1, len, result);
// Restore the status of arr to perform the next pick
swap(arr, loc, i);
}
}
public static ArrayList<String> permutations(String str) {
ArrayList<String> result = new ArrayList<String>();
if (str.length() == 0) { return result; }
permutations(str.toCharArray(), 0, str.length(), result);
return result;
}
public static void main(String []args){
ArrayList<String> result = permutations("123");
for (String str : result) {
System.out.println(str);
}
}
}
1234, e.g.4132? For1234, there should be 24 (4!) permutations, not just 8. If not, please explain the logic behind those "permutations". Also, have you tried anything, e.g. looking for related questions here?