빠르게 순열 구하기

빠르게 순열 구하기

ettolrach 작성, 2025-08-17.

최근에 permutations 함수를 사용하는 하스켈 프로그램을 작성하고 있었다. 재미로 코드를 러스트로 옮기고 싶었는데, 러스트 표준 라이브러리에는 그런 함수가 없다는 걸 깨달았다. 흔히 러스트 프로그램에서 쓰이는 기능도 아니고, 특히 비-지연(non-lazy) 버전은 작은 리스트에서만 동작하니 그런 결정은 이해가 된다.

그래도 직접 작성해 보고 싶었다. 그래서 면접 준비에서 한 번쯤 봤을 법한 고전 알고리즘으로 구현하기로 했다. 리스트의 각 원소를 하나씩 잡아두고 나머지를 순열로 만든다. 그리고 각 순열마다, 아까 잡아둔 원소를 앞(또는 뒤)에 붙인다. 종이에 리스트의 모든 순열을 손으로 적으라고 하면 아마 이런 식으로 할 것이다.

rust
fn permutations_recurse<X: Clone>(xs: impl IntoIterator<Item = X>) -> Option<Vec<Vec<X>>> {
    fn go<X: Clone>(v: Vec<X>) -> Vec<Vec<X>> {
        if v.len() == 0 {
            return Vec::new();
        }
        if v.len() == 1 {
            return vec![v];
        }
        let mut to_return = Vec::new();
        for i in 0..v.len() {
            let mut remaining = v.clone();
            _ = remaining.remove(i);
            let perms = go(remaining);
            // 잡아둔 원소를 끝에 붙인다.
            // 앞에 붙이든 뒤에 붙이든 상관없고, 결과 벡터의 순서만 달라진다.
            to_return.extend(perms.into_iter().map(|mut perm| {
                perm.push(v[i].clone());
                perm
            }));
        }
        to_return
    }

    let v: Vec<X> = xs.into_iter().collect();
    if v.len() > 12 {
        None
    } else {
        Some(go(v))
    }
}

하지만 이것만이 유일한 방법은 아니다. 팩토리얼 진법을 사용할 수 있다. 이는 각 자리값 n 이 n! 을 나타내는 진법(기수)으로, 이진법에서 각 자리값 n 이 2^n 을 나타내는 것과 비슷하다. 이 표현을 어떤 수의 팩토라딕(factoradic) 이라고 부르며, 아래 알고리즘으로 계산할 수 있다. 결과 벡터는 왼쪽에서 오른쪽으로 읽을 때 역순이며, 0번째 원소가 0번째 자리값이다.

rust
fn factoradic(n: u64) -> Vec<u64> {
    let mut to_return = Vec::new();
    let mut place_value = 1;
    let mut dividend = n;
    while dividend != 0 {
        to_return.push(dividend % place_value);
        dividend /= place_value;
        place_value += 1;
    }
    to_return
}

// 효율을 위해, 벡터를 미리 할당해 두는 버전.
fn padded_factoradic(n: u64, v: &mut [u64]) {
    let mut place_value: usize = 1;
    let mut dividend = n;
    while dividend != 0 {
        // 128비트 머신에서 돌고 있지 않다고 가정.
        v[place_value - 1] = dividend % (place_value as u64);
        dividend /= place_value as u64;
        place_value += 1;
    }
}

n번째 순열은, n의 팩토라딕을 계산한 다음 n의 각 자리값 k(가장 작은 자리부터 시작)를 보고 원래 리스트에서 k번째 원소를 제거해 출력 리스트에 추가하면 얻을 수 있다. 이 방법의 장점은 이터레이터로 작성할 수 있다는 것이다.

rust
fn factorial(n: usize) -> Option<usize> {
    // 12까지(12 포함) 하드코딩하고, n >= 13이면 `None`을 반환한다.
}

struct Permutations<X: Clone> {
    v: Vec<X>,
    current: usize,
    largest_fac: usize,
}

impl<X: Clone> Permutations<X> {
    fn new(v: Vec<X>) -> Option<Self> {
        let largest_fac = factorial(v.len())?;
        Some(Self {
            v,
            current: 0,
            largest_fac,
        })
    }
}

impl<X: Clone> Iterator for Permutations<X> {
    type Item = Vec<X>;

    fn next(&mut self) -> Option<Self::Item> {
        if self.current >= self.largest_fac {
            return None;
        }

        let mut n_factoriadic = vec![0; self.v.len()];
        let mut elems = self.v.clone();
        let mut to_return = Vec::with_capacity(self.v.len());

        padded_factoradic(self.current as u64, &mut n_factoriadic);

        for index in n_factoriadic.into_iter().rev() {
            to_return.push(elems.remove(index as usize));
        }

        self.current += 1;
        Some(to_return)
    }
}

fn permutations<X: Clone>(
    xs: impl IntoIterator<Item = X>,
) -> Option<impl Iterator<Item = Vec<X>>> {
    Permutations::new(xs.into_iter().collect())
}

처음에는 재귀 해법이 더 빠를 거라고 생각했다. 나눗셈이나 나머지 연산을 할 필요가 없으니까. 하지만 성능을 이야기할 때는 실제로 측정해야 한다. 결국 순진하게 보면 둘 다 리스트 길이를 l이라 했을 때 O(l!) 집합 안에 들어가기 때문이다. 그래서 Criterion.rs를 사용해 길이 8짜리 작은 리스트와 길이 10짜리 리스트를 측정했다(8! = 40320이지만 10! = 3628800이다). 매번 리스트는 동일했으며, ['A', 'B', 'C' ...] 같은 글자들로 이루어진 Vec<char>였다.

100회 반복 후 위 알고리즘들의 성능

내가 틀렸다! 재귀 해법이 더 빠르지 않았다.

또 다른 생각은 멀티스레딩을 해보는 것이다. 팩토라딕마다 새 스레드를 만드는 건 스레드 생성 오버헤드 때문에 별 도움이 안 될 테지만, 스레드 2개를 만들고 한 스레드에 팩토라딕의 절반을, 다른 스레드에 나머지 절반을 맡기면 어떨까?

rust
use std::{sync::mpsc, thread};

fn permutations_multithreaded<X: Clone + Send + 'static>(xs: impl IntoIterator<Item = X>) -> Option<Vec<Vec<X>>> {
    let v: Vec<X> = xs.into_iter().collect();
    let len = v.len();
    let fac_len = factorial(len)?;
    let (tx1, rx) = mpsc::channel();
    let tx2 = tx1.clone();

    {
        let elems = v.clone();
        thread::spawn(move || {
            let mut to_return: Vec<Vec<X>> = Vec::with_capacity(fac_len / 2);
            for n in 0..(fac_len / 2) {
                let mut this_elems = elems.clone();
                let mut n_factoradic = vec![0; len];
                padded_factoradic(n as u64, &mut n_factoradic);
                to_return.push(
                    n_factoradic
                        .into_iter()
                        .rev()
                        .map(|index| this_elems.remove(index as usize))
                        .collect(),
                );
            }
            tx1.send(to_return).unwrap();
        });
    }

    {
        let elems = v.clone();
        thread::spawn(move || {
            let mut to_return: Vec<Vec<X>> = Vec::with_capacity(fac_len / 2);
            for n in (fac_len / 2)..fac_len {
                let mut this_elems = elems.clone();
                let mut n_factoradic = vec![0; len];
                padded_factoradic(n as u64, &mut n_factoradic);
                to_return.push(
                    n_factoradic
                        .into_iter()
                        .rev()
                        .map(|index| this_elems.remove(index as usize))
                        .collect(),
                );
            }
            tx2.send(to_return).unwrap();
        });
    }

    Some(rx.iter().flatten().collect())
}

100회 반복 후 위 알고리즘들의 성능

또 한 번, 더 느렸다는 사실에 놀랐다! 아주 큰 리스트에서도 스레드 오버헤드가 여전히 너무 큰 것 같다.

하지만 내가 가장 놀란 건 이 팩토라딕 방식이 얼마나 빠른지였다. 나중에 순열을 계산해야 할 일이 생기면 꼭 기억해 둬야겠다.

---

덧붙여서, 하스켈은 어떻게 하고 있을까? 코드는 첫눈에 꽤 난해하다.

haskell
permutations :: [a] -> [[a]]
permutations xs0 = xs0 : perms xs0 []
 where
  -- | @perms ts is@ is equivalent to
  --
  -- > concat
  -- > [ interleave {(ts!!n)} {(drop (n+1) ts)} xs []
  -- > | n <- [0..length ts - 1]
  -- > , xs <- permutations (reverse (take n ts) ++ is)
  -- > ]
  --
  -- @{(ts!!n)}@ and @{(drop (n+1) ts)}@ denote the values of variables @t@ and @ts@
  -- when they appear free in the definition of @interleave@ and @interleave'@.
  perms :: forall a. [a] -> [a] -> [[a]]
  perms [] _ = []
  perms (t:ts) is = foldr interleave (perms ts (t:is)) (permutations is)
   where
    -- @interleave {t} {ts} xs r@ is equivalent to
    --
    -- > [ insertAt n t xs ++ ts | n <- [0..length xs - 1] ] ++ r
    --
    -- where
    --
    -- > insertAt n y xs = take n xs ++ y : drop n xs
    --
    interleave :: [a] -> [[a]] -> [[a]]
    interleave xs r = let (_,zs) = interleave' id xs r in zs
    -- @interleave' {t} {ts} f ys r@ is equivalent to
    --
    -- > ( ys ++ ts
    -- > , [ f (insertAt n t ys ++ ts) | n <- [0..length ys - 1] ] ++ r
    -- > )
    --
    interleave' :: ([a] -> b) -> [a] -> [b] -> ([a], [b])
    interleave' _ [] r = (ts, r)
    interleave' f (y:ys) r = let (us,zs) = interleave' (f . (y:)) ys r
                             in (y:us, f (t:y:us) : zs)

하지만 전체 소스 코드가 지적하듯이, 이 함수에 대한 훌륭한 해설이 Twan van Laarhoven이 작성한 Stack Overflow 답변에 있다. 목표는 지연성을 최대화하는 것이다. 하스켈 같은 언어에서는 이 함수가 러스트보다 훨씬 더 자주 쓰이기 때문이다. 그 Stack Overflow 답변을 읽어보길 강력히 추천한다. 시간을 들일 가치가 있는 정말 영리한 알고리즘이다.

---

댓글

서로 예의를 지켜 주세요. 부적절하다고 판단되는 댓글은 삭제됩니다. 댓글을 제출하면 개인정보 처리방침에 동의하는 것으로 간주합니다.

아직 댓글이 없습니다.