/*
    Permutations.java - a class to calculate all permutations of a string of varying lengths
    Copyright (C) 2009, Viren Kumar

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.

 */

import java.util.*;

public class Permutations {
    
    public ArrayList<String> getPerms(String input, int k){
        
        //base case of requested permutation length reached
        if (k == 0){
            ArrayList<String> result = new ArrayList<String>();
            result.add("");
            return result;
        }
        //base case of one-character string
        if (input.length() == 1 ){
            ArrayList<String> result = new ArrayList<String>();
            result.add(input);
            return result;
        }       
        
        ArrayList<String> finalResult = new ArrayList<String>();
        
        //extract one letter at a time and recurse on rest
        StringBuilder sb = new StringBuilder(input);
        for (int i = 0; i < input.length();i++){
            String prefix = new StringBuilder().append(input.charAt(i)).toString();
            //now delete the char
            sb = sb.deleteCharAt(i);
            //get all k-1 permutations of the rest
            ArrayList<String> intermediate = getPerms(sb.toString(),k-1);
            //add deleted character as prefix
            for (String s : intermediate){
                finalResult.add(prefix+s);
            }
            sb = new StringBuilder(input);
        }
        
        return finalResult;
        
    }

}