-5

Given n and k, I need to generate all of the following sequences:

n=5, k=2
0,1,2
0,1,3
0,1,4
1,2,3
1,2,4
2,3,4

Another example:

n=5, k=3
0,1,2,3
0,1,2,4
0,1,3,4
0,2,3,4
1,2,3,4

I think this can be solved using recursion, but got stuck. Need help

Robin Green
  • 32,079
  • 16
  • 104
  • 187
anupamD
  • 862
  • 1
  • 8
  • 21
  • 2
    If you want help with what is clearly your homework, show some effort. What have you tried? Have you typed anything at all or did you just come up with the last sentence while you were typing? Paste some code. Try to explain what part you don't understand. It's in your best interest too. – Nearoo Nov 24 '18 at 21:49

1 Answers1

1

It seems like you already know how to generate the sequences, so just describe the rules you used in your head. Then work the program backwards from there. Below we describe how to generate fixed-size combinations of size k from any iterable, it -

  1. if the amount to choose, k, is zero, return the empty combination, ()
  2. (inductive) k is at least one. If the iterable, it, is empty, there is nothing left to choose. Stop iteration
  3. (inductive) k is at least one and the the iterable has at least one element. Choose the first element of the iterable and add it to each combination of the sub-problem, (it[1:], k - 1). And do not choose this element and yield from the sub-problem, (it[1:], k).
def choosek(it, k):
  if k == 0:                            # 1
    yield ()
  elif not it:                          # 2
    return
  else:                                 # 3
    for c in choosek(it[1:], k - 1):
      yield (*c, it[0])
    yield from choosek(it[1:], k)

for c in choosek("", 2):
  print("".join(c))








for c in choosek("", 3):
  print("".join(c))
Mulan
  • 129,518
  • 31
  • 228
  • 259