순열, 조합 - Permutation, Combination

순열(Permutation)과 조합(Combination)은 쉽게 보이지만 실제 코드를 작성하려면 꽤 까다롭다.

Euler 문제 중에 조합을 사용해야 할 코드가 마침 있어, 이 기회에 정리해 본다.

 

	순서 고려 (순서가 다르면 다른 것)	중복 허용
순열	O	X
중복 순열	O	O
조합	X	X
중복 조합	X	O

---

1. 순열(Permutation)

nPr은 n개 중에 r을 뽑고, r에 대해 순서를 바꿔가며 나열하는 가짓수를 말한다.

 

공식은 $nPr = n! / (n-r)!$

 

{a, b, c}에 대해서 2개를 뽑는 순열은 6가지이고, 뽑힌 경우의 수는 아래와 같다.

$$ ab, ac, ba, bc, ca, cb$$

$$ _3P_2 = 3! / (3-2)! = 3! = 3 \cdot 2 = 6$$

 

---

순열의 가짓수를 구하는 것은 nPr 공식에 의해서 쉽게 구할 수 있으나, 순열로 이루어지는 경우의 수를 모두 구하는 것을 코드로 짜는 것은 꽤 어렵다. 

크게 2가지 구현 방법이 있다. 

하나는 재귀호출을 이용하는 방법이고, 다른 하나는 스택을 이용하는 것.

 

1.1 순열의 구현 - 재귀 호출 이용

nPr에 대해 구현을 한다고 하면, r개의 방에다가 n개 중의 하나씩을 넣는다고 상상해 보자.

 

예를 들어 {a, b, c}에 대해, 2개씩 뽑아내는 순열의 경우, 

• 2개의 방을 생각하자. 1번 방과 2번 방
• 1번 방에는 {a, b, c} 중 하나를 넣을 수 있다.
• 2번 방에는 {a, b, c}중에서, 1번 방에서 사용한 것을 제외한 2개 중 하나를 넣을 수 있다.

위 개념을 구현하는 것은, 그래프 이론에서 DFS(Deapth Frist Search)의 개념과 유사하다.

 

위 그림을 설명하면,

• {a, b, c}에서 각각의 원소를 하나의 노드로 생각하고, 각 단계마다 모든 노드를 방문한다고 생각하자.
• 처음 depth=0에서 시작해서(d=0), d=2일 때까지만 노드 깊이를 내려갈 것이다. 왜냐면 r=2이니깐. d=1일 때가 1번 방에 해당하고, d=2일 때까 2번 방에 대한 처리를 할 것이다.
• ① d=1일 때 방 1(여기서는 buffer 배열 b로 표현)에 {a, b, c}중 하나를 넣는다. 가장 먼저 들어가는 것은 'a'에 해당하는 인덱스 0이다. b[0]=0
• ② d=2로 갈 때 방 2에, 방 1에서 넣은 값 'a'를 제외한 나머지 {'b', 'c'}중 하나를 넣는다. 처음 들어가는 것은 'b'에 해당하는 인덱스 1. b[1]=1
• d==2가 되었을 때는, 방 1과 방 2에 들어간 값을 출력한다. 즉, b 배열에 있는 값을 출력하면 되는데, 이때 b={0,1}이기에 "ab"가 출력된다.
• ③ 그다음에 다시 방 2에 대한 처리가 이루어진다. DFS기 때문에, 제일 밑에 있는 노드로 갔으면 그다음은 그 바로 위에 있는 노드로 가는 것이다. 즉, 방 1에는 b[0]=0이 고정된 상태에서 b[1]={1,2}가 들어가게 되는 것 

이를 코드로 구현하면 다음과 같다.

#[test]
fn test(){
    let input = vec!["a","b","c","d"];
    
    let mut output:Vec<String> = Vec::new();
    let mut buf:Vec<usize> = vec![0; input.len()];
    let mut used:Vec<bool> = vec![false; input.len()];
    
    permu(0, input.len(),2, &input, &mut output, &mut buf, &mut used);
    println!("{:?}",output);
} 

#[cfg(test)]
//permutation: {a,b,c} -> ab ac ba bc ca cb 
fn permu<'a>(d:usize, n:usize, r:usize, input:&Vec<&'a str>, output:&mut Vec<String>, 
            buf:&mut Vec<usize>, used:&mut Vec<bool>){
    if d==r {
        let mut s:String = String::from("");
        for i in 0..r{ s.push_str(input[buf[i]]); }            
        output.push(s);
        return;
    }
    for i in 0..n {
        if used[i] {continue;}
        buf[d] = i;
        used[i] = true;
        permu(d+1, n,r,input,output,buf,used);
        used[i] = false;
    }
}

 

주요 코드만을 설명하면,

• d==r일 때는, r개의 방에 해당하는 buf에 있는 값들을 출력한다.
• 모든 노드에 대해서 n개의 원소를 모두 방문하는 것이기에 for루프의 i의 값은 0..n 이다.
• for 루프에서,
  • if used[i] {continue;}  //이미 방문한 노드라면 해당 노드는 방에 넣을 수 없다. 이미 방문한 노드인지는 used 배열을 사용
  • buf[d] = i ;  //방에 노드값을 넣는 구문이다. 방번호는 depth와 같음
  • used[i] = true; //사용된 노드(방에 넣은 노드)는 다시 사용되지 않게 used 처리
  • permu(d+1,...); //그다음 depth를 방문
  • used[i] = false; //used[0]=true를 하고 나서, 그 밑에 있는 depth 전부를 돌고 나서는, 다시 used[0]=false로해줘야한다. 만약 이것을 안 해주면, used[0]=true가 유지된 채로 제일 위에 있는 depth로 가게 되고, 따라서 'a'에 대한 노드는 방문하지 않게 되어, 제대로 permutation이 이루어지지 않는다.

1.2 순열의 구현 - 스택 이용

스택(Stack)을 이용하는 것은 재귀호출을 이용하는 것보다 이해하기가 좀 더 어렵다.

 

그렇지만, 아래와 같이 생각해 보면, 재귀호출과 스택을 이용하는 것이 동일한 개념이라는 것을 알 수 있을 것이다.

• 재귀호출을 한다는 것은, 자기 자신이 되는 함수를 호출하는 것
• 함수를 호출한다는 것은, 그 이전까지의 변수 값들을 스택에 저장해 놓고, 함수루틴으로 가고, 해당 함수에서는 자기 자신의 스택을 다시 만들어서 어떤 작업을 하고, 작업이 끝나면 이전 호출된 곳으로 돌아오는 것이다.
• 따라서, 어떤 값을 스택에 저장하고, 어떤 연산을 하고(이전 재귀호출에서 수행하는 연산), 그 연산이 끝났을 때 다시 스택에 있는 값을 복원해서 사용하면, 재귀호출을 하는 것이나 똑같은 효과가 되는 것임

DFS에서는 parent의 정보를 유지하면서 그 아래의 노드를 방문하게 된다. 

따라서, 스택에 저장해야 할 값은 부모의 정보이고, 이때 부모의 정보는 (depth, value)가 되겠다.

 

프로그램 구현은, 다음과 같이 생각해 본다.

• 스택에 depth=0일 때의 모든 노드값을 넣는다. 방문할 노드가 3개라면 [(0,0), (0,1), (0,2)]를 스택에 push
• 스택에 값이 있을 경우 While 루프를 돌면서,
  • 스택에 있는 노드 값 하나를 pop 한다.
  • 이 노드값 (d,v)를 이용해서, buf[d]=v로 저장해 둔다. 즉, d번 방에 값 v를 저장하는 것임
  • 만약 d==(r-1)로, r개의 노드에 다 도달했으면 buf 값을 프린트한다.
  • v값을 다시 방문하지 않기 위해서 used[v]=true로 하고, for 루프로 모든 노드를 방문한다.
  • for 루프에서는, used[v]가 false의 값에 대해서 스택에 집어넣는다. 이때 depth를 하나 증가하면서 스택에 push
  • for 루프 바깥에서는 used[v]=false로 해준다. 

위 개념을 그림으로 나타내면 아래와 같다. 3P2를 구할 때를 가정한 그림이다.

 

① 처음에 depth=0일 때의 노드값 3개를 모두 스택에 넣는다. 나중에 출력될 때 "ab" "ac"... 와 같이 인덱스 작은 것부터 출력되도록 하기 위해, 스택에 넣을 때 큰 값인 (0,2)부터 넣었다.

$$ Stack = [(0,2), (0,1), (0,0)]$$

 

② 이제 스택에서 하나를 꺼내면 (0,0)이 pop 될 것이다. 이 (0,0)의 하위에 있는 3개를 for 루프를 돌면서 push 하는데, depth=0에서의 값인 0을 제외한 {1,2} 값이 스택에 push 된다. 따라서 스택값은,

$$ [(0,2), (0,1), (1,2), (1,1)]$$

 

③ 다시 스택에서 하나를 빼내면 (1,1)이 되고, 이때 d==1이기에 프린트를 한다. 즉, value값인 {0,1}에 해당하는 "ab"가 출력될 것이다.

 

위와 같은 로직으로 짠 것이 아래 코드이다.

#[test]
fn test(){
    // let input = vec!["a","b","c","d"];
    let input = vec!["a","b","c"];
    
    let mut output:Vec<String> = Vec::new();
    let mut buf:Vec<usize> = vec![0; input.len()];
    let mut used:Vec<bool> = vec![false; input.len()];
    permu_stack(input.len(),2, &input, &mut output);
    println!("{:?}",output);

} 

#[cfg(test)]
//["ab", "ac", "ba", "bc", "ca", "cb"]
fn permu_stack(n:usize, r:usize, input:&Vec<&str>,output:&mut Vec<String>){
    let mut s:Vec<(usize,usize)> = Vec::new(); // (depth,node)
    let mut buf:Vec<usize> = vec![0; input.len()];
    let mut used:Vec<bool> = vec![false; input.len()];
   
    //push all of nodes as depth=0
    for i in (0..n).rev() { s.push((0,i)); }   

    while s.len() > 0 {
        let node = s.pop().unwrap(); // (depth, value)       
        let d = node.0;  let v = node.1;
        buf[d] = v; 
        if d == (r-1) {
            let mut s:String = String::from("");
            for i in 0..r{ s.push_str(input[buf[i]]); }            
            output.push(s);            
            continue;
        }

        used[v] = true;
        for i in (0..n).rev(){
            if used[i] {continue;}            
            s.push((d+1, i));                        
        }
        used[v] = false;
    }
}

 

1.3 중복 순열

순열은 중복을 허용하지 않는다. 

중복을 허용하지 않는다는것은, {a,b,c}에서 2개를 뽑는 경우, "aa" 같은 것을 허용하지 않는다는 것이다.

 

중복을 허용하는 순열의 구현은, 순열을 구현한 코드에서 used에 의한 체크를 안 하면 된다. 간단하다.

 

먼저 recursion을 이용한 순열의 코드에서 used 부분을 없애면 중복 순열이 된다. 방 1에서 사용한 원소를 중복 사용하지 않기 위해 used라는 것을 가지고 체크했었는데, 이것을 없애면 되는 것이다. 

아래코드에서 위 쪽이 일반 순열이고, 그 아래 있는 dup_permu_recursion이 중복허용 순열코드이다. 

#[cfg(test)]
//1. permutation with recursion: {a,b,c} -> ab ac ba bc ca cb 
//순서고려:O, 중복허용:X
//nPr = n! / (n-r)!
fn permu_recursion<'a>(d:usize, n:usize, r:usize, input:&Vec<&'a str>, output:&mut Vec<String>, 
            buf:&mut Vec<usize>, used:&mut Vec<bool>){
    if d==r {
        let mut s:String = String::from("");
        for i in 0..r{ s.push_str(input[buf[i]]); }            
        output.push(s);
        return;
    }
    for i in 0..n {
        if used[i] {continue;}
        buf[d] = i;   used[i] = true;
        permu_recursion(d+1, n,r,input,output,buf,used);
        used[i] = false;
    }
} 

#[cfg(test)]
//3. duplicated permutation with recursion: {a,b,c} -> aa ab ac ba bb bc ca cb cc
//순서고려:O, 중복허용:O
fn dup_permu_recursion<'a>(d:usize, n:usize, r:usize, input:&Vec<&'a str>, output:&mut Vec<String>, buf:&mut Vec<usize>){
    if d==r {
        let mut s:String = String::from("");
        for i in 0..r{ s.push_str(input[buf[i]]); }            
        output.push(s);
        return;
    }
    for i in 0..n {
        buf[d] = i;
        dup_permu_recursion(d+1, n,r,input,output,buf);
    }
}

 

 

스택을 사용한 순열코드에서, 중복허용 순열 구현도, used 부분을 없애면 된다.

아래 코드에 보면, used 부분 사용된 곳을 주석처리했다. 이렇게 하면 중복순열이 된다.

#[cfg(test)]
//2. permutation with stack: ["ab", "ac", "ba", "bc", "ca", "cb"]
fn dup_permu_stack(n:usize, r:usize, input:&Vec<&str>,output:&mut Vec<String>){
    let mut s:Vec<(usize,usize)> = Vec::new(); // (depth,node)
    let mut buf:Vec<usize> = vec![0; input.len()];
    // let mut used:Vec<bool> = vec![false; input.len()];
   
    //push all of nodes as depth=0
    for i in (0..n).rev() { s.push((0,i)); }   

    while s.len() > 0 {
        let node = s.pop().unwrap(); // (depth, value)       
        let d = node.0;  let v = node.1;
        buf[d] = v; 
        if d == (r-1) {
            let mut s:String = String::from("");
            for i in 0..r{ s.push_str(input[buf[i]]); }            
            output.push(s);            
            continue;
        }

        // used[v] = true;
        for i in (0..n).rev(){
            // if used[i] {continue;}            
            s.push((d+1, i));                        
        }
        // used[v] = false;
    }
}

---

2. 조합 (Combination)

조합은 순서의 다름을 인정하지 않는다. 즉, "ab"와 "ba"는 같은 것이다.

 

조합의 개수를 구하는 공식은,

$$ nCr = \frac {n!}{(n-r)!r!}$$

 

{a,b,c}에 대해 2개씩 조합하면 [ab, ab, bc] 가 된다.

 

---

2.1 조합의 구현 - 재귀 호출 이용

조합을 구현하는 것은, 순열을 구현했었으면, 순열 코드에서 약간의 변경을 해서 조합을 구현할 수 있다.

순열 코드에서는, 아래 코드와 같이, 모든 원소에 대해 for 루프를 돌렸었다.

    for i in 0..n {
        if used[i] {continue;}
        buf[d] = i;   used[i] = true;
        permu_recursion(d+1, n,r,input,output,buf,used);
        used[i] = false;
    }

 

조합(Combination)에서는 순서의 다름을 인정하지 않기에, 예를 들어, 'a'에 대해서 "ab" "ac"가 이미 만들어졌으면, 'b'에 대해서는 "ba"가 만들어지지 않게 하면 된다. 즉, for 루프에서 i의 시작을 그 이전 방에서 사용한 인덱스보다 하나 큰 인덱스부터 시작하게 하면 되겠다.

    for i in next..n {
        if used[i] {continue;}
        buf[d] = i;   used[i] = true;
        combi_recursion(d+1, i+1, n,r,input,output,buf, used);
        used[i] = false;
    }

위 코드에서 next 부분이 더 추가된 파라미터이다.

 

조합을 재귀호출로 구현한 전체 코드는,

#[cfg(test)]
//combination: {a,b,c} -> ab ac bc  
//순서고려:X, 중복허용:X
//nCr = n! / (n-r)!r!
fn combi_recursion<'a>(d:usize, next:usize, n:usize, r:usize, input:&Vec<&'a str>, output:&mut Vec<String>, 
            buf:&mut Vec<usize>, used:&mut Vec<bool>){
    if d==r {
        let mut s:String = String::from("");
        for i in 0..r{ s.push_str(input[buf[i]]); }            
        output.push(s);
        return;
    }
    for i in next..n {
        if used[i] {continue;}
        buf[d] = i;   used[i] = true;
        combi_recursion(d+1, i+1, n,r,input,output,buf, used);
        used[i] = false;
    }
}

 

2.2 조합의 구현 - 스택 이용

위 재귀호출을 구현한 아이디어와 동일하게, 스택을 이용한 순열 코드에서, for 루프에서 i의 시작 부분만을 윗 세대의 인덱스 값인 v보다 1 큰 값으로 바꿔주면 되겠다.

        used[v] = true;
        for i in ((v+1)..n).rev(){
            if used[i] {continue;}            
            s.push((d+1, i));                        
        }
        used[v] = false;

 

전체 코드는,

#[cfg(test)]
//["ab", "ac", "bc"] 
fn combi_stack(n:usize, r:usize, input:&Vec<&str>,output:&mut Vec<String>){
    let mut s:Vec<(usize,usize)> = Vec::new(); // (depth,node)
    let mut buf:Vec<usize> = vec![0; input.len()];
    let mut used:Vec<bool> = vec![false; input.len()];
   
    //push all of nodes as depth=0
    for i in (0..n).rev() { s.push((0,i)); }   

    while s.len() > 0 {
        let node = s.pop().unwrap(); // (depth, value)       
        let d = node.0;  let v = node.1;
        buf[d] = v; 
        if d == (r-1) {
            let mut s:String = String::from("");
            for i in 0..r{ s.push_str(input[buf[i]]); }            
            output.push(s);            
            continue;
        }

        used[v] = true;
        for i in ((v+1)..n).rev(){
            if used[i] {continue;}            
            s.push((d+1, i));                        
        }
        used[v] = false;
    }
}

 

 

2.3 중복 조합

{a, b, c}에서 중복 조합으로 2개를 뽑으면 [aa, ab, ac, bb, bc, cc]와 같이 된다.

 

중복 조합을 구현하는 것도, 순열에서 중복순열을 구할 때의 원리와 동일하다.

조합(Combination)을 구현한 코드에서, used 부분만을 없애면 된다.

 

재귀호출을 이용한 중복조합 코드는,

#[cfg(test)]
//duplicated combination: {a,b,c} -> aa ab ac bb bc cc
//순서고려:X, 중복허용:O
fn dup_combi_recursion<'a>(d:usize, next:usize, n:usize, r:usize, input:&Vec<&'a str>, output:&mut Vec<String>, buf:&mut Vec<usize>){
    if d==r {
        let mut s:String = String::from("");
        for i in 0..r{ s.push_str(input[buf[i]]); }            
        output.push(s);
        return;
    }
    for i in next..n {
        buf[d] = i;
        dup_combi_recursion(d+1, i, n,r,input,output,buf);
    }
}

 

스택을 이용한 중복 코드에서는 used 부분을 없애는 것에 더해서, for 루프에서 i의 시작을 v+1이 아닌 v에서 시작해야 함에 유의.  윗 세대에서의 인덱스값인 v와 동일한 값으로 시작해야 "aa"와 같은 중복쌍이 가능하다.

#[cfg(test)]
//["aa", "ab", "ac", "bb","bc","cc"] 
fn dup_combi_stack(n:usize, r:usize, input:&Vec<&str>,output:&mut Vec<String>){
    let mut s:Vec<(usize,usize)> = Vec::new(); // (depth,node)
    let mut buf:Vec<usize> = vec![0; input.len()];
    // let mut used:Vec<bool> = vec![false; input.len()];
   
    //push all of nodes as depth=0
    for i in (0..n).rev() { s.push((0,i)); }   

    while s.len() > 0 {
        let node = s.pop().unwrap(); // (depth, value)       
        let d = node.0;  let v = node.1;
        buf[d] = v; 
        if d == (r-1) {
            let mut s:String = String::from("");
            for i in 0..r{ s.push_str(input[buf[i]]); }            
            output.push(s);            
            continue;
        }

        // used[v] = true;
        for i in (v..n).rev(){
            // if used[i] {continue;}            
            s.push((d+1, i));                        
        }
        // used[v] = false;
    }
}

 

---

위에서 사용된 전체 소스 코드

#[test]
fn test(){
    // let input = vec!["a","b","c","d"];
    let input = vec!["a","b","c"];
    
    //1. permutation with recursion
    let mut output:Vec<String> = Vec::new();
    let mut buf:Vec<usize> = vec![0; input.len()];
    let mut used:Vec<bool> = vec![false; input.len()];
    permu_recursion(0, input.len(),2, &input, &mut output, &mut buf, &mut used);
    println!("permu: {:?}",output);

    //2. permutation with stack
    let mut output:Vec<String> = Vec::new();   
    permu_stack(input.len(),2, &input, &mut output);
    println!("permu_stack: {:?}",output);

    //3. duplicated permutation with recursion
    let mut output:Vec<String> = Vec::new();
    let mut buf:Vec<usize> = vec![0; input.len()];
    dup_permu_recursion(0,input.len(),2,&input,&mut output,&mut buf);
    println!("dup_permu: {:?}",output);

    //4. duplicated permutation with stack
    let mut output:Vec<String> = Vec::new();   
    dup_permu_stack(input.len(),2, &input, &mut output);
    println!("dup_permu_stack: {:?}",output);

    //5. combination
    let mut output:Vec<String> = Vec::new();
    let mut buf:Vec<usize> = vec![0; input.len()];
    let mut used:Vec<bool> = vec![false; input.len()];
    combi_recursion(0, 0, input.len(),2, &input, &mut output, &mut buf, &mut used);
    println!("combi: {:?}",output);

    //6. combination with stack
    let mut output:Vec<String> = Vec::new();   
    combi_stack(input.len(),2, &input, &mut output);
    println!("combi_stack: {:?}",output);

    //7. duplicated combination with recursion
    let mut output:Vec<String> = Vec::new();
    let mut buf:Vec<usize> = vec![0; input.len()];   
    dup_combi_recursion(0, 0, input.len(),2, &input, &mut output, &mut buf);
    println!("dup_combi: {:?}",output);

    //8. duplocated combination with stack
    let mut output:Vec<String> = Vec::new();   
    dup_combi_stack(input.len(),2, &input, &mut output);
    println!("dup_combi_stack: {:?}",output);
} 

#[cfg(test)]
//1. permutation with recursion: {a,b,c} -> ab ac ba bc ca cb 
//순서고려:O, 중복허용:X
//nPr = n! / (n-r)!
fn permu_recursion<'a>(d:usize, n:usize, r:usize, input:&Vec<&'a str>, output:&mut Vec<String>, 
            buf:&mut Vec<usize>, used:&mut Vec<bool>){
    if d==r {
        let mut s:String = String::from("");
        for i in 0..r{ s.push_str(input[buf[i]]); }            
        output.push(s);
        return;
    }
    for i in 0..n {
        if used[i] {continue;}
        buf[d] = i;   used[i] = true;
        permu_recursion(d+1, n,r,input,output,buf,used);
        used[i] = false;
    }
} 

#[cfg(test)]
//2. permutation with stack: ["ab", "ac", "ba", "bc", "ca", "cb"]
fn permu_stack(n:usize, r:usize, input:&Vec<&str>,output:&mut Vec<String>){
    let mut s:Vec<(usize,usize)> = Vec::new(); // (depth,node)
    let mut buf:Vec<usize> = vec![0; input.len()];
    let mut used:Vec<bool> = vec![false; input.len()];
   
    //push all of nodes as depth=0
    for i in (0..n).rev() { s.push((0,i)); }   

    while s.len() > 0 {
        let node = s.pop().unwrap(); // (depth, value)       
        let d = node.0;  let v = node.1;
        buf[d] = v; 
        if d == (r-1) {
            let mut s:String = String::from("");
            for i in 0..r{ s.push_str(input[buf[i]]); }            
            output.push(s);            
            continue;
        }

        used[v] = true;
        for i in (0..n).rev(){
            if used[i] {continue;}            
            s.push((d+1, i));                        
        }
        used[v] = false;
    }
}

#[cfg(test)]
//3. duplicated permutation with recursion: {a,b,c} -> aa ab ac ba bb bc ca cb cc
//순서고려:O, 중복허용:O
fn dup_permu_recursion<'a>(d:usize, n:usize, r:usize, input:&Vec<&'a str>, output:&mut Vec<String>, buf:&mut Vec<usize>){
    if d==r {
        let mut s:String = String::from("");
        for i in 0..r{ s.push_str(input[buf[i]]); }            
        output.push(s);
        return;
    }
    for i in 0..n {
        buf[d] = i;
        dup_permu_recursion(d+1, n,r,input,output,buf);
    }
}

#[cfg(test)]
//2. permutation with stack: ["ab", "ac", "ba", "bc", "ca", "cb"]
fn dup_permu_stack(n:usize, r:usize, input:&Vec<&str>,output:&mut Vec<String>){
    let mut s:Vec<(usize,usize)> = Vec::new(); // (depth,node)
    let mut buf:Vec<usize> = vec![0; input.len()];
    // let mut used:Vec<bool> = vec![false; input.len()];
   
    //push all of nodes as depth=0
    for i in (0..n).rev() { s.push((0,i)); }   

    while s.len() > 0 {
        let node = s.pop().unwrap(); // (depth, value)       
        let d = node.0;  let v = node.1;
        buf[d] = v; 
        if d == (r-1) {
            let mut s:String = String::from("");
            for i in 0..r{ s.push_str(input[buf[i]]); }            
            output.push(s);            
            continue;
        }

        // used[v] = true;
        for i in (0..n).rev(){
            // if used[i] {continue;}            
            s.push((d+1, i));                        
        }
        // used[v] = false;
    }
}

#[cfg(test)]
//combination: {a,b,c} -> ab ac bc  
//순서고려:X, 중복허용:X
//nCr = n! / (n-r)!r!
fn combi_recursion<'a>(d:usize, next:usize, n:usize, r:usize, input:&Vec<&'a str>, output:&mut Vec<String>, 
            buf:&mut Vec<usize>, used:&mut Vec<bool>){
    if d==r {
        let mut s:String = String::from("");
        for i in 0..r{ s.push_str(input[buf[i]]); }            
        output.push(s);
        return;
    }
    for i in next..n {
        if used[i] {continue;}
        buf[d] = i;   used[i] = true;
        combi_recursion(d+1, i+1, n,r,input,output,buf, used);
        used[i] = false;
    }
} 

#[cfg(test)]
//["ab", "ac", "bc"] 
fn combi_stack(n:usize, r:usize, input:&Vec<&str>,output:&mut Vec<String>){
    let mut s:Vec<(usize,usize)> = Vec::new(); // (depth,node)
    let mut buf:Vec<usize> = vec![0; input.len()];
    let mut used:Vec<bool> = vec![false; input.len()];
   
    //push all of nodes as depth=0
    for i in (0..n).rev() { s.push((0,i)); }   

    while s.len() > 0 {
        let node = s.pop().unwrap(); // (depth, value)       
        let d = node.0;  let v = node.1;
        buf[d] = v; 
        if d == (r-1) {
            let mut s:String = String::from("");
            for i in 0..r{ s.push_str(input[buf[i]]); }            
            output.push(s);            
            continue;
        }

        used[v] = true;
        for i in ((v+1)..n).rev(){
            if used[i] {continue;}            
            s.push((d+1, i));                        
        }
        used[v] = false;
    }
}

#[cfg(test)]
//duplicated combination: {a,b,c} -> aa ab ac bb bc cc
//순서고려:X, 중복허용:O
fn dup_combi_recursion<'a>(d:usize, next:usize, n:usize, r:usize, input:&Vec<&'a str>, output:&mut Vec<String>, buf:&mut Vec<usize>){
    if d==r {
        let mut s:String = String::from("");
        for i in 0..r{ s.push_str(input[buf[i]]); }            
        output.push(s);
        return;
    }
    for i in next..n {
        buf[d] = i;
        dup_combi_recursion(d+1, i, n,r,input,output,buf);
    }
}

#[cfg(test)]
//["aa", "ab", "ac", "bb","bc","cc"] 
fn dup_combi_stack(n:usize, r:usize, input:&Vec<&str>,output:&mut Vec<String>){
    let mut s:Vec<(usize,usize)> = Vec::new(); // (depth,node)
    let mut buf:Vec<usize> = vec![0; input.len()];
    // let mut used:Vec<bool> = vec![false; input.len()];
   
    //push all of nodes as depth=0
    for i in (0..n).rev() { s.push((0,i)); }   

    while s.len() > 0 {
        let node = s.pop().unwrap(); // (depth, value)       
        let d = node.0;  let v = node.1;
        buf[d] = v; 
        if d == (r-1) {
            let mut s:String = String::from("");
            for i in 0..r{ s.push_str(input[buf[i]]); }            
            output.push(s);            
            continue;
        }

        // used[v] = true;
        for i in (v..n).rev(){
            // if used[i] {continue;}            
            s.push((d+1, i));                        
        }
        // used[v] = false;
    }
}

 

끝