全ての組み合わせ in C++ DouKaku?

全ての組み合わせ

2個以上のリストlist1, list2, list3...が与えられたときに、その複数個のリストの中の要素を一つずつとりだして組にする方法の全通りのリストを返すコードを書いてください。

Pythonで表現すると下のようになります。

>>> c = CrossProduct([1,2,3,4], "abc")
>>> list(c.all())
[[1, 'a'], [1, 'b'], [1, 'c'], [2, 'a'],
 [2, 'b'], [2, 'c'], [3, 'a'], [3, 'b'],
 [3, 'c'], [4, 'a'], [4, 'b'], [4, 'c']]

>>> c = CrossProduct([0, 1], "ab", ["Foo", "Bar"])
>>> list(c.all())
[[0, 'a', 'Foo'], [0, 'a', 'Bar'], [0, 'b', 'Foo'], [0, 'b', 'Bar']
 [1, 'a', 'Foo'], [1, 'a', 'Bar'], [1, 'b', 'Foo'], [1, 'b', 'Bar']]

順番はこの通りでなくても構いません。返すものはリストと書きましたが、なんらかの「一度に全部をメモリ上に作成しないリスト状のモノ」がある言語ではそちらを使う方がおすすめです。数値や文字列を一つのリストに混在させるのがやっかいな言語では整数のリストに限定しても構いません。

このお題はZIGOROuさんとのやりとりにヒントを得て作りました。 (しまった、先にブログで公開されてしまった→Yet Another Hackadelic - 直積の導出と考えうる全ての値を網羅したハッシュの生成)

追記：サンプル出力が間違っていたのでoceanさんの解答を使って出力し直しました。

post comment

Posted feedbacks - C++

カバレッジ稼ぎ。よくわかりませんが、g++ではコンパイルできませんでした。bcc32とVC6で確認。

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>

template <typename T>
void combi_impl(
    std::vector<std::vector<T> >& ret,
    std::vector<T>& tmp,
    const std::vector<std::vector<T> >& src,
    size_t i)
{
    if (i == src.size())
    {
        ret.push_back(tmp);

        return;
    }

    std::vector<T>::const_iterator it;

    for (it = src[i].begin(); it != src[i].end(); ++it)
    {
        tmp[i] = *it;

        combi_impl(ret, tmp, src, i + 1);
    }
}

template <typename T>
std::vector<std::vector<T> > combi(const std::vector<std::vector<T> >& src)
{
    std::vector<std::vector<T> > ret;

    std::vector<T> tmp(src.size());

    combi_impl(ret, tmp, src, 0);

    return ret;
}

int main()
{
    std::vector<std::vector<int> > vectors;

#define PUSH(a) vectors.push_back(std::vector<int>(a, a + sizeof(a) / sizeof(*a)))

    const int a1[] = {1, 2, 3};    PUSH(a1);
    const int a2[] = {4, 5};       PUSH(a2);
    const int a3[] = {6, 7, 8, 9}; PUSH(a3);

#undef PUSH

    vectors = combi(vectors);

    std::vector<std::vector<int> >::const_iterator it;

    for (it = vectors.begin(); it != vectors.end(); ++it)
    {
        std::copy(it->begin(), it->end(), std::ostream_iterator<int>(std::cout, " "));

        std::cout << std::endl;
    }
}

DouKaku?

全ての組み合わせ

Posted feedbacks - C++

Index

Feed

Other

Link

Pathtraq