Find all permutations of non-repeating letters in a word

Question

Given 3 unique letters: can you print the six possible non repeating combinations of the letters, using a recursive function. 'cat' should output: cat, act, atc, tac, tca and cta. Here's my program, I'm having trouble finding the recursive algorithm. Here's my attempt:

 static void findWords(StringBuilder string, int start, int stride) {
    //1. iterate through all possible combinations of the chars recursively

    System.out.println(string);

    if (stride < string.length() && start < string.length())
    {
        char temp = string.charAt(stride);
        string.setCharAt(stride, string.charAt(start));
        string.setCharAt(start, temp);

        findWords(string, start, stride + 1);

        findWords(string, start + 1, stride + 1 );


    }
}

public static void main(String[] args)
{

   StringBuilder word = new StringBuilder("cat");
   findWords(word,0,1);
}

Answer 1

The algorithm I used is quite simple. Make each character the first character of the string and find combinations with other two characters. So for the characters c, a, t the combinations would be

c at
c ta

a ct
a tc

t ca
t ac

Code:

static void findWords(String str, int pos) {
    if(str == null || pos < -1) {
        return;
    }

    int len = str.length();
    if(pos + 1 < len) {
        findWords(str, pos + 1);
    }

    //find char swap positions
    int pos1 = (pos + 1) % len;
    int pos2 = (pos - 1 + len) % len;

    char[] chars = str.toCharArray();
    String str1 = new String(new char[] {chars[pos], chars[pos1], chars[pos2]});
    String str2 = new String(new char[] {chars[pos], chars[pos2], chars[pos1]});

    System.out.println(str1);
    System.out.println(str2);
}

public static void main(String[] args) {
    String word = new String("abc");
    findWords(word, 0);
}

Answer 2

Here is a full working example with my comments to explain the algorithm.

This solution is based on backtracking. Read more about that here. Look at the problem as a tree. In your example the word is "cat". Here comes some ascii art...

                                      cat
                              /        |        \
                            Cat       Act       Tca 
                           /   \     /   \     /   \
                          CAt CTa   ACt ATc   TCa TAc

At each pass, you fix a letter (I put it as a capital). The further down the tree you get the less there is that you can swap because you've fixed a certain amount of letters in place (at level 0 nothing is fixed, at level 1, one letter is fixed so a swap can be done, at level 2 you have no more swaps (the swap would be with itself), so the recursion reaches its base case.

public static void main(String[] args) {
    // get all the permutations of a word with distinct letters
    Set<String> permutations = getPermutations("cat");

    // print the resulting set
    System.out.println(permutations);
}

private static Set<String> getPermutations(String string) {
    // recursive call to get a permutation of the given string and put it in
    // the set of permutations (initially empty)
    return permute(string, 0, string.length() - 1, new HashSet<String>());
}

private static Set<String> permute(String string, int left, int right, Set<String> set) {
    if (left == right) {
        // swap would be with itself so just add the string
        // this is the base case
        set.add(string);
    } else {
        for (int i = left; i <= right; i++) {
            // indices are different, something can be swapped so swap it
            string = swap(string, left, i);
            // permute the swapped string starting from the next available character
            permute(string, left + 1, right, set);
        }
    }
    return set;
}

// utility method to carry out the swapping
// you could do this with primitive char[] and probably improve performance
// but for the sake of simplicity as it's just an exercise I used a 
// StringBuilder
private static String swap(String in, int i, int j) {
    char tmp1 = in.charAt(i);
    char tmp2 = in.charAt(j);
    StringBuilder sb = new StringBuilder(in);
    // put the char at j in place of the char at i
    sb.setCharAt(i, tmp2);
    // and do the same the other way around
    sb.setCharAt(j, tmp1);

    return sb.toString();
}

Answer 3

Solution:

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    static List<String> resultList = new ArrayList<>();

    static void computeResult(char[] s, int pos, String resultString) {
        if (pos == 3) {
            resultList.add(resultString);
            return;
        }
        for (int i = 0; i < 3; ++i) {
            if (!resultString.contains(String.valueOf(s[i]))) {
                computeResult(s, pos + 1, resultString + s[i]);
            }
        }
    }

    public static void main(String... args) {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        sc.close();
        computeResult(s, 0, "");
        for(String str : resultList) {
            System.out.println(str);
        }
    }
}

Explanation:

The recursion is done by the computeResult function. It starts with an empty string, then it iterates through all possible letters 'c', 'a' and 't', appending them to the resultString, now there are 3 strings and for each one of them the function computeResult is called again. Then it does the same thing and also adds only those letters to the resultString that haven't been added yet, so to 'c' we append 'a' resulting in 'ca' and 't', resulting in 'ct', I think the rest you can figure out yourself.

Note than this works if the letters are unique. If they are not, for example you are given the string 'tat', you can transform it into t1a1t2 and do the same procedure for the array ['t1', 'a1', 't2'], then remove the digits.