024. Lexicographic Permutations (사전식 조합에서 k번째 항목 구하기)

 

 

​문제 (English)

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

 

012 021 102 120 201 210

 

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

 

Answer: 2783915460

문제 분석

---

10개의 문자에 대해 사전식 조합을 했을 때, 백만 번째 조합에 해당하는 것은 무엇인지 구하는 문제.

 

n개에 대해 사전식 조합을 했을 때, 경우의 수는 n! 이다.

 

예를 들어 3개의 숫자 0,1,2를 가지고 조합을 해보면 아래와 같이 3! = 6개의 조합이 발생한다.

 

012 021 102 120 201 210

 

4개의 숫자 0,1,2,3을 가지고 조합을 하면 $4!=4 \times  3 \times 2 \times 1=24개$

 

0123 0132 0213 0231 0312 0321 1xxx ......

 

4개의 숫자에 대한 조합에 대해 좀 더 보면, 첫째 자리가 0으로 시작하는 것에 대해 3!=6개가 존재하고, 1로 시작하는 것에 대해서도 6개, 2에 대해서 6개, 3으로 시작하는것에 대해서 6개. 이렇게 앞자리 4종류에 대해서 각각 6개씩 해서 24개이다.

 

---

10개의 숫자에 대한 조합은 0..=9까지의 수로 조합을 만드는 것이다. 

위에서 예를 든 것과 마찬가지고 0으로 시작하는 것에 대해 9! 개가, 1로 시작하는 것에 대해 9! 개... 

이렇게 했을 때, 100만 번째는 어떤 조합일까를 구하는 문제이다.

 

풀이 1 

---

0..=9까지의 문자를 가지고, 첫 번째는 0123456789이고, 두 번째는 0123456798이고 하면서, 백만 번째까지 조합을 만들어서 풀 수도 있으나, 이렇게 하면 너무 느리다.

 

0..=3까지의 문자를 가지고서 조합을 해보면서, 효율적으로 문제를 풀 방법을 생각해 보자.

 

전체 조합수는 4!=24개이다. 

• 0으로 시작: 3! 개  -> 0123, 0132, 0213, 0231, 0312, 0321
• 1로 시작: 3!개
• 2로 시작: 3!개
• 3으로 시작: 3!개

이제 팩토리알 값을 보면 {1!, 2!, 3!,4!} = {1,2,6,28}

 

1~6번째까지는 0으로 시작하고, 7~12번째는 1로, 13~18번째는 2로, 19~24번째는 3으로 시작한다. 

규칙을 발견할 수 있다. 즉, n번째 조합에서 첫 번째 자리의 값은 arr[(n-1)/3!]이다. 여기서 arr={"0","1","2","3"}이다.

• 만약 n=1이면 arr[(0/6]=arr[0]="0" 
• 만약 n=5이면 arr[4/6]=arr[0]="0"
• 만약 n=6이면 arr[5/6]=arr[0]="0"
• 만약 n=7이면 arr[6/6]=arr[1]="1"

첫째 자리는 되었고, 이제 두 번째 자리에 지정되는 수에 대한 규칙을 찾아보자.

첫째 자리가 "1"이 되는 7~12번째에 대해서만 생각해 본다.

   

    [1123, 1132, 1213, 1231, 1312, 1321]

 

1~2번째는 두 번째 자리가 "1"

4~4번째는 두번째 자리가 "2"

5~6번째는 두번째 자리가 "3"

 

규칙이 있다. 

첫 번째 자리에서 사용한 (n-1)에 대해, (n-1)%6을 한 것을 다시 n으로 둔 상태에서,

첫번째 자리에서 사용한 "1"을 제외한 나머지 배열 arr={"1","2","3"}에 대해, arr[n/2!]이 두번째 자리 값이 된다.

 

예를 들어 9번째 자리를 구한다면, 

n=9 --> n=n-1=8

첫 번째 자리는 arr[8/6]=1 --> "1"

그리고 n = n % 6 = 8 % 6 = 2  --> 이 n=2에 대해 arr[2/2!]=1 --> 따라서 두 번째 자리는 "2" 

 

세 번째 자리 규칙은, 첫번째와 두번째 자리가 "12"의 경우를 생각해서 찾아보면,

 

  [1203, 1230]

 

1번째는 세번째 자리가 "0"

2번째는 세번째 자리가 "3"

 

세 번째 자리에 대한 규칙은, "1" "2"를 제외한 배열 arr={"0","3"}에서, arr[n/1]이 세번째 자리 값이 된다.

 

---

위에서 찾은 규칙을 좀 더 정교화해보자.

 

n번째를 찾는다면, n=n-1로 처리한다. 

첫 번째 자리는 arr[n/3!], 그리고 arr에서 해당 자릿수를 삭제 (즉, arr={"0","1","2","3"}에서, 만약 "1"을 첫째 자리로 사용했다면 arr={"0", "2", "3"}이 된다.)

 

이제 n=n % 3!로 놓고, 

두 번째 자리는 arr[n/2!], 다시 arr에서 사용된 문자를 삭제하고 세 번째 자리 구한다.

 

n = n % 2!

세번째 자리는 arr[n/1], arr에서 사용된 문자 삭제

 

n = n % 1 =

네 번째 자리는 arr[n/1] --> 이 때 arr에서 남아 있는 것은 한 개 원소밖에 없으니, 그 한개 남은 것이 선택됨

 

코드로 구현해 보면 다음과 같다.

 

 

#[cfg(test)]
// return nth permuation 
fn answer_study(mut n:usize) -> String{
    let fact = get_factorial_num(3); //[1, 1, 2, 6]
    let mut elements:Vec<&str> = vec!["0","1","2","3"];

    let mut ans = "".to_string();
    n -= 1;
    for i in (0..elements.len()).rev() {
        let t = n / fact[i];
        n %= fact[i];
        ans.push_str(elements[t]);
        elements.splice(t..t+1, vec![]);

        println!("t={}, n={}, ans={:?}, elements={:?}",t,n,ans,elements);        
    }
    return ans;
}

#[cfg(test)]
// n이하의 factorial number로된 벡터를 리턴. if n=3 -> [1,1,2,6]
fn get_factorial_num(n:usize) -> Vec<usize> {
    let mut v = vec![1,1];
    if n <= 1 {return v;}

    let mut f = 1;
    for i in 2..=n{
        f *= i;
        v.push(f);
    }    
    return v;
}

 

10개의 문자에 대한 처리도 동일하다. 아래가 코드.

#[cfg(test)]
// return nth permuation 
fn answer(mut n:usize) -> String{
    let fact = get_factorial_num(9); //[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
    let mut elements:Vec<&str> = vec!["0","1","2","3","4","5","6","7","8","9"];

    let mut ans = "".to_string();
    n -= 1;
    for i in (0..elements.len()).rev() {
        let t = n / fact[i];
        n %= fact[i];
        ans.push_str(elements[t]);
        elements.splice(t..t+1, vec![]);  
    }
    return ans;
}

 

개념적으로 얘기하면, 10진수로 n번째에 해당하는 조합을 찾으라는 것은, 십진수 n을 팩토리알 진수로 바꾸라는 것으로 생각할 수도 있다. 

예를 들어 10자리 문자에 대해서, 백만 번째 조합을 찾으라고 하면, 

• 첫 번째 자리를 제외한 나머지 9개자리에는 9!가지 경우의 수가 있으므로, n을 9!로 나눈 값을 이용해서 첫번째 자릿수를 결정할 수 있다. --> 이것은 진수를 변환할 때의 원리와 비슷
• 그리고, 두 번째 자리는, 첫째 자리가 결정되었으므로, 나머지 9! 내에서 첫 번째 자리를 결정하는 것이기에, 처음 수 n에 대해 n= n % 9!로 대체하고, 그 수 n에 대해 8!로 나눈 값을 이용해서 자릿수 결정

 

이처럼 팩토리알 수 [1,1,2,6, 24,120,720,5040, 40320,362880]를 가지고, 각 자릿수마다 이 팩토리알 수로 나누면서 어떤 값을 결정하게 되는데, 이는 어떤 수를 십진수로 바꾼다면 [1,10,100,1000,10000]으로 나누면서 값을 결정하는 것과 동일하다.

 

풀이 2 

---

hackerrank에서는 13개의 문자에 대해서 조합을 물어본다.

위 풀이 1과 다른 것은 단지 3개의 문자가 더 들어갔다는 것 밖에 없다.

 

use std::io::{self, BufRead};
fn main() {
    let stdin = io::stdin();
    let mut it = stdin.lock().lines();
    let t = it.next().unwrap().unwrap().trim().parse::<usize>().unwrap();
    for _ in 0..t {
        let n = it.next().unwrap().unwrap().trim().parse::<usize>().unwrap();
        println!("{}",answer1(n));
    }
}  

fn answer1(mut n:usize) -> String{
    let fact = get_factorial_num(12); //[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880,3628800,39916800,479001600]
    let mut elements:Vec<&str> = vec!["a","b","c","d","e","f","g","h","i","j","k","l","m"];

    let mut ans = "".to_string();
    n -= 1;
    for i in (0..elements.len()).rev() {
        let t = n / fact[i];
        n %= fact[i];
        ans.push_str(elements[t]);
        elements.splice(t..t+1, vec![]);  
    }
    return ans;
}

fn get_factorial_num(n:usize) -> Vec<usize> {
    let mut v = vec![1,1];
    if n <= 1 {return v;}

    let mut f = 1;
    for i in 2..=n{
        f *= i;
        v.push(f);
    }    
    return v;
}

 

총평

---

풀이 코드는 간단한데, 개념을 뽑아내기는 꽤 어렵다. 

조합을 뽑아낼 때, 첫째 자리는 어떻게 결정되며, 그다음 자리는 어떻게 결정되는지에 대한 깊은 이해가 필요하다.

 

전체 소스코드

---

p24.rs 

#[test]
fn test(){
    assert_eq!("0123", answer_study(1));
    assert_eq!("0132", answer_study(2));
    assert_eq!("0213", answer_study(3));
    assert_eq!("0231", answer_study(4));
    assert_eq!("1023", answer_study(7));

    assert_eq!("0123456789", answer(1));
    assert_eq!("0123456798", answer(2));
    assert_eq!("0123456879", answer(3));
    assert_eq!("0123456897", answer(4));
    assert_eq!("0123456978", answer(5));
    assert_eq!("0123456987", answer(6));
    assert_eq!("0123457689", answer(7));
    assert_eq!("0123457698", answer(8));
    assert_eq!("2783915460", answer(1000000));   
    
}

#[cfg(test)]
// return nth permuation 
fn answer(mut n:usize) -> String{
    let fact = get_factorial_num(9); //[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
    let mut elements:Vec<&str> = vec!["0","1","2","3","4","5","6","7","8","9"];

    let mut ans = "".to_string();
    n -= 1;
    for i in (0..elements.len()).rev() {
        let t = n / fact[i];
        n %= fact[i];
        ans.push_str(elements[t]);
        elements.splice(t..t+1, vec![]);  
    }
    return ans;
}

#[cfg(test)]
// return nth permuation 
fn answer_study(mut n:usize) -> String{
    let fact = get_factorial_num(3); //[1, 1, 2, 6]
    let mut elements:Vec<&str> = vec!["0","1","2","3"];

    let mut ans = "".to_string();
    n -= 1;
    for i in (0..elements.len()).rev() {
        let t = n / fact[i];
        n %= fact[i];
        ans.push_str(elements[t]);
        elements.splice(t..t+1, vec![]);

        println!("t={}, n={}, ans={:?}, elements={:?}",t,n,ans,elements);        
    }
    return ans;
}

#[cfg(test)]
// n이하의 factorial number로된 벡터를 리턴. if n=3 -> [1,1,2,6]
fn get_factorial_num(n:usize) -> Vec<usize> {
    let mut v = vec![1,1];
    if n <= 1 {return v;}

    let mut f = 1;
    for i in 2..=n{
        f *= i;
        v.push(f);
    }    
    return v;
}

//----------------------------
//hacker 문제
#[test]
fn test1(){
    assert_eq!("abcdefghijklm", answer1(1));
    assert_eq!("abcdefghijkml", answer1(2));
}

#[cfg(test)]
// return nth permuation 
fn answer1(mut n:usize) -> String{
    let fact = get_factorial_num(12); //[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880,3628800,39916800,479001600]
    let mut elements:Vec<&str> = vec!["a","b","c","d","e","f","g","h","i","j","k","l","m"];

    let mut ans = "".to_string();
    n -= 1;
    for i in (0..elements.len()).rev() {
        let t = n / fact[i];
        n %= fact[i];
        ans.push_str(elements[t]);
        elements.splice(t..t+1, vec![]);  
    }
    return ans;
}

 

끝