CareerCup

Math problem.... cool...

I did two examples fully to get used to the problem,

1) Drawing from set S = {1, 2, 3, 4} sequences of length 2. Answer was 10.
2) Drawing from set S = {1, 2, 3, 4} sequences of length 3. Answer was 20.

I did both above manually (try it) but it's fast as you see a pattern.

I can see 10 and 20 come from Pascal's triangle in a neat way.

Let N be the size of S (number of characters in alphabet, whatever)
Let n be length of sequence.

Number we want is (N+n-1) choose (n).

Omitted the proof I did to verify this (think of "bars and stars").

So write an function to essentially find Pascal's triangle values bottom up DP style until it reaches N+n-1 choose n , then return that.


===============

Nevermind, the problem was much easier... find all the sequences :P (printing them).
This gives us the excuse not to find a counting formula.

C:

#include <stdio.h>
// all this will be calculated at compile time (efficient)
#define FIRST_CHAR 'a'
#define ALPH_SIZE 26  
#define PAST_LIMIT (FIRST_CHAR + ALPH_SIZE) //1 past last char

#define SEQ_LEN 3           

char result[SEQ_LEN +1];  //let's make it global for change

void print_them()
{
    static i=0;   //position of result[] current invocation fills
    int p;

    if(i==SEQ_LEN) { puts(result); return; }  //seq. full, print

    p = (i==0) ? FIRST_CHAR : result[i-1];  //grab previous char

    while(p < PAST_LIMIT)  //iterate forward from prev. char
    {
        result[i++] = p++;    
        print_them(i) , i--;  //fill next then unwind i
    }
}

int main(void)
{
    print_them();
    return 0;
}

Keeping local variables + parameters to a minimum will help prevent the hardware stack from blowing up if you are dealing with longer sequences.

A solution in C#:

public static void PrintWords(int n)
		{
			DoPrintWords(n, 0, string.Empty);
		}

		private static void DoPrintWords(int n, int start, string s)
		{
			for (int i = start; i < 26; i++)
			{
				s += (char) ('A' + i);
				if (s.Length == n)
					Console.WriteLine(s);
				else
					DoPrintWords(n, i, s);

				s = s.Substring(0, s.Length - 1);
			}
		}

C++ program to generate valid words for any length

#include<iostream>
#include<string>

using namespace std;

void print(string s, int i, int n, int len);

char alphabets[]={'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u','v', 'w', 'x', 'y', 'z'};

int main()
{
        string s;
        int n;
        cin>>n;
        print(s, 0, n, 0);
        return 0;
}


void print(string s, int i, int n, int len)
{
        if(len==n)
        {
                cout<<s<<endl;
                return;
        }
        for(int j=i; j<26; j++)
        {
                print(s+alphabets[j], j, n, len+1);
        }
}

Is the question correct (might be typo)? If we need to find out the words with length n in string of n length then always only one string is possible. I guess, the question is find all words with length m (m <= n), then more words are possible in output. Please clarify.

/* //Call as 
* int 	n = 3;
* PrintValidWords("", 'a', n);
*/
const char EndChar = 'z';
    // Append charCount number of valid charaters to prefix
static private void PrintValidWords(String prefix, char start, int charCount)
{
	String newPrefix;
	if ((0 == charCount) || (null == prefix) || (start > EndChar))
	{
		return;
	}

	for (char c = start; c <= EndChar; c++)
	{
		newPrefix = prefix + c.ToString();
		if (1 == charCount)
		{
			Console.WriteLine(newPrefix);
		}
		else
		{
			PrintValidWords(newPrefix, c, charCount - 1);
		}
	}
}

count(int position, int last_char)
{
int counter =0;
// if position is last return - z-last_char +1
if (position == last)
{
return 'z'-last_char +1;
}
position++;

while(last_char <= 'z')
{
counter += count(position, last_char);
last_char++;
}
return counter;
}
// usage = a.out last // where last is length of string
main
{
char last_char = 'a';
last = atoi(argv[1]);
counter =count(1,last_char);
printf("total number of possible words of length %d is %d\n", last, counter);
return;
}

it should be 26^(n-1)+25^(n-1)+24^(n-1)+.......+1
reason :-
if first letter is 'a',then other can be from a-z thus 26 options for rest of n-1 blocks,,,
if first letter is 'b' ... 25 choices,,,if its c,then 24 choices and so on ...