Algorithm to represent a sequence of numbers

Question

I have a sequence of numbers to generate, and I want to generate it using some sort of algorithm (iterative or recursive, doesn't matter).

Contextualizing: This numbers are indexes to iterative over a list of lists. I need to do a permutation (combination, i don't know exactly), but I need to generate all combinations of all positions of that list of lists.

The sequence and the output I am trying to get is:

and so on... the last state is:

Note that at each line break is a step of iteration or recursion. The algorithm must be generic. This code that i wrote can help, but it isn't what I want. :(

List<List<int>> lstDays = new List<List<int>>
{
    new List<int>{1,2,3,4,5}, //day 18
    new List<int>{1,2,3,4,5}, //day 19
    new List<int>{1,2,3,4,5}, //day 22
    new List<int>{1,2,3,4,5}, //day 23
    new List<int>{1,2,3,4,5}, //day 24
};

for(int i=0;i<lstDays.Count;i++)
{
    for(int j=0;j<lstDays[i].Count;j++)
    {
        for(int k=0;k<lstDays.Count;k++)
        {
            Console.Write(k+1);

            //Console.Write(j+1);

            Console.Write('\n');
        }
        Console.Write('\n');
    }
}

I hope that you can help me ! (:

What do you want if this code works? What output do you expect... — rene, Aug 25 '13 at 14:31
The code must output the numbers that I showed, on that order. — richardaum, Aug 25 '13 at 14:32
It is generally better if you use arrays instead of lists here. — ismellike, Aug 25 '13 at 14:42
Hm... Why? I think that is the same thing. At least on C#. But I used a list of lists because I have another kind of object inside. I used int here just for simplicity. — richardaum, Aug 25 '13 at 14:43

score 2 · Answer 1 · answered Aug 25 '13 at 14:41

You can do it like this:

int[] second = new[] {0,0,0,0,0};
bool finish = false;
while (true) {
    for (int i = 0 ; i != 5 ; i++) {
        Console.WriteLine("{0} {1}", i+1, second[i]+1);
    }
    Console.WriteLine();
    int p = 0;
    do {
        second[p]++;
        if (second[p] == 5) {
            second[p] = 0;
            p++;
        } else {
            break;
        }
    } while (p != 5);
    if (p == 5) break;
}

The sequence of the second digits is stored in the array "creatively" named second. The do/while loop "increments" this array as if it were a base-5 number stored as five separate digits.

Here is a demo on ideone.

I am thinking that your code is what I need (: I am testing it now! :DD — richardaum, Aug 25 '13 at 15:00

score 1 · Accepted Answer · edited May 23 '17 at 10:32

Based on comments below by the venerable Eric Lippert, edits for the OPs original intent:

public void OutputSequence(int length){
    Recurse(length-1, Enumerable.Range(1, length).ToArray(), new int[length]);  
}

public void Recurse(int position, int[] arr, int[] state){  
    if (position == -1){
        PrintState(state);  
        return;
    }

    for (int i = 0; i < arr.Length; i++)
    {           
        state[position] = arr[i];
        Recurse(position-1, arr, state);
    }
}

public void PrintState(int[] state){
    for (int i = 0; i < state.Length; i++)
        Console.WriteLine ("{0} {1}",i+1, state[i]);        

        Console.WriteLine ();
}

OutputSequence(5); will give the output the OP originally asked for.

Old Answer

What you're looking for is called a Cartesian Product. LINQ is your friend:

var pairs = from i in Enumerable.Range(1, 5)
            from j in Enumerable.Range(1, 5)
            select new {i, j};

foreach(var p in pairs)
    Console.WriteLine ("{0} {1}", p.i, p.j);

EDIT: Just for fun, here's a way to do N-Ary cartesian products.

public IEnumerable<IEnumerable<int>> NAryCartesianProduct(int upper, int times){
    if (times == 0)
        return Enumerable.Empty<IEnumerable<int>>();

    var nums = Enumerable.Range(1, upper);          
    IEnumerable<IEnumerable<int>> products = nums.Select(i => new[]{i});

    for (int i = 1; i < times; i++)
    {
        products = from p in products
                   from n in nums
                   select p.Concat(new [] {n});                                     
    }       

    return products;
}

And now you can get what you had before with:

var p = NAryCartesianProduct(5, 2);

foreach(var i in p)
    Console.WriteLine (i);

I'm sure there's a more efficient way than creating new arrays all of the time but I just hacked this up quick :)

Here's a much more informative answer on this: Generating all Possible Combinations

EDIT2: Apparently the original link is the origination of the answer from that SO post. I didn't read through to the end until now.

I choose your answer as the best because you sent me the idea of Cartesian product. Although I have tagged this question as C#, I am using Python. So, you helped me a lot (: TNX — richardaum, Aug 25 '13 at 15:12
Though the original poster seems to like it, the question as asked doesn't match the Cartesian product at all. — Eric Lippert, Aug 25 '13 at 22:51
@EricLippert I re-read the question, as well as dasblinkenlight's solution: how is his expected output not the cartesian product of {1,2,3,4,5} on itself? — DavidN, Aug 26 '13 at 00:31
The Cartesian product would be 11, 21, 31, 41, 51, 12, 22, 32, 42, 52, 13, 23, 33, 43, 53, 14, 24, 34, 44, 54, 15, 25, 35, 45, 55. The sequence given in the original posting is 11, 21, 31, 41, 51, 12, 21, 31, 41, 51, 13, 21, 31, 41, 51, 14, 21, 31, 41, 51, 15, 21, 31, 41, 51, 12, 22, 31, 41, 51... which is a completely different sequence. — Eric Lippert, Aug 26 '13 at 07:33
You're absolutely correct, can't believe I missed that (guess the mind sees what it wants to see, and I did have some fun with the question). I'll edit it to reflect the change, or perhaps just remove it outright. — DavidN, Aug 26 '13 at 15:49

Algorithm to represent a sequence of numbers

2 Answers2