Permutation and subsequences of string

Question

I have an assignment to solve this problem. I’m not too sure how permutate works by tracing, just tried on inspiration and it works. This code runs on all provided test cases, but I’m just trying to look for ways of improvement in terms of time efficiency, space efficiency and styling.

Question Description

Bob the Dog has a word W containing N distinct lowercase letters (‘a’ to ‘z’).

Bob the Dog would like you to generate all possible permutations of the N letters followed by all possible sub-sequences of the N letters.

A permutation of the letters in W is generated by reordering the letters in W. You are to print all possible such re-orderings. For example, permutations of ‘cat’ are ‘cta’, ‘cat’, ‘atc’, ‘act’, ‘tac’, ‘tca’.

A sub-sequence of the letters in W is generated by choosing a non-empty subset of letters in W, without changing their relative order in W. For example, sub-sequences of ‘cat’ are ‘c’, ‘a’, ‘t’, ‘ca’, ‘at’, ‘ct’, ‘cat’.

The permutations should be printed in increasing lexicographical order, followed by the sub- sequences in increasing lexicographical order as well. In order to sort a list of strings in lexicographical order, you can simply utilize Collections.sort on a list of Strings. The default compareTo function in String class is already comparing in lexicographical order.

Input

The input contains a single line, containing the word W of length N.

Output

The output should contain (N!) + 2^N – 1 lines.

The first N! lines should contain all possible permutations of the letters in W, printed in increasing lexicographical order.

The next 2^N-1 lines should contain all possible sub-sequences of the letters in W, printed in increasing lexicographical order as well.

Limits

• 1≤N≤9

• W will only contain distinct lowercase letters (‘a’ to ‘z’).

Here is my attempt, do inform me if any more information is needed.Thanks.

import java.util.*;
import java.util.stream.Collectors;

public class Generate {
    private void run() {
        Scanner sc = new Scanner(System.in);
        String inputs = sc.next();
        List<String> sortedString = inputs.codePoints()//split into ASCII int
        .sorted()
        .mapToObj(x->String.valueOf((char)x))//changes to String
        .collect(Collectors.toList());
        //breaks the string into an array of String and sort a smaller list

        permutate(sortedString, new boolean[sortedString.size()],0,new StringBuilder());

        subSequence(inputs);//order requires the original string


    }

    public static void main(String[] args) {
        Generate newGenerate = new Generate();
        newGenerate.run();
    }

    //uses a flag Array to note which character is used before instead of making new String arrays
    public static void permutate(List<String> lst, boolean [] used, int numUsed,StringBuilder builder) {
        if (lst.size()==numUsed) {
            System.out.println(builder);//each permutation must be as long as the input size
            return;
        }
        for (int i=0;i<lst.size();i++) {    //For each loop, 1 case will use the character, the other wouldn't 
            if (used[i]) {
                continue;
            }
            String current = lst.get(i);

            StringBuilder copiedBuilder = new StringBuilder(builder.toString());//shallow copy of a String, 
            //Builders are generally faster than concatenation
            boolean [] copied = Arrays.copyOf(used,lst.size());//duplicate 1 flag array for the other case
            copied[i]=true;     //update only one of them
            copiedBuilder.append(current);
            permutate(lst,copied,numUsed+1,copiedBuilder);
        }

    }

    //helper method that fills the results list with StringBuilders to be sorted
    public static void basicSubSequence(String input,StringBuilder builder, int position,ArrayList<String> results) {
        if (position==input.length()) {//no more characters in input is left
            if (builder.length()==0) {//excludes the empty String as a subsequence
                return;
            }
            results.add(builder.toString());
            return;
        }
        //similarly, make a copy of builder and update only the copy
        StringBuilder copiedBuilder = new StringBuilder(builder.toString());
        char current = input.charAt(position);
        copiedBuilder.append(current);
        basicSubSequence(input,copiedBuilder,position+1,results);
        basicSubSequence(input,builder,position+1,results); 
    }

    public static void subSequence(String inputs) {
        ArrayList<String> seqResults = new ArrayList<>();//creates a result list
        basicSubSequence(inputs, new StringBuilder(),0,seqResults);//fills up the list
        Collections.sort(seqResults);//sorts the list
        for (String str: seqResults) {
            System.out.println(str);
        }
    }



}

Sample Input

tan

Output

ant
atn
nat
nta
tan
tna
a
an
n
t
ta
tan
tn

 

Disclaimer

There are some concerns regarding the use of words like "subsequence", which might include some cases that are not included here. However, this code works for all the test cases provided, which means my interpretation of it matches the meaning of the author's, that of which I cannot control.

Answer 1

The question states you get one line but you operate on a list of strings.

Don't use end-of-line comments. They're hard to read and impossible to format.

Permutations can be generated with a simple recursive divide-and-conquer algorithm:

1. If string length is 1, there is only one permutation.
2. For each character in the string
   1. Swap character and the first one
   2. Generate permutations for substring after first character

You need to pass the string, the index of the start of the substring and a collection where you collect the results through the recursions.

Answer 2

Your algorithm is single threaded, and does not modify the partial solution; so you need not copy about stuff. You can instead just undo what you modified in each step, namely remove the letter you appended and mark it unused.

There is also no reason to convert chars to strings.

private static void permutate2(char[] letters, boolean[] used, int numUsed, StringBuilder builder) {
    if (used.length == numUsed) {
        System.out.println(builder);
        return;
    }

    for (int i = 0; i < used.length; i++) {
        if (used[i]) {
            continue;
        }

        char current = letters[i];

        used[i] = true;
        builder.append(current);
        permutate2(letters, used, numUsed + 1, builder);
        used[i] = false;
        builder.setLength(builder.length() - 1);
    }

}