write a function comb(A,n,k,p,lo) that prints all k out of n combinations of 0..

Question

write a function comb(A,n,k,p,lo) that prints all k out of n combinations of 0...n-1 in lexicographical order. The parameters p and lo represent the current location to be filled (p) and the first number to pick in that location (lo). The array A is used to create and store the current combination. The algorithm for enumerating combinations is discussed in lecture 17 Permutations. Implementation MUST be recursive.

comb.txt contains some skeleton code. Download it and rename it comb.py. A correct implementation of comb:

produces

Explanation / Answer

import sys

def comb(A,n,k,p,lo):
    #assign current element lowest value allowed
    A[p] = lo
    #if we are pointing to the last element of the array, print it
    if p == k-1:
        print(A)
    #if we aren't at the end of the array, increment the ptr
    if not(p == k-1):
        p = p + 1
    #if the lowest value is k-1, we cannot increment anymore, therefore no recurse
    if not(lo == n-1):
        #increment the lo value if we can
        lo = lo + 1
        #do a recursive call
        comb(A,n,k,p,lo)
        comb(A,n,k,p-1,lo)

if __name__ == "__main__":
    d = len(sys.argv)>3
    n = int(sys.argv[1])
    k = int(sys.argv[2])
    A = []
    for i in range(k):
        A.append(0)
    if d: print("n:",n,"k:",k)
    comb(A,n,k,0,0)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.