Перебор размещений без повторений

[kas]

Здравствуйте.
Нужна помощь. Необходим алгоритм получения следующего размещения без повторений из текущего.
Пока всё, что я смог найти это или размещения с повторениями, или упоминание о том, что "рассмотрение этих вопросов оставим читателю в качестве полезного упражнения", но я сходу не могу сообразить. Буду благодарен за помощь или за указание источника, где этот вопрос хорошо освещен

[maxal]

Алгоритм генерации размещений из $n$ по $k$ можно представить в виде композиции двух: генерация сочетаний $n$ и $k$, и для каждого сочетания генерация всех $k!$ перестановок его элементов.
См. раздел II в Matters Computational.

[kiyanyn]

Вдруг кому пригодится :)
Делал максимально обобщенно, в духе STL, проверял на Open Watcom C++.
(с)

template< typename Bidirectional, typename Compare >
bool prev_kpermutation( Bidirectional first, Bidirectional middle,
                        Bidirectional last, Compare comp )
{

    typedef typename std::iterator_traits< Bidirectional >::difference_type Int;

    if( first == last ) return false;
    Int n = std::distance(first, last);
    Int k = std::distance(first, middle);
    if ((k > n) || (k <= 0)) return false;

    Bidirectional i = last;
    for(Bidirectional j = middle; j-- != first; )
    {
        if (std::min_element(j,last,comp) != j) { i = j; break; }
    }

    if (i == last) return false;
    Bidirectional j = i;
    ++j;
    while(!comp(*j,*i)) ++j;
    Bidirectional imin = j;
    for(; j != last; ++j)
    {
        if (comp(*j,*i) &&
                comp(*imin,*j))
        {
            imin = j;
        }
    }
    std::swap( *i, *imin );
    ++i;

    Bidirectional u = first;
    std::advance(u,std::min(k,n-1));
    while ( i != u )
    {
        Bidirectional imin = i;
        for(Bidirectional j = i; ++j != last;)
        {
            if (comp(*imin,*j)) imin = j;
        }
        std::swap( *imin,*i );
        ++i;
    }

    return true;
}

template< typename Bidirectional >
bool prev_kpermutation( Bidirectional first, Bidirectional middle, Bidirectional last )
{
    return ( prev_kpermutation( first, middle, last,
                                std::less< typename std::iterator_traits< Bidirectional >::value_type >( )
                              ) );
}



template< typename Bidirectional, typename Compare >
bool next_kpermutation( Bidirectional first, Bidirectional middle,
                        Bidirectional last, Compare comp )
{

    typedef typename std::iterator_traits< Bidirectional >::difference_type Int;

    if( first == last ) return false;
    Int n = std::distance(first, last);
    Int k = std::distance(first, middle);
    if ((k > n) || (k <= 0)) return false;

    Bidirectional i = last;
    for(Bidirectional j = middle; j-- != first; )
    if (std::max_element(j,last,comp) != j) { i = j; break; }

    if (i == last) return false;


    Bidirectional j = i;
    ++j;
    while(!comp(*i,*j)) ++j;
    Bidirectional imin = j;
    for(; j != last; ++j)
    {
        if (comp(*i,*j) &&
                comp(*j,*imin))
        {
            imin = j;
        }
    }
    std::swap( *i, *imin );
    ++i;

    Bidirectional u = first;
    std::advance(u,std::min(k,n-1));
    while ( i != u )
    {
        Bidirectional imin = i;
        for(Bidirectional j = i; ++j != last;)
        {
            if (comp(*j,*imin)) imin = j;
        }
        std::swap( *i, *imin );
        ++i;
    }

    return true;
}

template< typename Bidirectional >
bool next_kpermutation( Bidirectional first, Bidirectional middle, Bidirectional last )
{
    return ( next_kpermutation( first, middle, last,
                                std::less< typename std::iterator_traits< Bidirectional >::value_type >( )
                              ) );
}