0

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...

ashwinsakthi
  • 1,856
  • 4
  • 27
  • 56
  • Shouldn't there be many more permutations for `1234`, e.g. `4132`? For `1234`, 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? – tobias_k Apr 02 '16 at 13:15
  • yes you are right.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... – ashwinsakthi Apr 02 '16 at 13:19
  • Where did 1324, 1342, 1423, 1432, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 4123, 4132, 4213, and 4231 go? – Sergey Kalinichenko Apr 02 '16 at 13:20
  • "how to find the number of arrays needed"? Look up "factorial" – Sergey Kalinichenko Apr 02 '16 at 13:21
  • The proposed answer holds good for strings, but for an array the logic is different. – ashwinsakthi Apr 02 '16 at 13:27
  • 1
    take the array and split it in parts – Maytham Fahmi Apr 02 '16 at 13:28
  • @ashwinsakthi Create a string of the arrays if you are lazy. Else, by seeing that code, you must be able to find out the logic for arrays too. – dryairship Apr 02 '16 at 13:34
  • Why do it yourself? I googled "java permutation" and got http://introcs.cs.princeton.edu/java/23recursion/Permutations.java.html. It almost works. – Shear Plane Apr 03 '16 at 09:34

2 Answers2

2

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.

Marko vlaić
  • 316
  • 5
  • 15
1

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);   
        }
    }
}
Chen Pang
  • 1,370
  • 10
  • 11