#___________________ recursive factorials _________________________________

#5.py

# We know that n! = n(n-1)(n-2)(n-3).......... 3.2.1. Let's compute it recursively.

def rFact(n):           # returns n!

    if (n ==1):
        return 1
    else:
        return(n*rFact(n-1))

#  Home-work: write the iterative version to check results


    # n! gives you the number of ways of permuting n objects.

# What if you wanted to (do combinations) select objects. How many ways are there of
# selecting k objects from n objects? This is nCk or (n,k) ..... and .......

# the answer is :   n! / (k! (n-k)!)

# so you see that to compute this, you need 3 factorials.


def Comb(n,k):     # number of ways of choosing k objects from n objects

    
    denom = rFact(k) * rFact(n-k)

    num = rFact(n)

    return ((num//denom))

#___________________________________Extra_________________________________________________________________

# ***** This is a difficult recursion to understand when you are new to recursion. So take all the time you
# need to understand it. You will NOT be tested you on this. *****

# Now supposing you had a string of n arbitrary objects .... let's say 'abcdefg'. How
# can we list out all combinations of k objects at a time? 

def combinations(string, k):   #want all size k combinations from n things

    outlist = [ ]              # start with empty list and build it recursively
    
    for j in range (len(string)):
        
        if (k == 1):
            outlist.append(string[j])   # if there's only one object, put it in the list
            print(outlist)

        # Next slice through the smaller sublist recursively, and concatenate the
        # new element to each sub arrangement

        for element in combinations(string[j+1: ], k-1):
                outlist.append(string[j] + element)
                print(outlist)

    return outlist                  

#HW:  Also read the example on anagrams (page 437) .... it is similar.


def main():

    print("Factorial   5 = ",rFact(5))
    print("Factorial 10 = ",rFact(10))

    print("Factorial 27 = ",rFact(27))

    print(" ")

    print("Number of ways of choosing two objects from ten objects = ",Comb(10,2))

    print(" ")

    result = combinations("ABCDEFGH",3)
    
    print("\n\n Result:", result)



main()