'''
Try online python:
  https://www.programiz.com/python-programming/online-compiler/
  https://replit.com/languages/python3
'''

# ----------------------------------------------------------------------------
#                              K-SUBSETS
# Task:
# Generate all k-subsets of a given set of items.
# Technical note: A set is represented as a list.
# ----------------------------------------------------------------------------

# 1. -------------------------------------------------------------------------
# Idea:
# The first item of the given set is either an element
# of each k-subset or it does not.
# Implementation:
# Divide the set mentally
# into the first item F and the rest of the list  RL.
# 1. Generate all subsets of size k in RL
# 2. Generate all subsets of size k-1 in RL,
#    prepended F to each generated subset
#    and append the subset the to the result of 1.

def k_subsets1( set, k ):

  if k == len( set ) :
    return [ set ]
  if k == 0 :
    return [[]]

  # all subsets without the first item
  result = k_subsets1( set[1:], k )

  # all subsets with with the first item:
  resWithout = k_subsets1( set[1:], k-1 )
  for subset in resWithout:
    result.append( [set[0]] + subset )

  return result

# 2. -------------------------------------------------------------------------
# Idea:
# For each item I in the set generate all subsets
# of size k-1 using only the elements to the right of I
# (with higher index in the list)
# and prepend I to each of the generated subsets.

def k_subsets2( set, k ):
  if k == 0:
    return [[]]
  if k == len(set) :
    return [set]

  result = []
  for i in range( len(set) ):
    smallerSubsets = k_subsets2( set[i+1:], k-1 )
    for subset in smallerSubsets:
      result.append( [set[i]] + subset )

  return result

# 3. -------------------------------------------------------------------------
# Idea:
# Collect the items of the subset in a single result list.
# Add one item to the result on each recursion level.
# The technical advantage of the idea is that no
# intermediate lists (results) are generated.

def k_subsets3a( set, k, i_start, result, depth ):

  if depth == k:
    print( result )
    return

  i_lastStart = len(set) - (k-depth)
  for i in range( i_start, i_lastStart+1 ):
    result[depth] = set[i]
    k_subsets3a( set, k, i+1, result, depth+1 )

# Fancy modification of 3a approach:
# Process lists from the end to the beginning,
# with decreasing remaining depth to simplify the code.
# No more strange index calculations! Cool, isn't it? :-)

def k_subsets3b( set, i_end, result, remainingDepth ):
  if remainingDepth < 0:   # note the zero!
    print( result )
    return

  for i in range( i_end, remainingDepth-1, -1 ):  # go backwards
    result[remainingDepth] = set[i]
    k_subsets3b( set, i-1, result, remainingDepth-1 )

# ----------------------------------------------------------------------------
#   M A I N    -   e x p e r i m e n t s
# ----------------------------------------------------------------------------

set = [ 11, 22, 33, 44, 55, 66, 77, 88 ]
set = [ 1,2,3,4,5,6,7,8 ]

k = 4

'''
# alternate calls k_subsets1 and k_subsets2
subsets = k_subsets2( set, k )
for subs in subsets:
  print( subs )
print( "Number of subsets:", len(subsets) )
'''

#k_subsets3a( set, k, 0, [0]*k, 0 )
k_subsets3b( set, len(set)-1, [0]*k, k-1 )