Print combinations of integers in ascending order

4

"Given two nonnegative integer numbers m and n, generate all m-size combinations of integers from 0 to n-1, in ascending order.

Example: m = 3 and n = 5

(0 1 2); (0 1 3); (0 1 4); (0 2 3); (0 2 4); (0 3 4); (12); (1 2 4); (1 3 4); (2 3 4) "

I do not know how to solve this exercise. The most I could do was create the vector 0 1 2. I realized that I need to add 1 to the last element until it reaches the value n-1, then I get the vector 0 1 2 again and add 1 to the last two elements, then only to the last one and so on. But I do not know how to do that. I thought of using a FOR for each round of sums, but in case the amount of FORs would depend on the value of m and the algorithm should serve any values of m and n, so I understood.

public static void main(String[] args) {
        int n, m, i, j;
        Scanner ent = new Scanner (System.in);
        System.out.println("Digite o valor de m:");
        m = ent.nextInt();
        System.out.println("Digite o valor de n:");
        n = ent.nextInt(); 
        int [] v = new int [m];
        for (i=0; i<m; i++) {
            v[i] = i;
        }
    
asked by anonymous 23.11.2014 / 20:39

1 answer

2

You can solve your problem using recursion, following an adapted Java class of that link .

public class Combinacao {

    private int numeros[];
    private int posicoes;
    private int resultado[];
    private int quantidadeCombinacoes;

    public Combinacao(int m, int n) {
        numeros = new int[n];
        for (int i = 0; i < n; i++) {
            numeros[i] = i;
        }
        posicoes = m;
        resultado = new int[posicoes];
        quantidadeCombinacoes = 0;
    }

    private void combinar(int inicio, int fim, int profundidade) {
        if ((profundidade + 1) >= posicoes) {
            for (int x = inicio; x <= fim; x++) {
                resultado[profundidade] = numeros[x];
                quantidadeCombinacoes++;
                System.out.print("(");
                for (int i = 0; i < posicoes; i++) {
                    System.out.printf("%d%s", resultado[i], (i == posicoes - 1) ? "" : " ");
                }
                System.out.print("); ");
            }
        } else {
            for (int x = inicio; x <= fim; x++) {
                resultado[profundidade] = numeros[x];
                combinar(x + 1, fim + 1, profundidade + 1);
            }
        }
    }

    public void imprimirCombinacoes() {
        combinar(0, numeros.length - posicoes, 0);
    }

    public int getQuantidadeCombinacoes() {
        return quantidadeCombinacoes;
    }
}

To use do the following:

public static void main(String[] args) {
    Combinacao combinacao = new Combinacao(3, 5);
    combinacao.imprimirCombinacoes();
    System.out.println("\nTotal de combinacoes: " + combinacao.getQuantidadeCombinacoes());
}

The Combination class then receives parameters in the constructor, these parameters are respectively m and n, as in your question.

    
23.11.2014 / 23:39