組み合わせ（combination）と部分列（subsequence）

備忘録。

• Combination - Wikipedia
• Subsequence - Wikipedia

C++で

vector以外でキチンと動作するか、まだ確かめてないです。

combination

#ifndef COMBINATION_H
#define COMBINATION_H

#include <vector>
#include <iterator>

template<typename iterator_t>
void combination(iterator_t begin, iterator_t end, std::size_t size,
    std::vector<std::vector<typename iterator_t::value_type> >& destination)
{
    if(size == std::distance(begin, end))
    {
        destination.push_back(std::vector<typename iterator_t::value_type>(begin, end));
    }
    else if(size == 1)
    {
        for(iterator_t i = begin; i != end; ++i)
        {
            destination.push_back(std::vector<typename iterator_t::value_type>(1, *i));
        }
    }
    else if(begin != end)
    {
        const typename iterator_t::value_type& a = *begin;
        ++begin;
        std::vector<std::vector<typename iterator_t::value_type> > sub;
        combination(begin, end, size - 1, sub);
        for(int i = 0; i < sub.size(); ++i)
        {
            sub[i].push_back(a);
            destination.push_back(sub[i]);
        }
        combination(begin, end, size, destination);
    }
}

#endif//COMBINATION_H

#include "combination.h"

#include <iostream>

int main(int, char* [])
{
    std::vector<int> source;
    for(int i = 0; i < 5; ++i)
    {
        source.push_back(i + 1);
    }

    std::vector<std::vector<int> > destination;

    combination(source.begin(), source.end(), 3, destination);

    for(std::vector<std::vector<int> >::iterator itr = destination.begin(); itr != destination.end(); ++itr)
    {
        for(int i = 0; i < itr->size(); ++i)
        {
            std::cout << (*itr)[i] << ' ';
        }
        std::cout << '\n';
    }

    return 0;
}

$ g++ -o combination combination.cpp; ./combination 
3 2 1 
4 2 1 
5 2 1 
4 3 1 
5 3 1 
4 5 1 
4 3 2 
5 3 2 
4 5 2 
3 4 5 

subsequence

#ifndef SUBSEQUENCE_H
#define SUBSEQUENCE_H

#include <vector>
#include <iterator>

template<typename iterator_t>
void subsequence(iterator_t begin, iterator_t end,
    std::vector<std::vector<typename iterator_t::value_type> >& destination)
{
    std::vector<std::vector<typename iterator_t::value_type> > result;
    result.push_back(std::vector<typename iterator_t::value_type>());
    for(iterator_t itr = begin; itr != end; ++itr)
    {
        int n = result.size();
        for(int i = 0; i < n; ++i)
        {
            result.push_back(result[i]);
            result.back().push_back(*itr);
        }
    }
    destination.swap(result);
}

#endif//SUBSEQUENCE_H

#include "subsequence.h"

#include <iostream>
#include <vector>

int main(int, char* [])
{
    std::vector<int> source;
    for(int i = 0; i < 4; ++i)
    {
        source.push_back(i + 1);
    }

    std::vector<std::vector<int> > destination;
    subsequence(source.begin(), source.end(), destination);

    for(std::vector<std::vector<int> >::iterator itr = destination.begin(); itr != destination.end(); ++itr)
    {
        for(int i = 0; i < itr->size(); ++i)
        {
            std::cout << (*itr)[i] << ' ';
        }
        std::cout << '\n';
    }

    return 0;
}

$ g++ -o subsequence subsequence.cpp; ./subsequence

1 
2 
1 2 
3 
1 3 
2 3 
1 2 3 
4 
1 4 
2 4 
1 2 4 
3 4 
1 3 4 
2 3 4 
1 2 3 4 

Rubyで

Rubyはcombinationをすでに持っている。

combination

$ irb
>> c = []; [1,2,3,4,5].combination(3){|i|c<<i}
=> [1, 2, 3, 4, 5]
>> c
=> [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]

subsequence

def subsequence a
  result = [[]]
  a.each do |i|
    result.size.times do |j|
      result.push(result[j].dup.push(i))
    end
  end
  result
end

$ irb
>> require 'subsequence.rb'
=> true
>> subsequence [1,2,3,4]
=> [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3], [4], [1, 4], [2, 4], [1, 2, 4], [3, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]]

Haskellで

Haskellはsubsequencesをすでに持っている（subsequencesと複数形になっていることに注意）。

combination

combination n xxs@(x:xs)
    | n == len             = [xxs]
    | n == 1               = [[x]|x<-xxs]
    | (1 < n) && (n < len) = foldr (\xs xss -> (x:xs):xss) (combination n xs) (combination (n - 1) xs)
    | otherwise            = []
    where
        len = length xxs

$ ghci
Prelude> :l combination.hs
[1 of 1] Compiling Main             ( combination.hs, interpreted )
Ok, modules loaded: Main.
*Main> combination 3 [1..5]
[[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]]

subsequence

$ ghci
Prelude> :m Data.List
Prelude Data.List> subsequences [1..4]
[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3],[4],[1,4],[2,4],[1,2,4],[3,4],[1,3,4],[2,3,4],[1,2,3,4]]