Last active
October 26, 2017 00:47
-
-
Save Bambina-zz/bc4a4fff7c856d28882847a35c9927c8 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment