Ggthjy

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.

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.

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);

    }



}