Print integer combinations in ascending order

Asked

Viewed 1,566 times

4

"Given two nonnegative integers m and n, generate all combinations of integer size m 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); (1 2 3); (1 2 4); (1 3 4); (2 3 4)"

I don’t know how to solve this exercise. The most I could was to 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 take the vector 0 1 2 again and add 1 to the last two elements, then just the last one and so on. But I don’t know how to do that. I thought to use 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 for 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;
        }

1 answer

2

You can solve your problem using recursiveness, follow a class in adapted Java 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.

  • Thank you for your help. The only problem is that I don’t understand... I only know the basics. From what I have learned so far (which is what the teacher expects to find in the answer), I should use FOR loops and auxiliary variables. I’m going to post on the question the code I have so far.

  • @Cristianedossantoscosta, as I was new here, I had no option to comment, so I had to reply, the code I gave you was based on the link that is in the answer, if I find or manage to do with FOR edit the answer.

  • Thank you very much!

Browser other questions tagged

You are not signed in. Login or sign up in order to post.