PermTest.java

import java.util.*;
import org.junit.*;
import static org.junit.Assert.*;

public class PermTest {
  @Test
  public void testCountPermutation(){
    Perm p = new Perm(1);
    assertEquals(1, p.countPermutation());
  }

  @Test
  public void testCountPermutation1(){
    Perm p = new Perm(123);
    assertEquals(6, p.countPermutation());
  }

  @Test
  public void testCountPermutation2(){
    Perm p = new Perm(1230);
    assertEquals(18, p.countPermutation());
  }

  @Test
  public void testCountPermutation3(){
    Perm p = new Perm(1120);
    assertEquals(9, p.countPermutation());
  }

  @Test
  public void testCountPermutation4(){
    Perm p = new Perm(11200);
    assertEquals(18, p.countPermutation());
  }

// 1120 => 9
// 3!/2! * 3C1
// 3 * 3! / ((3-1)!*1!)
// 3 * 6 / (2!*1!) => 9
// 112: 1120 1102 1012
// 121: 1210 1201 1021
// 211: 2110 2101 2011

// 11200 => 18
// 3!/2! * 4C2
// 3!/2! * 4!/((4-2)!*2!)
// 3 * 24 / 4 => 18
// 112: 11200 11020 11002 10012 10102 10012
// 121: 1210 1201 1021
// 211: 2110 2101 2011

// x[xxxx] に 0が2個入るとき 00xx 0x0x 0xx0 x00x x0x0 xx00
// 4C2  4!/(4-2)!2! => 6通り

// 1-9が何種類あるか
// 1-9で重複している数は何回重複しているか
// 0はいくつあり、入る可能性のある桁は何桁あるか(全桁数-1)

  class Perm {
    private int n;
    private HashMap<Integer, Integer> factorialSheet = new HashMap<>();

    public Perm(int n){
      this.n = n;
    }

    public int countPermutation(){
      String str = Integer.toString(n);
      int numDigits = str.length();
      if(numDigits < 2) return 1;

      int[] table = new int[10];
      for(char c : str.toCharArray()){
        int i = c - '0';
        table[i] = table[i] + 1;
      }

      int numOf1to9 = 0;
      int divideBy = 1;
      for(int i=1; i< 10; i++){
        if(table[i] > 0){
          numOf1to9 += table[i];
          divideBy = divideBy * getFactorial(table[i]);
        }
      }

      int result = getFactorial(numOf1to9);
      int r = table[0];
      if(r > 0) {
        // nCr : n!/(n-r)!r!
        int n = numDigits - 1;
        result = result * getFactorial(n) / getFactorial(n-r) / getFactorial(r);
      }
      return result / divideBy;
    }

    private int getFactorial(int n){
      if(n == 1) return 1;
      if(factorialSheet.containsKey(n)) {
        return factorialSheet.get(n);
      }
      int ans = n * getFactorial(n-1);
      factorialSheet.put(n, ans);
      return ans;
    }
  }
}