1

I am given an input, "N", i have to find the number of list of length N, which starts with 1, such that the next number to be added is at most 1 more than the max number added till now. For Example,

N = 3, possible lists => (111, 112, 121, 122, 123), [113, or 131 is not possible as while adding '3' to the list, the maximum number present in the list would be '1', thus we can add only 1 or 2].

N = 4, the list 1213 is possible as while adding 3, the maximum number in the list is '2', thus 3 can be added.

Problem is to count the number of such lists possible for a given input "N".

My code is :- 

public static void Main(string[] args)
        {
            var noOfTestCases = Convert.ToInt32(Console.ReadLine());
            var listOfOutput = new List<long>();
            for (int i = 0; i < noOfTestCases; i++)
            {
                var requiredSize = Convert.ToInt64(Console.ReadLine());
                long result;
                const long listCount = 1;
                const long listMaxTillNow = 1;
                if (requiredSize < 3)
                    result = requiredSize;
                else
                {
                    SeqCount.Add(requiredSize, 0);
                    AddElementToList(requiredSize, listCount, listMaxTillNow);
                    result = SeqCount[requiredSize];
                }
                listOfOutput.Add(result);
            }
            foreach (var i in listOfOutput)
            {
                Console.WriteLine(i);
            }
        }

        private static Dictionary<long, long> SeqCount = new Dictionary<long, long>();

        private static void AddElementToList(long requiredSize, long listCount, long listMaxTillNow)
        {
            if (listCount == requiredSize)
            {
                SeqCount[requiredSize] = SeqCount[requiredSize] + 1;
                return;
            }
            var listMaxTillNowNew = listMaxTillNow + 1;
            for(var i = listMaxTillNowNew; i > 0; i--)
            {
                AddElementToList(requiredSize, listCount + 1,
                    i == listMaxTillNowNew ? listMaxTillNowNew : listMaxTillNow);
            }
            return;
        }

Which is the brute force method. I wish to know what might be the best algorithm for the problem? PS : I only wish to know the number of such lists, so i am sure creating all the list won't be required. (The way i am doing in the code) I am not at all good in algorithms, so please excuse for the long question.

Improve this question
8
  • 2
    Is this a homework? Is the text you posted exactly the question? I ask because I don't properly understand the question, and if it is homework, you might post the exact question. Commented Apr 7, 2012 at 19:47
  • No its not a homework, its just a puzzle a friend asked me, If you have some doubts about the question, please ask, may be i can clarify. Commented Apr 7, 2012 at 19:50
  • Okay - is 111 a list of three values, or is it just one number? Commented Apr 7, 2012 at 19:51
  • That is a list, all those are examples of valid list for the input length of 3. Thus, for input = 3, there are 5 different lists that are possible. Commented Apr 7, 2012 at 19:53
  • 1
    You want to compute the nth Bell number. oeis.org/A000110 Commented Apr 7, 2012 at 19:59

2 Answers 2

Reset to default
3

This problem is a classic example of a dynamic programming problem:

If you define a function dp(k, m) to be the number of lists of length k for which the maximum number is m, then you have a recurrence relation:

dp(1, 1) = 1
dp(1, m) = 0, for m > 1
dp(k, m) = dp(k-1, m) * m + dp(k-1, m-1)

Indeed, there is only one list of length 1 and its maximum element is 1. When you are building a list of length k with max element m, you can take any of the (k-1)-lists with max = m and append 1 or 2 or .... or m. Or you can take a (k-1)-list with max element m-1 and append m. If you take a (k-1)-list with max element less than m-1 then by your rule you can't get a max of m by appending just one element.

You can compute dp(k,m) for all k = 1,...,N and m = 1,...,N+1 using dynamic programming in O(N^2) and then the answer to your question would be

dp(N,1) + dp(N,2) + ... + dp(N,N+1)

Thus the algorithm is O(N^2).

See below for the implementation of dp calculation in C#:

        int[] arr = new int[N + 2];
        for (int m = 1; m < N + 2; m++)
            arr[m] = 0;
        arr[1] = 1;

        int[] newArr = new int[N + 2];
        int[] tmp;
        for (int k = 1; k < N; k++)
        {
            for (int m = 1; m < N + 2; m++)
                newArr[m] = arr[m] * m + arr[m - 1];
            tmp = arr;
            arr = newArr;
            newArr = tmp;
        }

        int answer = 0;strong text
        for (int m = 1; m < N + 2; m++)
            answer += arr[m];

        Console.WriteLine("The answer for " + N + " is " + answer);
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

This surely gives the correct answer, thanks for the code, but is it possible to do this with a lesser complexity. O(n) may be.
I don't think you can go below O(n^2). The problem is that in order to determine what are the possible values for k-th element you need to know the maximum value within the first k-1. And since there are k possibilities you need to sum k different numbers. To reach N you need to do this N times - so quadratic is the best you can hope for.
0

Well, I got interrupted by a fire this afternoon (really!) but FWIW, here's my contribution:

    /*
     * Counts the number of possible integer list on langth N, with the
     * property that no integer in a list(starting with one) may be more
     * than one greater than the greatest integer preceeding it in the list.
     * 
     * I am calling this "Semi-Factorial" since it  is somewhat similar to
     * the factorial function and its constituent integer combinations.
     */
    public int SemiFactorial(int N)
    {
        int sumCounts = 0;

        // get a list of the counts of all valid lists of length N,
        //whose maximum integer is listCounts[maxInt].
        List<int> listCounts = SemiFactorialCounts(N);

        for (int maxInt = 1; maxInt <= N; maxInt++)
        {
            // Get the number of lists, of length N-1 whose maximum integer
            //is (maxInt):
            int maxIntCnt = listCounts[maxInt];

            // just sum them up
            sumCounts += maxIntCnt;
        }

        return sumCounts;
    }

    // Returns a list of the counts of all valid lists of length N, and
    //whose maximum integer is [i], where [i] is also its index in this
    //returned list. (0 is not used).
    public List<int> SemiFactorialCounts(int N)
    {
        List<int> cnts;
        if (N == 0)
        {
            // no valid lists, 
            cnts = new List<int>();
            // (zero isn't used)
            cnts.Add(0);
        }
        else if (N == 1)
            {
                // the only valid list is {1}, 
                cnts = new List<int>();
                // (zero isn't used)
                cnts.Add(0);
                //so that's one list of length 1
                cnts.Add(1);
            }
            else
            {
            // start with the maxInt counts of lists whose length is N-1:
            cnts = SemiFactorialCounts(N - 1);

            // add an entry for (N)
            cnts.Add(0);

            // (reverse order because we overwrite the list using values
            // from the next lower index.)
            for (int K = N; K > 0; K--) 
            {
                // The number of lists of length N and maxInt K { SF(N,K) }
                // Equals K times # of lists one shorter, but same maxInt,
                // Plus, the number of lists one shorter with maxInt-1.
                cnts[K] = K * cnts[K] + cnts[K - 1];
            }
        }

        return cnts;
    }

pretty similar to the others. Though I wouldn't call this "classic dynamic programming" so much as just "classic recursion".

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.