I want to print number of possible non-empty sequences of letters . Eg.

String str="ABC";

Expected output is

A,B,C
AB,AC,BC,BA,CA,CB
ABC,ACB,BAC,BCA,CAB,CBA`

But i get the below output which is incorrect. How to fix my code

BB CC A AB ACC BC ABC AC B BBC CCC BCC C CBC CB

I have written the below code using Recurion

String tiles = "ABC";
Set<String> ans = new HashSet<>();
solve(tiles, 0, "", ans);

public static void solve(String tiles, int idx, String output, Set<String> ans) {

        ans.add(output);

        if (idx >= tiles.length()) {
            return;
        }

        for (int i = idx; i < tiles.length(); i  ) {

            solve(tiles, idx   1, output   tiles.charAt(i), ans);

        }

    }

This is how recursion tree would look like for str="AAB"

CodePudding user response：

You need to ignore the first passing of the "" from output and then you need to ignore each letter you already passed through

public static void main(String[] args) {
    String tiles = "ABC";
    List<String> ans = new ArrayList<>();
    solve(tiles, "", ans);
    System.out.println(ans);
}
public static void solve(String tiles, String output, List<String> ans) {
    if (!output.equals("")) ans.add(output);
    for (int i = 0; i < tiles.length(); i  ) {
        String str = tiles.substring(0, i)   tiles.substring(i   1);
        solve(str, output   tiles.charAt(i), ans);
    }
}

Output

[A, AB, ABC, AC, ACB, B, BA, BAC, BC, BCA, C, CA, CAB, CB, CBA]

CodePudding user response：

you can try this

public class Permutation {

    public static List<String> getPermutations(String str) {
        Set<String> permutations = new HashSet<>();
        permute(str, "", permutations);
        return new ArrayList<>(permutations);
    }

    private static void permute(String string, String prefix, Set<String> permutations) {
        if (string.length() == 0) {
            permutations.add(prefix);
        } else {
            for (int i = 0; i < string.length(); i  ) {
                char charAt = string.charAt(i);
                String remainingString = string.substring(0, i)   string.substring(i   1);
                permute(remainingString, prefix   charAt, permutations);
            }
        }
    }
}

The "permute" method takes in 3 parameters: a string, a prefix string and a set of permutations.

• The "permute" method takes in 3 parameters: a string, a prefix string and a set of permutations.
• If the input string is not empty, it uses a for loop to iterate through the characters of the input string.
• For each iteration, it gets the character at the current index, creates a new string by removing that character from the input string.
• it then calls the permute method 3 times:
  1. it then calls the permute method 3 times:
  2. One with the original string and prefix
  3. One with the remaining string and prefix

This way, the function explores all the possible permutations of the characters in the input string, including the option of not having one of the characters in the permutation and the permutation of positions, without including an empty string as an option.

Then you use like:

Permutation p = new Permutation();
List<String> permutations = p.getPermutations("abc");

CodePudding user response：

Make 1 change:

Set<String> ans = new TreeSet<>(Comparators.comparing(String::length).thenComparing(s -> s));