CareerCup

Don't lie: that's your combinatorics homework.

Brute force recursion? And ignore the ones that violate the conditions? Anyone think of anything better? Brute force is definitely exponntial

Wow, difficult question.

C(26,10)*(9+8+7+6+5+4+3+2+1)

eww

1) Its not homework lol
2) We need to write a program, not compute it manually
3) Oshin I dont think thats right, how did you get it?

Shouldnt it be P(26,10) in place of C(26,10)?

No.We are not interested in all the permutations, only the ones which are according to the problem. By P, we would be selecting 10 numbers out of 26 & then rearranging them as well, which is wrong.

After selecting a set of 10 characters from 26 characters , arrange them in decreasing order , then select any 2 ( out of 10 ) and swap them .

It should be C(26,10) * C(10,2)

I concur the answer C(26, 10) * 9. Plus if you swap two non-adjacent positions, it is really hard to guarantee condition 4.

An example to support my solution :
say the length is 5 & alphabets selected are a,b,c,d,e

then, valid arrangements :

decba,dceba,dcbea,dcbae (floating e)
ecdba,ecbda,ecbad (floating d)
edbca,edbac (floating c)
edcab (floating b)

easy problem think in terms of dynamic programming :)

I think the solution is 26C10 * (9+8+7+6...+1)

this is because we can have 26C10 combinations of 10 chars in the alphabet, each combination having a descending order to start with. say, j i h g f e d c b a

Now for condition 4, we can move j to 9 other places except its correct place in descending order. for each of those permutations, all others need to stay in place.
So for each combination, 9 permutations with the first letter floating.

similarly, letter i can float in 9 places, but one such combination is already covered when j floated, so with I floating, we have another 8 permutations in this combination.

now with H floating , we have 9 permutations, one of which was covered by floating j, one covered by floating i. so 7 more permutations.
thus we have 9 + 8 + 7 + .. + 1 permutations per combination

hence 26C10 * (9+8+7+..+1) total strings

Number of possible different different strings = 26*25*24* ... 17 / 10! = C(26,10)
Given a string, let it be ordered, we can break the order in only 1 point only swapping two adjacent position, there are 9 different possible swap.
C(26,10)*9

I wrote some python to print all the strings. It could be easily modified to print the number (although this would be an inefficient way to solve just the number).

#!/usr/bin/env python


def ord_permute(length):
    alphabet = 'abcdefghijklmnopqrstuvwxyz'
    helper(length, alphabet, '')


def helper(length, to_permute, has_permuted):
    if len(has_permuted) is length:
        if verify(has_permuted):
            print has_permuted
        return

    for i, char in enumerate(to_permute):
        has_temp = has_permuted + char
        to_temp = to_permute[:i] + to_permute[(i+1):]
        helper(length, to_temp, has_temp)

def verify(string):
    flag = False
    for i in range(len(string) - 1):
        if ord(string[i]) > ord(string[i+1]):
            if not flag:
                flag = True
            elif flag:
                return False
    return flag

pastebin (for some syntax highlighting):
pastebin DOT com/viDqBcjc

Select 10 alphabets from the 26. This can be done in C(26,10)
Now there is 1 combination in which all are in decreasing order.
For example : j i h g f e d c b a

Obviously the above order is invalid.
Now, In order for the above combination to be valid think of all the ways in which you can permute the alphabets.

Starting from left to right, j can be floated at 9 different places.
Eg:

i J h g f e d c b a
i h J g f e d c b a
i h g J f e d c b a
i h g f J e d c b a...

so on


Similarly, i can be floated at 8 different places, and so on.

Hence, C(26,10)*(9+8+...+1)