순열,조합

순열

class Main {
    public static void main(String args[]) throws Exception {
        Permutation per = new Permutation();
        int n = 6;
        int[] arr = {1,2,3,4,5,6};

        per.create(arr, 2);
        ArrayList<int[]> perList =  per.getList();
        for(int p = 0; p < perList.size(); p++){
            for(int i = 0; i < perList.get(p).length; i++){
                System.out.print(perList.get(p)[i] + " ");
            }
            System.out.println();
        }

        PermutationString ps = new PermutationString();
        String tt = "abcdef";
        ps.create(tt, n);
        ArrayList<char[]> perStringList =  ps.getList();

        for(int p = 0; p < perStringList.size(); p++){
            for(int i = 0; i < perStringList.get(p).length; i++){
                System.out.print(perStringList.get(p)[i] + " ");
            }
            System.out.println();
        }
    }
}

class Permutation{
    ArrayList<int[]> list = new ArrayList();

    public void create(int[] arr, int r){
        int[] output = new int[r];
        boolean[] visited = new boolean[arr.length];
        permutation(arr, output, visited, 0, arr.length, r);
    }

    public void permutation(int[] arr, int[] output, boolean[] visited, int depth, int n, int r){
        if(depth == r){
            list.add(output.clone());
            return;
        }

        for(int i = 0; i < n; i++){
            if(!visited[i]){
                visited[i] = true;
                output[depth] = arr[i];
                permutation(arr, output, visited, depth + 1, n, r);
                visited[i] = false;
            }
        }
    }

    public ArrayList<int[]> getList(){
        return list;
    }
}

class PermutationString{
    ArrayList<char[]> list = new ArrayList();

    public void create(String arr, int r){
        char[] output = new char[r];
        boolean[] visited = new boolean[arr.length()];
        permutation(arr.toCharArray(), output, visited, 0, arr.length(), r);
    }

    public void permutation(char[] arr, char[] output, boolean[] visited, int depth, int n, int r){
        if(depth == r){
            list.add(output.clone());
            return;
        }

        for(int i = 0; i < n; i++){
            if(!visited[i]){
                visited[i] = true;
                output[depth] = arr[i];
                permutation(arr, output, visited, depth + 1, n, r);
                visited[i] = false;
            }
        }
    }

    public ArrayList<char[]> getList(){
        return list;
    }
}

조합

class Main {
    public static void main(String args[]) throws Exception {
        Combination com = new Combination();
        int[] arr = {1,2,3,4,5,6};

        com.create(arr, 2);

        ArrayList<int[]> perList =  com.getList();
        for(int p = 0; p < perList.size(); p++){
            for(int i = 0; i < perList.get(p).length; i++){
                System.out.print(perList.get(p)[i] + " ");
            }
            System.out.println();
        }

        CombinationString comString = new CombinationString();
        String tt = "abcdef";
        comString.create(tt, 2);
        ArrayList<char[]> perStringList =  comString.getList();

        for(int p = 0; p < perStringList.size(); p++){
            for(int i = 0; i < perStringList.get(p).length; i++){
                System.out.print(perStringList.get(p)[i] + " ");
            }
            System.out.println();
        }
    }
}

class Combination{
    private ArrayList<int[]> list = new ArrayList();
    private int originalR;

    public void create(int[] arr, int r){
        boolean[] visited = new boolean[arr.length];
        originalR = r;
        combination(arr, visited, 0, arr.length, r);
    }

    private void combination(int[] arr, boolean[] visited, int start, int n, int r) {
        if(r == 0) {
            list.add(select(arr, visited));
            return;
        } else {
            for(int i=start; i<n; i++) {
                visited[i] = true;
                combination(arr, visited, i + 1, n, r - 1);
                visited[i] = false;
            }
        }
    }

    private int[] select(int[] arr, boolean[] visited){
        int[] result = new int[originalR];
        int index = 0;

        for(int i = 0; i < arr.length; i++){
            if(visited[i]){
                result[index++] = arr[i];
            }
        }
        return result;
    }

    public ArrayList<int[]> getList(){
        return list;
    }
}

class CombinationString{
    private ArrayList<char[]> list = new ArrayList();
    private int originalR;

    public void create(String arr, int r){
        boolean[] visited = new boolean[arr.length()];
        originalR = r;
        combination(arr.toCharArray(), visited, 0, arr.length(), r);
    }

    private void combination(char[] arr, boolean[] visited, int start, int n, int r) {
        if(r == 0) {
            list.add(select(arr, visited));
            return;
        } else {
            for(int i=start; i<n; i++) {
                visited[i] = true;
                combination(arr, visited, i + 1, n, r - 1);
                visited[i] = false;
            }
        }
    }

    private char[] select(char[] arr, boolean[] visited){
        char[] result = new char[originalR];
        int index = 0;

        for(int i = 0; i < arr.length; i++){
            if(visited[i]){
                result[index++] = arr[i];
            }
        }
        return result;
    }

    public ArrayList<char[]> getList(){
        return list;
    }
}

멱집합

class Main {
    public static void main(String args[]) throws Exception {
        int[] arr = {1,2,3,4,5,6};
        PowerSet pos = new PowerSet();

        pos.create(arr);

        ArrayList<int[]> perList =  pos.getList();
        for(int p = 0; p < perList.size(); p++){
            for(int i = 0; i < perList.get(p).length; i++){
                System.out.print(perList.get(p)[i] + " ");
            }
            System.out.println();
        }

        PowerSetString poss = new PowerSetString();
        String tt = "abcdef";
        poss.create(tt);

        ArrayList<char[]> perStringList =  poss.getList();

        for(int p = 0; p < perStringList.size(); p++){
            for(int i = 0; i < perStringList.get(p).length; i++){
                System.out.print(perStringList.get(p)[i] + " ");
            }
            System.out.println();
        }
    }
}

class PowerSet{
    private ArrayList<int[]> list = new ArrayList();

    public void create(int[] arr){
        boolean[] visited = new boolean[arr.length];

        powerSet(arr, visited, arr.length, 0);
    }

    private void powerSet(int[] arr, boolean[] visited, int n, int index){
        if(index == n){
            list.add(select(arr, visited));
            return;
        }

        visited[index] = false;
        powerSet(arr, visited, n, index + 1);

        visited[index] = true;
        powerSet(arr, visited, n, index + 1);
    }

    private int[] select(int[] arr, boolean[] visited){
        int[] result;
        int index = 0;
        int size = 0;

        for(int i = 0; i < arr.length; i++){
            if(visited[i]){
                ++size;
            }
        }

        result = new int[size];

        for(int i = 0; i < arr.length; i++){
            if(visited[i]){
                result[index++] = arr[i];
            }
        }
        return result;
    }

    public ArrayList<int[]> getList(){
        return list;
    }
}

class PowerSetString{
    private ArrayList<char[]> list = new ArrayList();

    public void create(String arr){
        boolean[] visited = new boolean[arr.length()];

        powerSet(arr.toCharArray(), visited, arr.length(), 0);
    }

    private void powerSet(char[] arr, boolean[] visited, int n, int index){
        if(index == n){
            list.add(select(arr, visited));
            return;
        }

        visited[index] = false;
        powerSet(arr, visited, n, index + 1);

        visited[index] = true;
        powerSet(arr, visited, n, index + 1);
    }

    private char[] select(char[] arr, boolean[] visited){
        char[] result;
        int index = 0;
        int size = 0;

        for(int i = 0; i < arr.length; i++){
            if(visited[i]){
                ++size;
            }
        }

        result = new char[size];

        for(int i = 0; i < arr.length; i++){
            if(visited[i]){
                result[index++] = arr[i];
            }
        }
        return result;
    }

    public ArrayList<char[]> getList(){
        return list;
    }
}