请教高手们一个遍历的算法，大家帮帮忙

Question

题目如下：有N个状态S1, s2, ...Sn， 然后有一个含有T个元素的观测序列O1, O2, ...OT，其中O1, O2, ...OT中每个元素只能够娶到那N个状态中的一个，可以重复，求遍历所有的可能O1, O2, ...OT序列？例如：
有2个状态S1, s2， 一个含有3个元素的观测序列O1, O2， 03的输出结果是：
s1 s1 s1    s1 s1 s2     s1 s2 s1    s1 s2 s2     
s2 s1 s1    s2 s1 s2    s2 s2 s1     s2 s2 s2，
遍历总数是状态个数的T次方大家帮帮忙，有什么好建议，用什么算法实现啊？
谢谢了

Answer 1

例如： 
有2个状态S1, s2， 一个含有3个元素的观测序列O1, O2， 03的输出结果是： 
s1 s1 s1    s1 s1 s2    s1 s2 s1    s1 s2 s2    
s2 s1 s1    s2 s1 s2    s2 s2 s1    s2 s2 s2， 就好比是建树，
每个节点两个叶子S1，S2，
一共三层O1，O2,O3
这样说明白了么

Answer 2

namespace ConsoleApplication3
{
    class Program
    {
        const int NumOfOb = 3;
        static int nNo = 1;
        static string[] sState = {"s1", "s2"};
        static string[] sObState = new string[NumOfOb];        static void SetObState(int nInObPos)
        {
            if (nInObPos >= NumOfOb)
            {
                DispResult();
                return;
            }            for (int i = 0; i < 2; i++)
            {
                sObState[nInObPos] = sState[i];
                SetObState(nInObPos + 1);
            }
        }        static void DispResult()
        {
            string sOut;            sOut = nNo.ToString() +": ";            for (int i = 0; i < NumOfOb - 1; i++)
            {
                sOut = sOut + sObState[i] + ',';
            }            sOut = sOut + sObState[NumOfOb - 1];            nNo = nNo + 1;
            Console.WriteLine(sOut);
        }        static void Main(string[] args)
        {
            SetObState(0);
            Console.Read();
        }
    }
}
更多状态和ob，自己改改了，随便写的，没有仔细检查

Answer 3

输出结果
1: s1,s1,s1
2: s1,s1,s2
3: s1,s2,s1
4: s1,s2,s2
5: s2,s1,s1
6: s2,s1,s2
7: s2,s2,s1
8: s2,s2,s2