Permutations of an integer disregarding the zeros on the left

Question

I have the following problem:

Given an input n I have to calculate the number of possible permutations 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 entrance 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 arrived at 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 that? Remembering that performance is important and that, therefore, just perform the exchanges to have all the possibilities is not interesting. The resolution is more complete by applying the discount in the formula or after the calculation of the formula.

---

Examples:

• Entree: 1213. Exit: 12.
• Entree: 123. Exit: 6.
• Entree: 100. Exit: 1.
• Entree: 120. Exit: 4.
• Entree: 1200. Exit: 6.
• Entree: 0. Exit: 1.

Answer 1

The formulas below have been removed from here.

---

Given any number, and considering:

• to_i is the number of times the digit i occurs in this number (therefore 0 <= i <= 9)
  • Ex: in paragraph 644, the value of to₄ is equal to 2 (there are 2 digits 4 in the number) and to₆ is equal to 1 (all other to_i - for i other than 4 and 6 - equal to zero)
• n is the number of digits of the number, that is, the sum of all the to_i:
  to₀ + to₁ + ... + to₉ = n

The total number of possible permutations (including those with zeros at the beginning) is:

n! / (a₀! * a₁! * a₂! * ... * a₉!)

If the number has no zero (ie, to₀ is equal to zero), so the value above is already the answer.

But if there is some zero in the number, then we can put one of them at the beginning, leaving to₀ - 1 zeros in the rest of the number (that is, simply rearrange the remaining digits to know the quantity). Therefore, the amount of permutations that have a zero at the beginning would be:

(n - 1)! / ((a₀ - 1)! * a₁! * a₂! * ... * a₉!)

So, if there are zeros, just make the first formula above minus the second, we will have the result. If there is no zero, the first formula is already the answer. In Java it would look like this:

public int solucao(int n) {
    int[] quantidades = new int[10];
    int nDigits = 0;
    while (n > 0) {
        nDigits++;
        quantidades[n % 10]++;
        n /= 10;
    }

    // multiplica os fatoriais de a1 até a9
    int d = 1;
    for (int i = 1; i < quantidades.length; i++) {
        d *= fatorial(quantidades[i]);
    }

    // total de permutações
    int totalPerms = fatorial(nDigits) / (d * fatorial(quantidades[0]));
    if (quantidades[0] == 0) { // não tem zeros
        return totalPerms;
    }
    // descontar as permutações que começam com zero
    return totalPerms - (fatorial(nDigits - 1) / (d * fatorial(quantidades[0] - 1)));
}

As I am computing the number of digits from zero to 9, I saved these values in an array of int even with 10 positions (zero element is the number of zeros, in position 1 is the number of 1, etc). In addition to being simpler, it also avoids the use of Wrappers.

The method fatorial is the same as you already have (although it would be possible to improve this with memoisation, is the suggestion). And could also change all int's to long's, if you go to work with very large numbers, in which the factorial breaks the limits of a int.

---

Another alternative is to consider, in addition to the above definitions:

• bn(n, k): formula of Newton binomial, that is to say, bn(n, k) is equal to n! / k! (n - k)! (whereas n! is the factor of n)

We have to total possible permutations, disregarding the zeroes at the beginning, is:

bn(n - 1, a₀) * bn(n - a₀, a₁) * bn(n - a₀ - a₁, a₂) * ... * bn(a₉, a₉)

The idea is similar: if you set a zero at the beginning, all other digits (whether zero or not) can be placed later. The above formula makes this "discount", and can also be generalized to:

bn(n - 1, a₀) * ( (n - a₀)! / (a₁! * a₂! * ... * a₉!) )

In Java would stay:

public int solucao(int n) {
    int[] quantidades = new int[10];
    int nDigits = 0;
    while (n > 0) {
        nDigits++;
        quantidades[n % 10]++;
        n /= 10;
    }
    int d = 1;
    for (int i = 1; i < quantidades.length; i++) {
        d *= this.fatorial(quantidades[i]);
    }
    return bn(nDigits - 1, quantidades[0]) * (this.fatorial(nDigits - quantidades[0]) / d);
}

private int bn(int n, int k) {
    return this.fatorial(n) / (this.fatorial(k) * this.fatorial(n - k));
}

Answer 2

I was able to arrive at a calculated result the proportion in which the number zero appears and discounting from the permutation 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;
  }
}