Permutations of integers

Question

Permutations of integers

Navigation

#1 by (0 votes)

2

I have the following problem:

Given an entry n I have to calculate the number of permutations possible with the digits that compose it. For example, if n = 123 I have 6 numbers that can be formed: 123 , 132 , 231 , 213 , 312 , 321 . But if the input is 100 the answer would be 1, since the possible permutations are: 001 , 010 and 001 but 001 , 010 are not valid representations for the problem. >

Applying the mathematical formula for permutation with repetition, I came up with the following code:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Similaridade {

  public int solucao(int n) {
    List<Integer> digitos = separarDigitos(n);
    Map<Integer, Integer> ocorrencias;
    Integer resultado;
    Integer[] valores;

    ocorrencias = this.contarOcorrencias(digitos);
    valores = ocorrencias.values().toArray(new Integer[ocorrencias.size()]);
    resultado = this.calcularPermutacao(digitos.size(), valores);

    return resultado;
  }

  public Integer calcularPermutacao(Integer total, Integer... repeticoes) {
    Long denominador = 1L;
    Long numerador;
    Long resultado;

    for (Integer repeticao : repeticoes) {
      if (repeticao > 1) {
        denominador = denominador * this.fatorial(repeticao);
      }
    }

    numerador = this.fatorial(total);
    resultado = numerador / denominador;

    return resultado.intValue();
  }

  private List<Integer> separarDigitos(int numero) {
    List<Integer> resultado = new ArrayList<>();

    while (numero != 0) {
      int digito = numero % 10;
      numero = numero / 10;
      resultado.add(digito);
    }

    return resultado;
  }

  private Map<Integer, Integer> contarOcorrencias(List<Integer> numeros) {
    Map<Integer, Integer> ocorrencias = new HashMap<>();

    numeros.forEach((numero) -> {
      if (ocorrencias.containsKey(numero)) {
        ocorrencias.put(numero, ocorrencias.get(numero) + 1);
      } else {
        ocorrencias.put(numero, 1);
      }
    });

    return ocorrencias;
  }

  private Long fatorial(Integer numero) {
    Long resultado = 1L;

    for (int fator = 2; fator <= numero; fator++) {
      resultado = resultado * fator;
    }

    return resultado;
  }
}

But now I need to calculate and apply the results with zeros.

How can I do this? Remembering that the performance is important and that, so, just make the changes to have all the possibilities is not interesting. The resolution becomes more complete by applying the discount to the formula or after calculating it.

Examples:

Input: 1213 . Output: 12 .
Input: 123 . Output: 6 .
Input: 100 . Output: 1 .
Input: 120 . Output: 4 .
Input: 1200 . Output: 6 .
Input: 0 . Output: 1 .

java

asked by anonymous 24.02.2018 / 01:39

1 answer

Enable "featured image" on specific WordPress pages doubt select with modal

score 0 · Accepted Answer

I was able to arrive at a calculated result at the ratio where the number zero appears and discounted from the permutations calculation. The end result was as follows:

import java.util.HashMap;
import java.util.Map;

public class Similaridade {

  public int solucao(int n) {
    Map<Integer, Integer> ocorrencias = new HashMap<>();
    Integer total = this.separarDigitos(n, ocorrencias);
    Integer resultado;
    Integer[] valores;

    valores = ocorrencias.values().toArray(new Integer[ocorrencias.size()]);
    resultado = this.calcularPermutacao(total, valores);

    // Desconsidera os zeros no início
    if (ocorrencias.containsKey(0)) {
      Double quantidadeDeZeros = Double.valueOf(ocorrencias.get(0));
      Double quantidadeDeDigitos = Double.valueOf(total);
      Double provisorio = Double.valueOf(resultado);

      provisorio = provisorio - (provisorio / (quantidadeDeDigitos / quantidadeDeZeros));
      resultado = provisorio.intValue();
    }

    return resultado;
  }

  public Integer calcularPermutacao(Integer total, Integer... combinacoes) {
    Long denominador = 1L;
    Long numerador;
    Long resultado;

    for (Integer combinacao : combinacoes) {
      if (combinacao > 1) {
        denominador = denominador * this.fatorial(combinacao);
      }
    }

    numerador = this.fatorial(total);
    resultado = numerador / denominador;

    return resultado.intValue();
  }

  private Integer separarDigitos(int numero, Map<Integer, Integer> ocorrencias) {
    Integer total = 0;

    while (numero != 0) {
      int digito = numero % 10;

      numero = numero / 10;

      if (ocorrencias.containsKey(digito)) {
        ocorrencias.put(digito, ocorrencias.get(digito) + 1);
      } else {
        ocorrencias.put(digito, 1);
      }

      total++;
    }

    return total;
  }

  private Long fatorial(Integer numero) {
    Long resultado = 1L;

    for (int fator = 2; fator <= numero; fator++) {
      resultado = resultado * fator;
    }

    return resultado;
  }
}