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

public class PermutationsFinder {

    private class Choice {

        ///////////////////
        // ADD CODE HERE //
        ///////////////////

    }

    private class State implements StateAllowingBacktracking<Choice> {

        private Stack<Choice> choicesMade;

        //////////////////////////////////////////////////////////////////////
        // ADD CONSTRUCTORS AND INSTANCE METHODS HERE, AS NEEDED OR DESIRED //
        //////////////////////////////////////////////////////////////////////
        
    }

    private int n;
    private int k;
    private StateAllowingBacktracking<Choice> state;
    static private int numPermutationsFound;

    public PermutationsFinder(int n, int k) {
        this.n = n;
        this.k = k;
        this.state = new State();
        PermutationsFinder.numPermutationsFound = 0;
    }
    
    public void searchFromCurrentState() {

        if (state.isSolution()) {
            reactToSolution();
            return; // stop pursuing this path
        }

        for (Choice choice : state.nextChoicesToConsider()) {
            if (state.isValid(choice)) {
                state.makeChoice(choice);
                searchFromCurrentState(); // <-- the recursive call!
                state.undoChoice(choice); // try another path
            }
        }
    }

    private void reactToSolution() {
        System.out.println(state);
        numPermutationsFound++;
    }

    public static void main(String[] args) {
        System.out.println("Enter n and k separated by a space to find all permutations of k values selected from 1 to n:");
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        scanner.close();
        scanner = new Scanner(line);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        scanner.close();

        scanner.close();

        PermutationsFinder finder = new PermutationsFinder(n,k);
        finder.searchFromCurrentState();
        System.out.println("number of permutations found: " + PermutationsFinder.numPermutationsFound);
    }
}